2 - GRAFOS EULERIANOS E HAMILTONIANOS


Última revisão: 29/3/2001


Conteúdo

Circuito euleriano e grafo euleriano
Grafo semi-euleriano e carteiro chinês
Ciclo hamiltoniano e grafo hamiltoniano
Exercícios

Circuito euleriano e grafo euleriano

Um caminho ou um circuito é dito euleriano se ele contém todas as arestas de um grafo. Um grafo que contém um circuito euleriano é um grafo euleriano. Um grafo que não contém um circuito euleriano mas contém um caminho euleriano será chamado grafo semi-euleriano. As figuras 1a e 1b ilustram grafos euleriano e semi-euleriano, respectivamente.

Figura 1

Por definição, um caminho é sempre conexo. Como um circuito euleriano contém todas as arestas de um grafo, um grafo euleriano é sempre conexo, com a exceção dos vértices isolados.

Teorema 2-1: Um grafo conexo G é um grafo euleriano se e somente se todo vértice de G possui grau par.

Prova:

Ida: Seja G um grafo euleriano. Logo ele contém um circuito euleriano. Por cada ocorrência de vértice desse caminho, existe uma aresta que chega nesse vértice e outra que sai desse vértice. Como toda aresta faz parte do caminho, isto é, nenhuma aresta fica fora do caminho, necessariamente o número de arestas por cada vértice é par.

Volta: Suponhamos que todos os vértices possuem grau par. Seja vi um vértice do grafo. Tentemos, a partir de vi, construir um caminho que não passa duas vezes pela mesma aresta, e até que não seja possível continuar. Como todos os vértices possuem um grau par, sempre sera possível entrar e sair de um vértice. A única exceção é o vértice vi onde o caminho vai terminar. Se esse caminho, que chamaremos C1, contém todas as arestas de G, temos um circuito euleriano. Senão, retiramos de G todas as arestas que fazem parte de C1. No grafo resultante G', todos os vértices também possuem grau par e necessariamente um deles faz parte de C1, senão o grafo não seria conexo. Recomeçamos o mesmo processo com o grafo G', partindo de um vértice comum com C1, obtendo assim um novo circuito C2. A figura 2 mostra que dois circuitos que têm um vértice em comum podem formar um circuito único: chegando no vértice comum em um dos dois circuitos, continuamos o percurso no outro circuito. Continuando esse processo, necessariamente obteremos um circuito único que contém todas as arestas de G.

Figura 2

Um aspecto muito interessante dessa prova é que ela sugere um algoritmo para identificar um circuito euleriano. Considere por exemplo o grafo ilustrado na figura 3a.

Figura 3

Supondo que começamos pelo vértice 1, e escolhemos aleatoriamente um aresta nunca visitada a cada vértice visitado, até voltar ao vértice 1 sem poder sair mais. A figura 3b mostra um circuito obtido, que consiste na sequência 1, 2, 5, 9, 10, 11, 6, 3 e 1. Como sobram arestas não percorridas, devemos recomeçar a partir de um vértice desse circuito. Supondo que o vértice 6 foi escolhido, podemos obter, como ilustrado na figura 3c, o circuito 6, 7, 12, 8, 7, 4, 3, 2, 6, 5, 10 , 6. Combinando esses circuito com o que já tinhamos, obtemos um novo circuito 1, 2, 5, 9, 10, 11, 6, 7, 12, 8, 7, 4, 3, 2, 6, 5, 10, 6, 3, 1. Como esse circuito cobre o grafo inteiro, não é preciso recomeçar o processo: já temos o nosso circuito euleriano.

Esse algoritmo é conhecido como o algoritmo de Hierholzer. Suponhamos que um caminho de um vértice v1 até vk é representado por uma lista [v1, a1,..., ak-1, vk], que alterna vértices e arestas. Eis uma descrição do algoritmo de Hierholzer (supondo que já sabemos que o grafo é euleriano):

