Teoria dos grafos
Keywords: Teoria dos grafos, Algoritmo, Algoritmo de Dijkstra, Algoritmo de Kruskal, Caminho hamiltoniano, Ciência da computação, Clique, Combinatória, Conjunto, Conjunto das partes
A Teoria dos Grafos é o ramo da matemática que estuda as propriedades de grafos.
| Imagem não encontrada 6n-graf.png Image:6n-graf.png |
| Um grafo com 6 vértices e 7 arestas. |
Um grafo é um conjunto de pontos, chamados vértices (ou nodos), conectados por linhas, chamadas de arestas (ou arcos). A nomenclatura de nodos e arcos está caindo em desuso.
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, ou dígrafo.
Um grafo com um único vértice e sem arestas é conhecido como o grafo trivial ou "o ponto".
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 links da Wikipedia pode ser representada por um dígrafo: os vértices são os artigos da Wikipedia 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.
| Conteúdo |
Histórico
O artigo de Leonhard Euler em Sete Pontes de Königsberg é considerado o primeiro resultado da teoria dos grafos. É também considerado um dos primeiros resultados topológicos na geometria; isto é, não dependente de quaisquer medidas. Isso ilustra a profunda conexão entre a teoria dos grafos e topologia.
Definições de Grafos e Dígrafos
Na literatura, as definições básicas da teoria dos grafos variam bastante. Aqui estão as convenções usadas nesta enciclopédia.
Um grafo direccionado (também chamado digrafo ou quiver) consiste de
- um conjunto V de vértices,
- um conjunto E de arestas e
- mapas s, t : E → V, onde s(e) é a fonte e t(e) é o alvo da aresta direccionada e.
Um grafo não direccionado (ou simplesmente grafo) é dado por
- um conjunto V de vértices,
- um conjunto E de arestas e
- uma função w : E → P(V) que associa a cada aresta um subconjunto de dois ou de um elemento de V, interpretado como os pontos terminais da aresta.
Em um grafo ou dígrafo com pesos, uma função adicional E → R associa um valor a cada aresta, o que pode ser considerado seu "custo"; tais grafos surgem em problemas de rota ótima tais como o problema do caixeiro viajante.
Representação "gráfica" (layout do grafo)
Os grafos são geralmente representados "graficamente" da seguinte maneira: é desenhado um círculo para cada vértice, e para cada aresta é desenhado um arco conectando suas extremidades. Se o grafo for direcionado, seu sentido é indicado na aresta por uma seta.
Note que essa representação gráfica (o layout) não deve ser confundida com o grafo em si (a estrutura abstrata, não-gráfica). Vários diferentes layouts podem corresponder ao mesmo grafo (ver http://www.aisee.com/gallery/graph23.htm). O que importe é quais vértices estão conectados entre si por quantas arestas.
Seguem alguns exemplos de layouts de grafos:
- http://www.aisee.com/gallery
- http://www.research.att.com/sw/tools/graphviz/examples/
- http://www.tomsawyer.com/gallery/gallery.php
Glossário dos conceitos básicos de Teoria dos Grafos
Um laço (loop) num grafo ou num digrafo é uma aresta e em E cujas terminações estão no mesmo vértice. Um digrafo ou grafo é chamado simples se não tem laços e existe no máximo uma aresta entre quaisquer dois vértices.
| Imagem:6n-graf.png |
O grafo de exemplo exibido à direita é um grafo simples com o conjunto de vértices V = {1, 2, 3, 4, 5, 6} e um conjunto de arestas E = {{1,2}, {1,5}, {2,3}, {2,5}, {3,4}, {4,5}, {4,6}} (com o mapeamento w sendo a identidade).
Uma aresta conecta dois vértices; esses dois vértices são ditos como incidentes à aresta. A valência (ou grau) de um vértice é o número de arestas incidentes a ele, com loops contados duas vezes. No grafo de exemplo os vértices 1 e 3 possuem uma valência de 2, os vértices 2, 4 e 5 têm a valência de 3 e o vértice 6 tem a valência de 1. Se E é finito, então a valência total dos vértices é o dobro do número de arestas. Em um dígrafo, distingue-se o grau de saída (o número de arestas saindo de um vértice) e o grau de entrada (o número de arestas entrando em um vértice). O grau de um vértice é igual à soma dos graus de saída e de entrada.
Dois vértices são considerados adjascentes se uma aresta existe entre eles. No grafo acima, os vértices 1 e 2 são adjascentes, mas os vértices 2 e 4 não são. O conjunto de vizinhos de um vértice consiste de todos os vértices adjascentes a ele. No grafo-exemplo, o vértice 1 possui 2 vizinhos: vértice 2 e vértice 5. Para um grafo simples, o número de vizinhos de um vértice é igual à sua valência.
Na computação, um grafo finito direcionado ou não-direcionado (com, digamos, n vértices) é geralmente representado por sua matriz de adjacência: uma matriz n-por-n cujo valor na linha i e coluna j fornece o número de arestas do i-ésimo ao j-ésimo vértices.
Um caminho é uma sequência de vértices tal que de cada um dos vértices existe uma aresta para o vértice seguinte. Um caminho é chamado simples se nenhum dos vértices no caminho se repete. O comprimento do caminho é o número de arestas que o caminho usa, contando-se arestas múltiplas múltiplas vezes. O custo de um caminho num grafo balanceado é a soma dos custos das arestas atravessadas. Dois caminhos são independentes se não tiverem nenhum vértice em comum, excepto o primeiro e o último.
No grafo de exemplo, (1, 2, 5, 1, 2, 3) é um caminho com comprimento 5, e (5, 2, 1) é um caminho simples de comprimento 2.
Se for possível estabelecer um caminho de qualquer vértice para qualquer outro vértice de um grafo, diz-se que o grafo é conexo. Se for sempre possível estabelecer um caminho de qualquer vértice para qualquer outro vértice mesmo depois de remover k-1 vértices, então diz-se que o grafo está k-conexo. Note que um grafo está k-conexo se e só se contém k caminhos independentes entre qualquer par de vértices. O grafo de exemplo acima é conexo (e portanto 1-conexo), mas não é 2-conexo.
Um ciclo (ou circuito) é um caminho que começa e acaba com o mesmo vértice. Ciclos de comprimento 1 são laços. No grafo de exemplo, (1, 2, 3, 4, 5, 2, 1) é um ciclo de comprimento 6. Um ciclo simples é um ciclo que tem um comprimento pelo menos de 3 e no qual o vértice inicial só aparece mais uma vez, como vértice final, e os outros vértices aparecem só uma vez. No grafo acima, (1, 5, 2, 1) é um ciclo simples. Um grafo chama-se acíclico se não contém ciclos simples.
Um ponto de articulação é um vértice cuja remoção desliga um grafo. Uma ponte é uma aresta cuja remoção desliga um grafo. Um componente biconectado é um conjunto máximo de arestas tal que qualquer par de arestas do conjunto fazem parte de um ciclo simples comum. O contorno de um grafo é o comprimento do ciclo simples mais curto no grafo. O contorno de um grafo acíclico é, por definição, infinito.
Uma árvore é um grafo simples acíclico e conexo. Às vezes, um vértice da árvore é distinto e chamado de raiz. Árvores são comumente usadas como estruturas de dados em informática (veja estrutura de dados em árvore).
Uma floresta | teoria_dos_grafos é um conjunto de árvores; equivalentemente a uma floresta, em algum grafo acíclico.
Um subgrafo de um grafo G é um grafo cujo conjunto dos vértices é um subconjunto do conjunto de vértices G, cujo conjunto de arestas é um subconjunto do conjunto de arestas de G, e cuja função w é uma restrição da função de G.
Um grafo parcial de um grafo G é um subgrafo com o mesmo conjunto de vértices que G. Uma árvore parcial é um grafo parcial que é árvore. Todo grafo tem pelo menos uma árvore parcial.
Um grafo completo é o grafo simples em que todo vértice é adjacente a outro vértice. O grafo do exemplo não é completo. O grafo completo de n vertices é frequentemente denotado porKn. Ele tem n(n-1)/2 arestas (correspondendo a todas as possíveis escolhas de pares de vértices).
Um grafo planar é aquele que pode ser representado em um plano sem qualquer interseção entre arestas. O grafo do exemplo é planar; o grafo completo de n vertices, para n> 4, não é planar.
Um caminho euleriano em um grafo é o caminho que usa cada aresta exatamente uma vez. Se tal caminho existir, o grafo é chamado traversável. Um ciclo euleriano é um ciclo que usa cada aresta exatamente uma vez. Existe um conceito paralelo: um caminho hamiltoniano em um grafo é o caminho que visita cada vertex uma só vez; e um ciclo hamiltoniano é um ciclo que visita cada vértice uma só vez. O grafo do exemplo não contém um caminho euleriano, mas contém um caminho hamiltoniano. Enquanto determinar se um dado grafo contém um caminho ou ciclo euleriano é trivial, o mesmo problema para caminhos e ciclos hamiltonianos é extremamente árduo.
O grafo nulo é o grafo cujos conjuntos de vertices e de arestas são vazios.
Um conjunto independente em um grafo é um conjunto de vértices não adjacentes entre si. No exemplo acima, os vértices 1, 3 e 6 formam um conjunto independente e 3, 5 e 6 são outro conjunto independente.
Uma clique em um grafo é um subgrafo que também é um grafo completo. No grafo do exemplo acima, os vértices 1, 2 e 5 formam um clique.
Um grafo bipartido é o grafo cujos vértices podem ser divididos em dois conjuntos, nos quais não há arestas entre vértices de um mesmo conjunto.Pode-se provar se um grafo é bipartido se não existe qualquer circuito de comprimento ímpar.
Um grafo k-partido ou grafo de k-coloração é um grafo cujos vértices podem ser particionados emk conjuntos disjuntos, nos quais não há arestas entre vértices de um mesmo conjunto. Um grafo 2-partido é o mesmo que grafo bipartido.
Problemas que envolvem grafos
- Coloração de grafos: o Teorema das quatro cores
- Conjuntos de Grafos
- Problemas de roteamento:
- Sete pontes de Königsberg
- árvore de recobrimento mínimo
- Problema do caminho mínimo
- Problema da inspeção de Rotas (também conhecido como o "Problema do Carteiro Chinês")
- Problema do caixeiro viajante
- Fluxos de rede:
- conjectura da reconstrução
- Problemas de Isomorfismo (casamento de grafos)
- Rotulação canônica?
- Isomorfismo de subgrafos e monomorfismos.
- Máximo subgrafo comum
Algoritmos Importantes
- algoritmo de Dijkstra
- algoritmo de Kruskal
- algoritmo do vizinho mais próximo
- algoritmo de Prim
Generalizações
Num hipergrafo uma aresta pode conectar mais que dois grafos.
Um grafo não-direcionado pode ser visto como um complexo simplicial consistindo de símplices de uma dimensão (as arestas) e símplices de dimensão zero (os vértices). Ou seja, complexos são generalizações de grafos que permitem símplices de maiores dimensões.
Todo grafo gera um(a) matróide, mas em geral o grafo não pode ser recuperado da sua matróide, logo, matróides não são generelizações reais de grafos.
Ferramentas de grafos populares
- http://www.research.att.com/sw/tools/graphviz/
- http://www.cs.uni-sb.de/RW/users/sander/html/gsvcg1.html
- http://www.aisee.com
- http://www.tulip-software.org
- http://www.projetorox.org
Referências Internas
- Combinatória
- Otimização Combinatória
- Teoria da computação
- Teoria de Ramsey
Veja também
- Estrutra de dados árvore ordenada - DAGs, árvores binárias e outras formas especiais de grafos.
- Grafo (estrutura de dados)
- Lista de tópicos da teoria dos grafos
- Construção de grafos
Links externos
Em inglês
- Graph theory tutorial
- Graph theory algorithm presentation
- Some graph theory algorithm animations
- Step through the algorithm to understand it.
- The compendium of algorithm visualisation sites
- A search site for finding algorithm implementations, explanations and animations