Teoria dos Grafos: Fundamentos, História e Representação
By Brenner Cruvinel • 7 minutes read
recorte higienizado da wikipedia, salvo aqui pra eu ter isso decentemente arquivado. é curadoria, não conteúdo original.
definição
a teoria dos grafos é o ramo da matemática que estuda as relações entre objetos de um conjunto. usa estruturas chamadas grafos, $G(V, E)$, onde $V$ é um conjunto não vazio de objetos chamados vértices (ou nós) e $E$ (do inglês edges, arestas) é um subconjunto de pares não ordenados de $V$.
dependendo da aplicação, a aresta pode ou não ter direção, pode ser permitido ou não uma aresta ligar um vértice a ele próprio, e vértice e aresta podem ter um peso numérico associado. se a aresta tem sentido (indicado por uma seta), temos um dígrafo (grafo orientado). um grafo com um único vértice e sem aresta é o grafo trivial.
estrutura representável por grafo está em toda parte. a estrutura de ligações da wikipedia, por exemplo, é um dígrafo: os vértices são os artigos, e existe uma aresta de A para B se e somente se A contém um link para B. dígrafo também representa máquina de estado finito.
história
o artigo de leonhard euler, publicado em 1736, sobre o problema das sete pontes de Königsberg, é considerado o primeiro resultado da teoria dos grafos. é também um dos primeiros resultados topológicos em geometria, não depende de medida, o que ilustra a conexão profunda entre teoria dos grafos e topologia.
mais de um século depois, enquanto Listing introduzia o conceito de topologia, Cayley estudou uma classe particular de grafos, as árvores, por interesse em formas analíticas do cálculo diferencial, com implicação na química teórica. o primeiro livro didático sobre teoria dos grafos foi escrito por Dénes König, publicado em 1936.
o problema das quatro cores (“é possível colorir qualquer mapa dividido em regiões com apenas quatro cores, de forma que região vizinha não partilhe a mesma cor?”) foi notado primeiro por August Möbius em 1840 e levado adiante por Francis Guthrie em 1852.
definições básicas
um grafo direcionado (dígrafo, ou quiver) consiste de um conjunto $V$ de vértices (não vazio), um conjunto $E$ de arestas, e mapas $s, t : E \to V$, onde $s(e)$ é a fonte e $t(e)$ é o alvo da aresta direcionada $e$.
um grafo não direcionado é dado por $V$, $E$ e uma função $w : E \to P(V)$ que associa a cada aresta um subconjunto de dois (ou de um) elemento de $V$, os pontos terminais.
num grafo com peso, uma função adicional $E \to \mathbb{R}$ associa um custo a cada aresta. esse tipo de grafo aparece em problema de rota ótima, como o caixeiro viajante.
grafo de exemplo: $V = {1, 2, 3, 4, 5, 6}$ e $E = {{1,2}, {1,5}, {2,3}, {2,5}, {3,4}, {4,5}, {4,6}}$. a representação gráfica não deve ser confundida com o grafo em si, a estrutura abstrata. o que importa é qual vértice está conectado a qual, por quantas arestas.
armazenamento em computador
duas famílias de estrutura, com o trade-off clássico de memória contra velocidade de acesso.
estrutura tipo lista (grafo esparso, menos memória): lista de adjacência (associa a cada vértice a lista dos vértices com que tem aresta) e lista de incidência (lista de arestas incidentes a cada vértice).
estrutura tipo matriz (acesso rápido, mais memória): matriz de incidência (0 e 1, linha é vértice, coluna é aresta) e matriz de adjacência (linha e coluna são vértices, 1 indica adjacência). na computação, um grafo finito com $n$ vértices costuma ser representado pela matriz de adjacência $n \times n$, cujo valor na linha $i$ coluna $j$ dá o número de arestas do $i$-ésimo ao $j$-ésimo vértice.
conceitos
valência (ou grau) de um vértice: número de arestas incidentes a ele (laço conta duas vezes). o lema do aperto de mão diz que a soma dos graus de todos os vértices é o dobro do número de arestas:
$$2m = \sum_{v \in V} \deg(v)$$
num dígrafo, distingue-se grau de saída e grau de entrada.
passeio entre A e B: lista alternada de vértice e aresta. o tamanho é o número de arestas, contando repetição. caminho: sequência de vértices em que de cada um existe aresta para o seguinte. caminho simples: nenhum vértice se repete.
- caminho euleriano usa cada aresta exatamente uma vez. ciclo euleriano é o ciclo que faz isso. determinar se existe é trivial.
- caminho hamiltoniano visita cada vértice exatamente uma vez. ciclo hamiltoniano faz isso e fecha. determinar se existe é trabalhoso.
ciclo (ou circuito): caminho que começa e acaba no mesmo vértice. ciclo de comprimento 1 é laço. um grafo é acíclico se não contém ciclo simples.
tipos de grafo
| tipo | definição |
|---|---|
| simples | não direcionado, sem laço, no máximo uma aresta entre dois vértices |
| multigrafo | permite múltiplas arestas entre os mesmos vértices |
| pseudografo | contém aresta paralela e laço |
| completo | cada vértice liga a todos os outros; $K_n$ tem $n(n-1)/2$ arestas |
| nulo | conjunto de vértices vazio |
| vazio | conjunto de arestas vazio |
| regular | todos os vértices com o mesmo grau |
| conexo | existe caminho de qualquer vértice a qualquer outro; $k$-conexo se isso vale após remover $k-1$ vértices |
| árvore | grafo simples, acíclico e conexo; às vezes um vértice é a raiz |
| floresta | conjunto de árvores (acíclico) |
| planar | representável no plano sem cruzar aresta; $K_n$ com $n > 4$ não é planar |
| bipartido | vértices em dois conjuntos, sem aresta dentro do mesmo conjunto; é bipartido sse não contém ciclo de comprimento ímpar |
além desses: subgrafo, subgrafo gerador, subgrafo induzido e grafo parcial; ponto de articulação (vértice cuja remoção desconecta o grafo) e ponte (aresta com o mesmo efeito); clique (subgrafo que também é completo); conjunto independente (vértice não adjacente entre si); grafo bipartido completo e grafo $k$-partido ($k$-coloração); e o teorema das quatro cores, que diz que todo grafo planar pode ser colorido com quatro cores.
percurso e algoritmo
percorrer um grafo é visitar de modo sistemático todo vértice e toda aresta. os dois básicos:
- BFS usa fila. visita cada nó começando do menor nível, da esquerda para a direita. computa a menor distância para todos os vértices alcançáveis. o subgrafo dos caminhos é a breadth-first tree.
- DFS usa pilha. expande o primeiro nó filho e se aprofunda até achar o alvo ou uma folha, aí retrocede (backtrack). gasta menos espaço que a BFS.
a complexidade de tempo das duas é proporcional ao número de vértices mais o de arestas.
problemas e algoritmos que orbitam isso: coloração de grafo, teorema das quatro cores, conjunto independente, clique, caminho mínimo, árvore geradora mínima, as sete pontes de Königsberg, inspeção de rotas (carteiro chinês), caixeiro viajante, fluxo máximo (Ford-Fulkerson), Dijkstra, Kruskal, vizinho mais próximo, Prim.
generalização
num hipergrafo, uma aresta pode conectar mais de dois vértices. um grafo não direcionado pode ser visto como um complexo simplicial: simplices de dimensão um (as arestas) e de dimensão zero (os vértices), e o complexo generaliza isso para dimensão maior. ver também rede complexa, teoria espectral de grafos, rede de pequeno mundo, modelo de Watts e Strogatz.
referências
- Biggs, N.; Lloyd, E.; Wilson, R. (1986). Graph Theory, 1736-1936. Oxford University Press.
- Cayley, A. (1857). On the theory of the analytical forms called trees. Philosophical Magazine, Série IV, 13(85), 172-176.
- Tutte, W.T. (2001). Graph Theory. Cambridge University Press, p. 30.
- Di Battista, G.; Eades, P.; Tamassia, R.; Tollis, I. G. (1994). Algorithms for Drawing Graphs: an Annotated Bibliography. Computational Geometry: Theory and Applications, 4, 235-282.
- Longabaugh, W. (2012). Combing the hairball with BioFabric. BMC Bioinformatics, 13, 275.
- Goodrich, M. T.; Tamassia, R. (2001). Estruturas de Dados e Algoritmos em Java, 2ª ed. Bookman, p. 502-503.
- West, D. B. (2001). Introduction to Graph Theory, 2nd ed. Prentice Hall, p. 20.