Teoria dos Grafos - Grafos Eulerianos e Hamiltonianos

---

Grafos Eulerianos

Definição

Um grafo conexo G é Euleriano se existir uma trilha fechada que inclua todas as arestas de G.
Esta trilha é chamada de Trilha Euleriana
  Trilha Euleriana: { A, B, C, D, E, C, G, F, E, G, B, F, A }
Portanto G é um Grafo Euleriano.

Teorema 1: Um Grafo conexo G é Euleriano sse cada vértice de G possui grau par

Prova:
 
Parte I () . { "A ida": Se um grafo conexo G é Euleriano então cada vértice de G possui grau par}
 
// G  é Euleriano v VG , Gr(v) é par.

Tomemos  um grafo euleriano G.
Seja T uma trilha euleriana de G com origem em u.
Seja  v um vértice qualquer de T
 

Caso 1:  v  u { Todos os vértices internos da trilha tem grau par }
 

Em cada ocorrência de v em T, duas arestas distintas incidem em v.
Logo, contribuem com 2 para o grau de v
Como todas as arestas de G, estão em T, Gr(v) é par.
Caso 2:   v = u
 
Como todos os outros vértices de G tem grau par , e a quantidade de vértices com grau ímpar em um grafo qualquer não pode ser  ímpar, temos que Gr(v) é par.
Temos então que v VG , Gr(v) é par.
Parte II ().{ "A volta": Se cada vértice de um grafo conexo G possui grau par então G é Euleriano}
 
// v VG , Gr(v) é par  G é euleriano

Provemos por Indução no número de arestas (m).

Base : (m=0)
 

G é o grafo trivial, e portanto. a trilha degenerada, que começa e termina no único vértice v de G, é uma trilha euleriana. {Ela passa por todas as 0 arestas de G}
Hipótese de Indução:
Para todo grafo G conexo com k< m arestas, onde todos os vértices tem grau par, temos que G é euleriano. {Assumo que "a volta do teorema" vale para todos os grafos onde a quantidade de arestas é menor que um m qualquer. (Indução Forte)}
 Passo: (m>0) {Aqui eu provo que quando o teorema vale para todos os grafos com menos de m entao ele vale para m}
 
Como todo vértice tem grau par, temos que G não é uma árvore  e portanto possui um ciclo induzido C.
Seja H = G \{Arestas de C} {"Imaginar" G sem as arestas do ciclo C}
O grafo H pode ser eventualmente desconexo.
Seja H' um componente conexo de H.
Observando que cada vértice de H' tem grau par*, |AH| < m** e H' é conexo, podemos aplicar a Hipótese de Indução, e concluir que existe uma trilha  euleriana em H'. {H' satisfaz todas as 3 condições da hipótese de indução}

Portanto, existe uma trilha  euleriana em  G, que pode ser encontrada  aplicando-se o seguinte algoritmo:

1. Inicie em algum vértice u de C
2. Caminhe em C até encontrar algum vértice v pertencente a algum componente H'
3. Caminhe pela Trilha Euleriana de H' até voltar a v
4. Repita 2 e 3 até encontrar o vértice inicial u.
* Retirando as arestas do ciclo eu retiro de cada vértice duas aretas diferentes, como antes o grau do vertice era par ele continua sendo par.
** O ciclo tem pelo menor uma aresta.

Problema do Dominó

É possível com as pedras de um Jogo de Dominó formar um anel ( Seguindo as regras do Jogo ).

Representação do Problema usando Teoria dos Grafos:

Seja G um grafo onde
VG = { 0 , 1 , 2 , 3 , 4 , 5 , 6 } // Números que aparecem nas pedras do dominó.
AG = { (0,0) , (0,1) , ... , (0,6) , (1,1) , (1,2) , ... , (1,6) , (2,2) , ... , (6,6) } // Peças do dominó.
Problema: G é Euleriano ?
Resposta: O Grafo G é um grafo completo, com 7 vértices, acrescido de um laço em cada vértice, e portanto, todos os vértices de G tem grau 8 ( Par ). Logo, pelo teorema 1, G é Euleriano.

Problema do Explorador

Problema:
Um explorador deseja conhecer todas as estradas entre algumas cidades. É possível encontrar um passeio que use cada estrada  exatamente uma vez e retorne ao ponto de partida.
Solução no Domínio de Teoria dos Grafos:
Representando cada cidade por um vértice e cada estrada por uma aresta, o problema passa a ser decidir se o grafo é ou não Euleriando

