Teoria dos grafos: exercícios com soluções passo a passo

1Vértices, arestas e graus

Um grafo consiste em vértices (pontos) e arestas (linhas entre dois vértices). Num grafo simples não há laços nem arestas duplas.

O grau de um vértice é o número de arestas que o tocam. Cada aresta tem duas pontas, então soma 1 ao grau de cada uma. Isso dá o lema do aperto de mãos:

Duas consequências: a soma dos graus é sempre par, e o número de vértices de grau ímpar também é par.

• O grafo completo K_n liga todos os pares: n(n − 1)/2 arestas.
• O grafo bipartido completo K_m,n liga cada vértice de um lado a cada vértice do outro: m·n arestas.
• Um grafo k-regular com n vértices tem n·k/2 arestas.

A matriz de adjacência tem um 1 em (i, j) quando i e j estão ligados. Para um grafo não direcionado ela é simétrica, a soma de uma linha é um grau, e a entrada (i, j) de Mᴸ conta os passeios de comprimento L de i a j.

2Euler e Hamilton

Um circuito euleriano usa cada aresta exatamente uma vez e volta ao ponto de partida. Um caminho euleriano usa cada aresta uma vez, mas pode terminar em outro lugar. Para um grafo conexo:

• todos os graus pares: existe um circuito euleriano;
• exatamente dois graus ímpares: existe um caminho euleriano, de um vértice ímpar ao outro;
• mais de dois graus ímpares: nenhum dos dois.

Um circuito hamiltoniano visita cada vértice exatamente uma vez. Não existe um teste simples de graus para ele. Em K_n há (n − 1)!/2 circuitos hamiltonianos diferentes: fixe o início, ordene os outros n − 1 vértices e divida por 2 pelos dois sentidos.

3Árvores

Uma árvore é um grafo conexo sem ciclos. Toda árvore com n vértices tem exatamente n − 1 arestas. Acrescentar qualquer aresta cria um ciclo; remover qualquer aresta a desconecta.

Uma floresta de c árvores com n vértices tem n − c arestas. Um grafo conexo com m arestas mantém uma árvore geradora depois de remover m − n + 1 arestas.

O lema do aperto de mãos conta as folhas: Σ deg = 2(n − 1). Uma forma curta é L = 2 + Σ (d − 2) sobre os vértices de grau d ≥ 3. Uma árvore com dois vértices de grau 3 e o resto folhas tem 2 + 1 + 1 = 4 folhas.

4Dijkstra e árvores geradoras mínimas

O algoritmo de Dijkstra encontra as menores distâncias a partir de um vértice inicial num grafo com pesos não negativos.

1. Dê ao início a distância 0 e a todos os outros vértices ∞.
2. Fixe o vértice não fixado de menor distância; sua distância agora é definitiva.
3. Para cada vizinho v, atualize d(v) = min(d(v), d(u) + w(u, v)).
4. Repita até que o destino seja fixado.

Uma árvore geradora mínima conecta todos os vértices com o menor peso total. Kruskal ordena as arestas da mais leve para a mais pesada e pega cada uma, a menos que feche um ciclo. Prim faz crescer uma árvore a partir de um vértice inicial, sempre acrescentando a aresta mais leve que sai dela. Ambos param após n − 1 arestas.

5Erros comuns

• Esquecer de dividir a soma dos graus por 2 para obter o número de arestas.
• Testar a existência de um circuito euleriano sem verificar se o grafo é conexo.
• Fixar um vértice em Dijkstra antes que ele tenha a menor distância provisória.
• Pegar as n − 1 arestas mais leves sem verificar a existência de ciclos.
• Contar os circuitos hamiltonianos de K_n como n! em vez de (n − 1)!/2.

6Como são as questões de prova

• Fácil: graus e arestas. Você usa o lema do aperto de mãos, conta as arestas de K_n, K_m,n, grafos regulares e árvores, lê uma matriz de adjacência ou clica no vértice com um dado grau.
• Médio: caminhos eulerianos e árvores. Você decide se um grafo tem circuito ou caminho euleriano, conta as folhas de uma árvore, conta as arestas a remover para obter uma árvore geradora ou conta os circuitos hamiltonianos em K_n.
• Difícil: caminhos mínimos e árvores geradoras. Você executa o algoritmo de Dijkstra, encontra o vértice fixado em uma dada rodada, encontra o peso de uma árvore geradora mínima, clica na aresta que Kruskal ou Prim acrescenta em seguida ou conta passeios com a matriz de adjacência.