Laboratório de grafos

Grafo

Um par G = (V, E): V é um conjunto de vértices e E, um conjunto de arestas, cada uma ligando dois vértices. O grafo vazio, sem vértices, também é um grafo. Onde cada vértice fica no desenho não importa: o grafo é só quem está ligado a quem.

Grafo não direcionado

Cada aresta é um par não ordenado {u, v}: liga u a v e v a u, como uma amizade numa rede social. Ela é desenhada como uma linha, sem seta. Quando nada se diz sobre a direção, o grafo é não direcionado.

Grafo direcionado

Também chamado de grafo dirigido, ou digrafo. Cada aresta tem direção: o par ordenado (u, v) vai de u para v e é diferente de (v, u), como um link de uma página para outra. Na lista de adjacência, v entra só na lista de u; na matriz de adjacência, só a casa da linha u e da coluna v vale 1.

Laço

Uma aresta que liga um vértice a ele mesmo, também chamada de loop. No grau, o laço conta duas vezes, porque as duas pontas dele estão no mesmo vértice; assim, a soma dos graus continua 2m. Num grafo direcionado, o laço (v, v) soma 1 ao grau de entrada de v e 1 ao de saída.

Multígrafo

Um grafo que pode ter mais de uma aresta entre os mesmos dois vértices: são as arestas paralelas, ou múltiplas, como várias pontes entre as mesmas duas margens de um rio. Alguns livros também aceitam laços no multígrafo; outros chamam esse caso de pseudografo. Na matriz de adjacência, cada casa guarda quantas arestas ligam os dois vértices.

Grafo simples

Um grafo sem laços e sem arestas paralelas: entre dois vértices há no máximo uma aresta. É o caso mais comum, e quase sempre o do laboratório: em Conceitos, a opção “Laços e arestas paralelas” transforma o grafo num multígrafo, e em Direção e relações os laços representam os pares (x, x) de uma relação.

Vértices adjacentes e grau

Dois vértices ligados por uma aresta são adjacentes, ou vizinhos. O grau de um vértice é o número de arestas que incidem nele. Cada aresta conta para as suas duas pontas; por isso, a soma dos graus é 2m, o dobro do número de arestas.

Lista de adjacência

Para cada vértice, uma lista encadeada com os seus vizinhos: cada célula da lista guarda um vizinho e um ponteiro para a célula seguinte, e o ponteiro da última célula é null, desenhado como o símbolo de aterramento. Num grafo sem direção, cada aresta {u, v} aparece em duas listas, e as listas somam 2m células.

Matriz de adjacência

Com os vértices em fila, v₁, v₂, …, vₙ, uma tabela n × n em que a casa da linha i e da coluna j vale 1 quando vᵢ e vⱼ são adjacentes, e 0 quando não são. Sem direção, a matriz é simétrica, e a soma de cada linha é o grau do vértice. Ela ocupa n² casas, mesmo com poucas arestas, mas responde olhando uma casa só se dois vértices são vizinhos.

Subgrafo

Um subgrafo de G = (V, E) é um grafo H = (V′, E′) com V′ ⊆ V e E′ ⊆ E: alguns vértices de G e algumas das arestas entre eles. As componentes são subgrafos, e dizer que um grafo contém o K₅ é dizer que ele tem o K₅ como subgrafo.

Grafo conexo e componentes

O grafo é conexo quando há caminho entre quaisquer dois vértices. As componentes são os subgrafos conexos máximos: cada uma é conexa e não cabe numa parte conexa maior. Elas formam uma partição do conjunto de vértices.

Pesos

Números associados às arestas, como distâncias, custos ou tempos. O peso de um caminho é a soma dos pesos das suas arestas.

Caminho

Uma sequência de vértices v₀, v₁, …, v_k em que cada vértice é vizinho do seguinte. O comprimento k é o número de arestas percorridas: dois vértices vizinhos, com a aresta entre eles, já formam um caminho, de comprimento 1. O caminho é simples quando não repete vértices.

Distância

A distância entre dois vértices é o comprimento do caminho mais curto entre eles: o menor número de arestas para ir de um ao outro. Cada vértice está à distância 0 de si mesmo, e dois vértices de componentes diferentes não têm distância (às vezes se diz que ela é infinita). A travessia em largura, do capítulo Algoritmos, encontra as distâncias a partir do início.