função Hierholzer(G = (V,E): grafo) : caminho
G' := G     { G' = (V', E')}
v0 := um vértice de G'
C := [v0] {Inicialmente, o circuito contém só v0}
Enquanto E' não vazio
vi := um vértice de C tal que d(vi) > 0 em G'
C' := Circuito em G' que contém vi
G' := G' - {a | a é aresta contida em C'}
Em C, substituir o vértice vi pelo circuito C'
Retornar C

Existe uma outra maneira de identificar um circuito euleriano. É o algoritmo de Fleury, que é o seguinte:

função Fleury(G = (V,E): grafo) : caminho
G' := G     { G' = (V', E')}
v0 := um vértice de G'
C := [v0] {Inicialmente, o circuito contém só v0}
Enquanto E' não vazio
vi := último vértice de C
Se vi tem só uma aresta incidente;
ai := a aresta incidente a vi em G'
Senão
ai := uma aresta incidente a vi em G' e que não é uma ponte
Retirar a aresta ai do grafo G'
Acrescentar ai no final de C
vj := vértice ligado a vi por ai
Acrescentar vj no final de C
Retornar C

Para entender como funciona o algoritmo de Fleury, considere o grafo da figura 4a. Suponhamos que o algoritmo começa com o vértice 6. Ele pode escolher uma das arestas h, d, e ou i. Supondo que ele escolhe d, ele se encontra depois no vértice 2, onde ele é obrigado a seguir pela ponte que liga com o vértice 5. Isso é ilustrado na figura 4b. Nesse momento, ele pode escolher entre b, g o h. O último é descartado por ser uma ponte. Então sobram somente b e g. Supondo que b é selecionado, ele chega ao vértice 1, como ilustrado em 4. Nas três próximas etapas, ele não tem escolha. Chegando ao vértice 6, de novo ele tem mais du uma opção. Em mais três etapas, ele volta à origem, o que completa o circuito euleriano.

Figura 4

Agora, podemos resolver facilmente o problema das pontes de Königsberg. Simplesmente temos que ver se grafo utilizado para representar o problema é um grafo euleriano. Mas como nem todos os vértices desse grafo possuem grau par, ele não é um grafo euleriano. Então, é impossível atravessar todas as pontes uma vez só e voltar no lugar da partida.

Agora vamos ver mais um teorema interessante sobre os grafos eulerianos.

Teorema 2-2: Um grafo conexo G é um grafo euleriano se e somente se ele pode ser decomposto em circuitos.

Prova:

Ida: Deixamos esta prova como exercício.

Volta:

Suponhamos um grafo G que pode ser decomposto em circuitos, isto é, G é a união de circuitos disjuntos. Como todo vértice de um circuito é de grau par, o grau de cada vértice de G é necessariamente par. Então G é um grafo euleriano.


Grafo semi-euleriano e carteiro chinês

Podemos utilizar o teorema 2-1 para determinar se um grafo é semi-euleriano? A resposta é sim. Imaginamos o caminho euleriano desse grafo. Consideramos agora os dois vértices que formam as extremidades desse caminho. Se acrescentarmos no grafo uma aresta entre esse dois vértices, obteremos um grafo euleriano, com todos os vértices pares. Isso significa que o grafo original tem exatamente dois vértices ímpares, que vão formar as extremidades do caminho euleriano.

Um problema interessante ligado ao conceito de grafo semi-euleriano é o problema do carteiro chinês. Imagine um carteiro que deve percorrer um roteiro todo dia. O problema é de identificar esse roteiro de maneira a minimizar a distância total percorrida. Essa situação pode ser representada por um grafo onde as arestas correspondem às ruas e os vértices correspondem aos cruzamentos.

Se o grafo é euleriano, a solução consiste simplesmente em achar um circuite euleriano. Mais interessante é o caso de um grafo não euleriano. Consideremos por exemplo um grafo semi-euleriano, como ilustrado na figura 5. Supondo que o carteiro quer voltar ao lugar de origem, sabem com certeza que para cada um dos vértices 1 e 8, uma das arestas adjacentes sera atravessada no mínimo duas vezes.

Figura 5

Uma solução ao problema é a seguinte. Transforme o grafo en grafo euleriano, duplicando as arestas que formam o caminho mais curto entre os dois vértices de grau ímpar. Esse caminho é indicado em vermelho na figura 5. O grafo assim obtido é euleriano. Agora podemos aplicar um dos algoritmos de identificação de circuito euleriano.

