Pesquisa Teoria Dos Grafos

Pesquisa: Grafos

Conceito:

A teoria dos grafos é um ramo da matemática que estuda as relações entre os objetos de um determinado conjunto. Para tal são empregadas estruturas chamadas de grafos, G(V,A), onde V é um conjunto não vazio de objetos denominados vértices e A é um conjunto de pares não ordenados de V, chamado arestas.

Dependendo da aplicação, arestas podem ou não ter direção, pode ser permitido ou não arestas ligarem um vértice a ele próprio e vértices e/ou arestas podem ter um peso (numérico) associado. Se as arestas têm uma direção associada (indicada por uma seta na representação gráfica) temos um grafo direcionado, grafo orientado ou dígrafo. Um grafo com um único vértice e sem arestas é conhecido como o grafo trivial.

Estruturas que podem ser representadas por grafos estão em toda parte e muitos problemas de interesse prático podem ser formulados como questões sobre certos grafos. Por exemplo, a estrutura de ligações da Wikipédia pode ser representada por um dígrafo: os vértices são os artigos da Wikipédia e existe uma aresta do artigo A para o artigo B se e somente se A contém um link para B. Dígrafos são também usados para representar máquinas de estado finito. O desenvolvimento de algoritmos para manipular grafos é um importante tema da ciência da computação.

Aplicabilidade na ciência da computação:

Com o desenvolvimento da ciência da computação, a teoria sobre grafos tem permitido obter resultados importantes de modelos matemáticos que representam várias situações reais e auxiliam na solução de diversos problemas.

A teoria dos grafos é uma área de pesquisa com vasta aplicabilidade em diversas áreas da computação, mas para a solução de problemas complexos, novos resultados precisam ser estudados, e estes resultados requerem conhecimentos profundos da matemática e da ciência da computação.

Complexidade no algoritmo:

Existem diversos algoritmos de grafos, e para cada um deles existe uma complexidade particular.

Para falar sobre a complexidade sobre o algoritmo de um grafo, vou utilizar um problema solucionado com o algoritmo Húngaro, demonstrando também sua solução.

Consideremos um exemplo da aplicação do Algoritmo Húngaro.

Seja G =(V,E) bipartido, onde V =X∪Y, e X = {x1,x2,x3,x4,x5} Y ={y1,y2,y3,y4,y5},

E ={x1y2,x1y3,x2y1,x2y2,x2y4,x2y5,x3y2,x3y3,x4y2,x4y3,x5y5}

Começamos com o emparelhamento M ={x2y2,x3y3,x5y5}.

Construímos a arvore aumentante H a partir do vértice x1 da seguinte forma:

Inicializamos S ={x1} e T =∅.

Seja y2∈ N(S)\T.

Como a aresta y2x2 ∈ M, atualizamos S ={x1,x2} e T ={y2}.

Em seguida, seja y3 ∈ N(S)\T. Como a aresta y3x3∈ M, atualizamos S ={x1,x2,x3} e T = {y2,y3}. Seja y1∈N(S)\T. Como y1 não é M-saturado, temos o caminho aumentante P = x1y2x2y1 na árvore aumentante H.

Temos o emparelhamento aumentado de uma unidade para: M = {x1y2,x2y1,x3y3,x5y5}. Construímos

...