Ciclo

Um caminho fechado: depois de pelo menos uma aresta, termina no vértice em que começou. No sentido geral, pode repetir arestas e vértices.

Circuito

Um ciclo que não repete arestas. Os vértices ainda podem se repetir.

Ciclo simples

Um circuito que também não repete vértices, a não ser o primeiro, que é também o último. É o que a Leitura 08 chama simplesmente de ciclo (veja a nota 2 da leitura).

Ciclo sem corda

Um ciclo simples que não contém outro ciclo formado com os seus vértices: nenhuma aresta liga dois vértices do ciclo que não são vizinhos nele. Uma aresta assim, a corda, dividiria o ciclo em dois ciclos menores. Também se diz ciclo induzido.

Circuito euleriano

Um circuito que passa por todas as arestas do grafo, cada uma uma única vez. Teorema de Euler: um grafo conexo tem circuito euleriano se, e somente se, todos os vértices têm grau par.

Caminho euleriano

Um caminho que passa por todas as arestas do grafo, cada uma uma única vez, sem voltar ao início: é desenhar o grafo sem tirar o lápis do papel. Um grafo conexo tem um caminho assim exatamente quando tem dois vértices de grau ímpar, e o caminho começa num deles e termina no outro. Sem nenhum vértice de grau ímpar, o que existe é o circuito euleriano.

Circuito hamiltoniano

Um ciclo simples que passa por todos os vértices do grafo. Não se conhece uma regra simples e rápida para saber se ele existe; o grafo de Petersen, no menu de exemplos do laboratório, não tem nenhum.

Vértice de corte

Um vértice cuja remoção, junto com as arestas que incidem nele, desconecta o grafo. Quando existe, a conectividade de vértices é κ(G) = 1.

Ponte

Uma aresta cuja remoção desconecta o grafo. Uma ponte não está em nenhum ciclo simples; quando existe, a conectividade de arestas é λ(G) = 1.

Árvores: só pontes

Uma árvore é um grafo conexo sem ciclos simples. Como nenhuma aresta está num ciclo, tirar qualquer uma desconecta a árvore: toda aresta é uma ponte. Tirar um vértice que não é folha também a desconecta. Por isso, numa árvore com pelo menos dois vértices, κ = λ = 1: ela é conexa com o menor número possível de arestas, n − 1, e nenhuma sobra. Veja o laboratório de árvores.

Conectividade de vértices κ(G)

O menor número de vértices cuja remoção desconecta G ou o deixa com um vértice só. G é k-conexo quando κ(G) ≥ k: continua conexo depois de perder quaisquer k − 1 vértices. No grafo completo Kₙ, κ = n − 1.

Conectividade de arestas λ(G)

O menor número de arestas cuja remoção desconecta G. G é k-aresta-conexo quando λ(G) ≥ k: continua conexo depois de perder quaisquer k − 1 arestas.

Desigualdade de Whitney

κ(G) ≤ λ(G) ≤ δ(G), em que δ(G) é o menor grau do grafo. Tirar as arestas de um vértice de grau mínimo o isola; por isso λ ≤ δ. As duas desigualdades podem ser estritas, como no desenho.

Graus de entrada e de saída

O grau de entrada de um vértice é o número de setas que chegam nele; o grau de saída, o número de setas que saem dele. Cada seta sai de um vértice e chega a outro; por isso, somados sobre todos os vértices, os graus de entrada e os de saída dão, cada um, o número de arestas.

Fonte e sumidouro

Uma fonte é um vértice com grau de entrada 0: nenhuma seta chega nele. Um sumidouro é um vértice com grau de saída 0: nenhuma seta sai dele. Todo DAG com pelo menos um vértice tem uma fonte e um sumidouro; numa ordem topológica, o primeiro vértice é sempre uma fonte, e o último, um sumidouro.

Ciclo direcionado

Num grafo direcionado, um ciclo tem de andar sempre no sentido das setas: não dá para voltar por uma seta ao contrário. Um laço é um ciclo direcionado de comprimento 1. O grafo direcionado sem nenhum ciclo direcionado é um DAG.

