Grafos Hamiltonianos e Eulerianos
Por Igor Cruz
(igor.cruz@ccc.ufcg.eu.br)
A teoria dos grafos é uma área da matemática que estuda as relações entre os objetos de um conjunto. Diversas aplicações podem ser representadas com grafos, como por exemplo, o caminho que o carteiro percorrerá para visitar todas as casas aonde ele deve entregar correspondências. Assim, vamos relembrar um pouco sobre esse assunto e resolver uma questão do POSCOMP 2013!


Um grafo, G (V, A), é constituído por um conjunto de vértices (V) ligados por arestas (A). De acordo com a aplicação desejada, as arestas podem ter direção e para esse tipo de grafo damos o nome de dígrafo. Além disso, existem tipos especiais de grafos, como por exemplo, os grafos hamiltonianos e eulerianos, descritos a seguir.

  • Grafos Eulerianos: Grafo no qual é possível caminhar por todas as suas arestas, visitando cada uma delas apenas uma única vez, formando um ciclo (ciclo euleriano).

  • Caminho Euleriano: É um caminho, em um grafo, que visita cada aresta apenas uma vez, não necessariamente gerando um ciclo.

    • O grafo G é euleriano, já que contém o ciclo euleriano: (u1, u2), (u2, u3),(u3, u4), (u4,u5), (u5, u3), (u3, u1), (u1, u6), (u6, u2), (u2, u7), (u7, u3), (u3, u6), (u6, u7), (u7, u1)


  • Grafos Hamiltonianos: Grafo no qual é possível caminhar por todos os seus vértices, visitando cada um deles apenas uma única vez, formando um ciclo (ciclo hamiltoniano).

    • O grafo G1 é hamiltoniano, já que possui o ciclo: v1, v2, v3, v4, v5 que é hamiltoniano.

Vamos agora resolver a questão abaixo do POSCOMP 2013, sobre grafos eulerianos!

Resolvendo a questão:

  • No primeiro grafo, conseguimos ver claramente que é possível criar um ciclo euleriano, assim ele é euleriano e admite caminho euleriano;

  • No II, a complexidade é um pouco maior, porém se partirmos da aresta mais a direita, depois explorarmos o centro e, por fim, a aresta mais a esquerda, conseguimos gerar um caminho euleriano com sucesso. Observe a imagem ao lado para um melhor entendimento (os números significam a ordem das arestas a se percorrer);

  • Apesar de não conseguirmos gerar um ciclo euleriano no grafo III, é possível caminhar por todas as arestas somente uma vez, logo ele admite caminho euleriano.

  • O último grafo (grafo IV) é o único que não admite caminho euleriano, já que independente de por qual aresta começarmos a caminhar, nunca conseguiremos caminhar por todo o grafo, sempre ficará faltando uma aresta a ser consumida.

  • Logo a resposta correta é a letra d.

Referências:

Jornal PETNews - Edição: Rafael Rêgo - Revisão: Lívia Sampaio
Grupo PET Computação UFCG, 2013. All rights reserved.