Grafos Eulerianos e Hamiltonianos

Apresentação baseada nas notas de Aula do Professor Pedro Noia

<http://w.pedronoia.net/ResumoAss5111.htm> e dos professores Silvio A. de Araujo e Socorro Rangel <http://w.ibilce.unesp.br/Home/Departamentos/MatematicaAplicada/docentes/cnmac20 14---aula02a.pdf>

Campus - Mossoró Profª Adricia Fonseca Mendes

Definições

Caminhos que usam todos os vértices ou todas as arestas de um grafo são geralmente chamados de percursos;

Uma grande variedade de problemas práticos podem ser vistos como um percurso num grafo;

Eles se dividem em duas categorias:

o Problemas do tipo euleriano o Problemas do tipo hamiltoniano

Problemas eulerianos x problemas hamiltonianos o A maior parte dos problemas eulerianos são resolvidos em tempo polinomial o A maioria dos problemas hamiltonianos têm uma solução de custo elevado e são classificados como NP-difícil, é necessário a utilização de técnicas aproximativas para se obter um resultado em tempo hábil.

Algorítimos heurísticos

Vantagens oAmpla aplicabilidade; oConsumo de tempo computacional muitas vezes menor do que um algoritmo exato.

Desvantagens oNão são capazes de garantir a otimalidade ou até, em muitos casos, de estabelecer quão perto uma dada solução viável está da solução ótima.

Principais classes de algoritmos heurísticos oHeurística de Construção; oHeurística de Melhoramento; oHeurística mista.

Definições

•Um grafo G é um par (V, A), em que V é o conjunto de vértices e A o conjunto de arestas.

•Uma aresta liga um vértice a outro ou a ele próprio.

•Ordem de um grafo: Representa o número de vértices de um grafo.

•Um grafo é conexo quando qualquer vértice está ligado por uma aresta ou por uma sequência de arestas a qualquer um dos outros vértices do grafo

Grau dos vértices 7

Problemas Eulerianos Requerem que cada aresta seja percorrida uma única vez!

Exemplo – Trajeto Euleriano e Circuito Euleriano

Mostre que a Figura a) trata-se de um trajeto Euleriano e a Figura b) de um circuito Euleriano.

Figura a) Exemplo de trajeto Euleriano Figura b) Exemplo de circuito Euleriano 9

Exercício 10

Existem outras possibilidades. Teste por exemplo iniciar e terminar em A! 1

Problema do Carteiro Chinês e o circuito de Euler

Variações do problema do carteiro chinês aparecem em diversas aplicações:

oColeta de lixo; oLimpeza das ruas; oPintura de linhas no centro das ruas; oPatrulhamento da polícia; oPesquisa de opinião e recenseamento; oPlotagem de uma rede.

Exemplo - Eulerização de Grafos

Eulerizar um grafo consiste em acrescentar-lhe arestas, por repetição, até obter um circuito euleriano. Para eulerizar, basta duplicar as arestas que formam o caminho mais curto entre os dois vértices de grau ímpar. No exemplo, para eulerizar o primeiro grafo, basta duplicar a aresta [AC].

Exemplo - Eulerização de Grafos 19

Problemas Hamiltonianos

Requerem que todos os vértices sejam percorridos uma única vez, com exceção do vértice de partida!

No exemplo abaixo, o objetivo é partir do ponto C, passar por todos os outros pontos uma única vez e voltar ao ponto inicial.

Exemplo - Problemas Hamiltonianos 2

Exercício - Problemas Hamiltonianos Resolvido em sala!

Problemas Hamiltonianos – Caixeiro Viajante

Exemplo - Caixeiro Viajante 26

Exemplo - Caixeiro Viajante 27

28 2° Exemplo - Caixeiro Viajante

29 2° Exemplo - Caixeiro Viajante

30 2° Exemplo - Caixeiro Viajante

31 2° Exemplo - Caixeiro Viajante

32 2° Exemplo - Caixeiro Viajante

3 2° Exemplo - Caixeiro Viajante

34 2° Exemplo - Caixeiro Viajante

35 2° Exemplo - Caixeiro Viajante

36 2° Exemplo - Caixeiro Viajante

Comentários