Grafo de uma relação

Uma relação R num conjunto V é um grafo direcionado: há aresta de x para y quando (x, y) ∈ R. Reflexiva, simétrica, antissimétrica e transitiva viram propriedades das setas.

Fecho transitivo

O fecho transitivo de uma relação R é a menor relação transitiva que contém R. No grafo, ele põe a seta x → z sempre que há um caminho de x até z seguindo as setas. O último passo do guia de Direção e relações monta o fecho de uma cadeia, seta por seta.

DAG e ordem topológica

DAG é um grafo direcionado sem ciclos direcionados (directed acyclic graph). Numa ordem topológica, toda seta vai de um vértice para outro que vem depois dele; todo DAG tem pelo menos uma ordem topológica dos vértices.

Grafo completo Kₙ

O grafo completo Kₙ tem n vértices, e cada par deles é ligado por uma aresta: são n(n − 1)/2 arestas, e todo vértice tem grau n − 1. Um grafo em que todos os vértices têm o mesmo grau k é k-regular; o Kₙ é (n − 1)-regular. O K₄ é planar; do K₅ em diante, nenhum Kₙ é.

Grafo bipartido

Um grafo é bipartido quando os vértices se dividem em duas partes, X e Y, e toda aresta liga um vértice de X a um de Y: dentro de cada parte, ninguém é vizinho. Um grafo é bipartido se, e somente se, não tem ciclo de comprimento ímpar. Árvores, ciclos de comprimento par e hipercubos são bipartidos; o triângulo não é.

Bipartido completo Kᵢ,ⱼ

O grafo bipartido completo Kᵢ,ⱼ tem uma parte com i vértices e outra com j, e cada vértice de uma parte é vizinho de todos os da outra: são i · j arestas. A estrela é o K₁,ₙ. O Kᵢ,ⱼ é planar quando i ≤ 2 ou j ≤ 2; o K₃,₃ já não é.

Hipercubo

O hipercubo Qₙ tem um vértice para cada sequência de n bits, e dois vértices são vizinhos quando as sequências diferem em exatamente um bit. Ele tem 2ⁿ vértices, todos de grau n, e n · 2ⁿ⁻¹ arestas. É bipartido: as sequências com uma quantidade par de 1s formam uma parte, e as com quantidade ímpar, a outra. Para n ≥ 2, tem circuito hamiltoniano, o código de Gray, em que cada sequência difere da anterior num bit só. Q₁, Q₂ e o cubo Q₃ são planares; o Q₄ já não é.

Estrela

A estrela K₁,ₙ tem um vértice no centro ligado a n vértices de grau 1, as folhas, e nenhuma outra aresta. É uma árvore, com n + 1 vértices e n arestas, e é o bipartido completo em que uma das partes tem só o centro. Sem o centro, sobram n vértices isolados. Como toda árvore, é planar.

Caterpillar

Uma árvore em que todo vértice está num mesmo caminho, a espinha dorsal, ou é vizinho de um vértice dele. Com pelo menos três vértices, a espinha aparece quando se apagam todas as folhas (os vértices de grau 1): o que sobra tem de ser um caminho. Todo caminho é um caterpillar, e toda estrela também: sem as folhas, sobra só o centro. Como toda árvore, é planar e bipartido. Veja o laboratório de árvores.

Cactus

Um grafo conexo em que dois ciclos simples quaisquer têm no máximo um vértice em comum. Equivalentemente, cada aresta está em no máximo um ciclo simples. Toda árvore é um cactus, sem nenhum ciclo simples; o K₄ não é, porque os ciclos A – B – C – A e A – B – D – A têm a aresta A–B em comum. Todo cactus é planar: cada ciclo pode ser desenhado do lado de fora dos outros.

Lollipop

O lollipop L(k, ℓ) junta um grafo completo Kₖ, a bala, a um caminho com ℓ vértices, o palito, por uma única aresta; o nome vem do pirulito, em inglês. Essa aresta e as do palito não estão em nenhum ciclo simples. Já na bala, com k ≥ 4, há ciclos simples com arestas em comum: por isso, L(k, ℓ) só é um cactus quando k ≤ 3. Ele é planar quando k ≤ 4; com k ≥ 5, contém o K₅ e não é.