Grafos Hamiltonianos

Definição

Um grafo G conexo é Hamiltoniano se existir um ciclo que inclui todo vértice de G. Tal ciclo é dito Ciclo Hamiltoniano.
 

O Dodecaedro é Hamiltoniano pois existe um ciclo que  passa por todos os vértices (Lembre-se que num ciclo  apenas o primeiro vértice se repete)

Outros exemplos: Grafos Ciclo, Kn , Platônicos ( Cubo, Tetraedro, Octaedro, Dodecaedro, Icosaedro ),

Condicões suficientes para G ser Hamiltoniano (Não se conhece ainda condições, não triviais, necessárias e suficientes, que caracterize um grafo Hamiltoniano)

Condição de Dirac - 1952

Seja G um grafo simples com n3 vértices.
Se gr(v) n/2,   v VG então G é Hamiltoniano

Exemplos:
 

{ O numero de vértices tem que ser maior igual a 3, e os graus maiores ou iguais a n/2}

Condição de Ore - 1960

Se gr(u) + gr(v) n para todo u,v não adjacente, então G é Hamiltoniano.
Exemplo:
 

n=5 (vértices) 2 + 5n (soma dos graus) 2 + 4n 1 + 3 n É hamiltoniano

{ Para cada par não adjacente a soma dos graus deve ser maior ou igual a n }

Note que o grafo acima não satisfaz a condição de Dirac.

Exercício: Provar que a condição de Ore engloba a condição de Dirac ( A condição de Dirac é uma consequência da condição de Ore)

Condição de Bondy e Chvata - 1974

Definição Auxiliar

O Fecho de G, F(G), é o grafo obtido acrescentando-se arestas entre pares de vértices não adjacentes cuja soma dos graus é n, até que tais pares de vértices não mais existam.
  n=6

Exceção:

O Grafo abaixo não satisfaz as condições de Bondy e Chvata, Ore, Dirack, mas é um grafo hamiltoniano, porque
possui um ciclo hamiltoniano
 

Grafo G	Fecho de G

Considerações:

• Pela condição de Dirac, ele seria hamiltoniano se Gr(v)n/2, com n 3, o exemplo acima não satisfaz esta condicao, visto que n=6, o grau dos vértices teria de ser 3,  o que não acontece no exemplo acima pois todos os vértices possuem grau 2
• Pela condição de Ore, a soma dos graus de vértices não adjacentes deveria ser  número de vértices, o que não acontece no exemplo acima, todos os pares de vértices não adjacentes possuem a soma de seus graus igual a 4, e o grafo possui 6 vértices, o que não respeita a condição
• Pela condição de Bondy e Chvata o fecho do grafo teria de ser um grafo completo, o que não acontece no grafo acima.

Embora todas estas considerações não podemos afirmar que o grafo não é hamiltoniano, porque não satisfaz nenhuma destas condições.
O grafo é hamiltoniano, pois possui um ciclo hamiltoniano

Teorema: Um grafo simples  é Hamiltoniano sse F(G) é Hamiltoniano

Se F(G) é completo então G é Hamiltoniano.

Exercício: Provar que um Grafo completo é hamiltoniano

 
Resolução:
 
*Grafo Completo: Existe aresta ligando cada par de vértice
*Grafo Hamiltoniano: Ciclo hamiltoniano
*Ciclo Hamiltoniano: um ciclo que inclui todos os vértices de G, repetindo apenas o primeiro vértice

Como em um grafo completo todos os vértices estão ligados entre si é possível, partindo de um vértice inicial v0 eu passar por todos os vértices e voltar ao vértice inicial v0, sem que haja repetição de vértices encontrando assim um ciclo hamiltoniano, e portanto o grafo é hamiltoniano.

Problema do Viajante

Problema:
Um viajante deseja visitar algumas cidades.
É possível encontrar um passeio que atravesse cada cidade exatamente uma vez e retorne a cidade inicial.

Representação em Teoria dos Grafos:

Representando cada cidade por um vértice e cada estrada por uma aresta
, problema passa a ser decidir se o grafo é ou não Hamiltoniano.

Problema do Caixeiro Viajante

Página de J. F. Porto da Silveira