É possível generalizar esse algoritmo para um grafo que tem mais de dois vértices de grau ímpar. Mas isso requer alguns conceitos que serão vistos mais tarde.


Ciclo hamiltoniano e grafo hamiltoniano

Um caminho que passa exatamente uma vez por cada vértice de um grafo é chamado hamiltoniano. Se o caminho começa e termina no mesmo vértice, temos um ciclo hamiltoniano. Um grafo que contém um ciclo hamiltoniano é um grafo hamiltoniano.

Evidentemente, nem todo grafo é hamiltioniano. O grafo da figura 6a é hamiltoniano, enquanto que o da figura 6b não é.

Figura 6

Agora, a questão é a seguinte. Quais são as condições necessárias e suficientes para determinar se um grafo é hamiltoniano? Ou, en outras palavras, existe um algoritmo eficiente para determinar se um grafo é hamiltoniano? Infelizmente, ao contrário do caso dos grafos eulerianos, que a primeira vista parece semelhante, não sabemos responder a essa pergunta. Pior que isso, tem muita chance de que não exista tal algoritmo, pois isso é um problema NP-Completo. Intuitivamente, isto significa que podemos verificar em tempo polinomial se temos uma solução, mas não podemos produzir uma solução em tempo polinomial. Já foi demonstrado que se existe um algoritmo polinomial para um problema da classe dos problemas NP-Completos, existe um algoritmo polinomial para todos os problemas da classe. Na classe dos problemas NP-Completos, encontramos vários problemas cruciais e que foram muito estudados. Como até agora não encontramos um algoritmo eficiente para nenhum, podemos suspeitar que tal algoritmo não existe.

Não existe um algoritmo eficiente para determinar, no caso geral, se um grafo é hamiltoniano. Mas em certos casos específicos, a tarefa é mais factível.

Ciclo hamiltoniano em grafos completos

Não é muito complicado ver que todo grafo completo que contém mais de dois vértices é um grafo hamiltioniano. Seja v1, v2...vn os vértices de G. Como existe uma aresta entre qualquer par de vértices, é possivel, à partir de v1, percorrer essa seqüência até vn e voltar a v1.

Propriedades dos grafos hamiltonianos

Infelizmente, há poucos teoremas realmente úteis sobre os grafos hamiltonianos. Eis dois teoremas:

Teorema 2-3: (Teorema de Ore) Uma condição suficiente (mas não necessária) para que um grafo G seja hamiltoniano é que a soma dos graus de cada par de vértices não-adjacentes seja no mínimo n.

Teorema 2-4: (Teorema de Dirac) Uma condição suficiente (mas não necessária) para que um grafo G seja hamiltoniano é que o grau de todo vértice de G seja no mínimo n/2, onde n é o número de vértices em G.

Esses teoremas deixam muito a desejar, por várias razões. Primeiro, eles não são suficientes para determinar se um grafo é hamiltoniano. O grafo da figura 7, por exemplo, é hamiltoniano e não respeita a condição do teorema 2-4. O grau de cada vértice é 2, o que é menor que 6/2 = 3.

Figura 7

Segundo, esses teoremas não são muito informativos. O que eles dizem, intuitivamente, é que se um grafo contém muitas arestas e que elas são bem distribuidas, ele é hamiltoniano. No limite, temos um grafo completo.

O teorema 2-3 é mais forte que o teorema 2-4, no sentido que ele permite identificar mais grafos hamiltonianos. O problema com esse teorema, e outros que foram propostos, é que demora muito para efetuar o cálculo. Temos que efetuar uma soma (ou testar a adjacência) para cada par de vértices. Já sabemos que o número de pares de vértices é n(n-1)/2. Portanto, o tempo é O(n2). Como o grafo tem bastante arestas, uma busca com tentativas e erros pode ser mais eficiente em vários casos.

Problema do caixeiro viajante

Seja um grafo completo G, tal que cada aresta a possui um peso c(a) 0. O problema do caixeiro viajante consiste em procurar um ciclo hamiltoniano em G de maneira a minimizar a soma dos pesos das arestas que compõem o ciclo. Esse problema também é NP-completo.

Exercícios