Mergulho e grafo planar

Um mergulho é um desenho do grafo no plano em que as arestas só se encontram nas pontas. O grafo que admite um mergulho é planar: ser planar é uma propriedade do grafo, não de um desenho dele.

Fórmula de Euler

Um mergulho divide o plano em regiões, as faces, contando a de fora. Num grafo planar conexo com n vértices, m arestas e f faces, vale n − m + f = 2. Se o grafo é simples e tem n ≥ 3, cada face tem pelo menos 3 arestas na borda, e cada aresta está na borda de no máximo duas faces; daí sai m ≤ 3n − 6. Sem triângulos, cada face tem pelo menos 4 arestas na borda, e m ≤ 2n − 4. Quem desobedece a uma dessas contas não é planar; quem obedece pode ser planar ou não.

Grafos não planares

O K₅ e o K₃,₃ não são planares: todo desenho deles no plano tem algum cruzamento. As contas da fórmula de Euler mostram por quê: o K₅ tem m = 10, mais que 3n − 6 = 9; o K₃,₃, bipartido e sem triângulos, tem m = 9, mais que 2n − 4 = 8.

Subdivisão e teorema de Kuratowski

Subdividir uma aresta é trocá-la por um caminho, com vértices novos no meio. Teorema de Kuratowski: um grafo é planar se, e somente se, não contém uma subdivisão do K₅ nem do K₃,₃. O grafo de Petersen passa nas duas contas, com m = 15 ≤ 2n − 4 = 16, mas não é planar. Entre os grafos especiais, Kₙ é planar só com n ≤ 4; Kᵢ,ⱼ, só com i ≤ 2 ou j ≤ 2; Qₙ, só com n ≤ 3; L(k, ℓ), só com k ≤ 4; e árvores e cactus, sempre.

Marcar e visitar

Marcar um vértice é registrar que ele já foi encontrado; visitar é processá-lo, isto é, fazer com ele o que a travessia precisa. O vértice é marcado na hora em que entra na fila ou na pilha, e um vértice marcado nunca entra de novo: cada vértice entra no máximo uma vez. Se só os visitados fossem marcados, um vértice poderia entrar uma vez para cada aresta que chega nele.

Fila e pilha

Duas formas de guardar os vértices que esperam a vez. Na fila, quem chega vai para o fim, e quem sai é o da frente: o primeiro a entrar é o primeiro a sair (first in, first out). Na pilha, quem entra e quem sai é o do topo: o último a entrar é o primeiro a sair (last in, first out). A travessia em largura usa uma fila; a em profundidade, uma pilha.

Travessia em largura (BFT)

1. Marque o vértice de início e ponha-o numa fila vazia.
2. Enquanto a fila não estiver vazia:
   1. tire o vértice da frente da fila e visite-o;
   2. marque cada vizinho dele ainda não marcado e ponha-o no fim da fila.

A travessia anda em ondas a partir do início e, sem pesos, chega a cada vértice pelo menor número de arestas.

Travessia em profundidade (DFT)

1. Marque o vértice de início e empurre-o numa pilha vazia.
2. Enquanto a pilha não estiver vazia:
   1. tire o vértice do topo da pilha e visite-o;
   2. marque cada vizinho dele ainda não marcado e empurre-o na pilha.

É a travessia em largura com uma pilha no lugar da fila: quem entrou por último sai primeiro, e a travessia mergulha por um caminho antes de voltar.

Árvore da travessia

As arestas pelas quais cada vértice foi marcado formam uma árvore com raiz no início. Na travessia em largura, a profundidade de cada vértice nessa árvore é a sua distância até o início. Veja o laboratório de árvores.

Algoritmo de Kahn

1. Conte o grau de entrada de cada vértice e ponha numa fila os vértices de grau de entrada 0.
2. Enquanto a fila não estiver vazia:
   1. tire o vértice da frente da fila e acrescente-o à ordem;
   2. retire as setas que saem dele; cada vértice que ficar com grau de entrada 0 entra no fim da fila.

Se algum vértice ficar fora da ordem, o grafo tem um ciclo direcionado e não tem ordem topológica.