Grafos Hamiltonianos

Prévia do material em texto

Grafos Hamiltonianos
� Aparentemente o problema de decidir se um grafo é
hamiltoniano parece muito semelhante ao problema 
de decidir se um grafo é eureliano, e gostariamos de 
poder conseguir condições necessárias e suficientes 
para isso como no caso dos grafos eurelianos.
� Infelizmente só temos condições parciais para o 
problema de decidir se um grafo é hamiltoniano.
*A igualdade aconte quando S é
formado por vértices não consecutivos
Temos também que: (C – S) é um subgrafo de (G – S), logo:
Teorema 1: Se G é hamiltoniano, então para cada
subconjunto não vazio S de V, temos:
*Pois a introdução de arestas não pode aumentar o núm. de componentes conexos de um grafo
. Temos então, 
Prova: Seja G hamiltoniano, logo G possui um ciclo hamiltoniano
C. Então, para todo S , tal que S é um subconjunto de V, S ≠ ø , 
temos:
Grafos Hamiltonianos-(condições necessárias)
Observe que essa condição é necessária, porém não suficiente. 
Exemplo:
Esse grafo não é hamiltoniano, mas satisfaz a condição do 
teorema.
Grafos Hamiltonianos
Observação: A condição é necessária mas não suficiente.
Teorema 2: Se G é hamiltoniano, então G é biconexo
(em vértices).
Prova: Se G é hamiltoniano, então G possui um ciclo
hamiltoniano C, que contém todos os vértices de G, ou seja, todo
vértice de G está no ciclo C, o que garante a existência de dois
caminhos disjuntos entre cada par de vértices.
Grafos Hamiltonianos-(condições necessárias)
Grafos Hamiltonianos
� Note que Cn (ciclo com n vértices) é sempre 
hamiltoniano. Observe o caso do C5.
a b c d e a é um 
ciclo hamiltoniano de C5.
� Se acrescentássemos mais arestas ao grafo C5, ele 
deixaria de ser hamiltoniano? Vamos raciocinar...
Grafos Hamiltonianos
Acrescentando a aresta (a,c).
� Neste caso, continuamos 
tendo o ciclo hamiltoniano
a b c d e a. Logo, C5 + {(a,c)} 
é hamiltoniano.
� Acrescentando 
as arestas (a,c) e (a,d).
Ainda continuamos tendo o 
mesmo ciclo hamiltoniano.
Grafos Hamiltonianos
� Tornando C5 no grafo completo K5.
Podemos obter os ciclos hamiltonianos:
a b c d e a
a e d b c a
� Observamos que se temos um grafo hamiltoniano e, 
se adicionarmos mais arestas a ele, então o grafos 
obtido também será hamiltoniano.
� Grafos com muitas arestas têm mais chance de serem 
hamiltonianos. 
.
.
.
Grafos Hamiltonianos
(condicões suficientes)
Teorema 3 (Dirac): Seja G 
um grafo com n vértices,
n ≥ 3. Se d(v) ≥ n/2 para 
todo vértice v de G, então 
G é hamiltoniano.
Grafos Hamiltonianos
(condições suficientes)
Teorema 4 (Ore): Seja G um 
grafo com n vértices, n ≥
3. Se d(v)+d(w)≥ n para 
todo par de vértices v e w
não adjacentes de G, então 
G é hamiltoniano.
Grafos Hamiltonianos
(condições suficientes)
Teorema 5:(Bondy and Chvátal) 
Sejam G um grafo com n 
vértices e u,v dois vértices 
distintos e não adjacentes de 
G tais que d(u)+d(v) ≥ n. G é
hamiltoniano se e somente se 
G +(u,v) é hamiltoniano.
Grafos Hamiltonianos
� Ilustração dos teoremas:
n=6 e o grafo é 3-regular.
Logo o grafo ao lado é hamiltoniano pelo 
teorema 3 de Dirac.
n=5 
O teorema de Dirac NÃO é satisfeito.
Mas d(a) + d(c) = 6 > 5 e
d(b) + d(e) = d(b) + d(d) = 5 = n
Logo, o grafo é hamiltoniano pelo 
teorema 5.
Grafos Hamiltonianos
� Mas como já foi dito, essas condições são suficientes mas 
não necessárias. Observe que C5 é hamiltoniano mas não 
satisfaz as condições de Dirac e nem de Bondy-Chvátal.
� O Teorema 5 nos motiva a seguinte definição.
� O fecho de um grafo é o grafo obtido por sucessivas 
adições de arestas que unem vértices não adjacentes do 
grafo cuja soma dos graus é no mínimo n, até que não 
haja pares remanescentes.
� Denotamos o fecho de um grafo G por c(G).
Grafos Hamiltonianos
� Observe a construção do fecho de um grafo com 6 
vértices.
Grafos Hamiltonianos
� Observe a construção do fecho de um grafo com 6 
vértices.
Grafos Hamiltonianos
� Observe a construção do fecho de um grafo com 6 
vértices.
Grafos Hamiltonianos
� Observe a construção do fecho de um grafo com 6 
vértices.
Grafos Hamiltonianos
� Observe a construção do fecho de um grafo com 6 
vértices.
Grafos Hamiltonianos
� Observe a construção do fecho de um grafo com 6 
vértices.
Grafos Hamiltonianos
� Observe a construção do fecho de um grafo com 6 
vértices.
Grafos Hamiltonianos
� Observe a construção do fecho de um grafo com 6 
vértices.
Grafos Hamiltonianos
Teorema 6.Um grafo G é hamiltoniano
se e somente se c(G) é hamiltoniano
Prova:
Basta aplicar o Teorema 5 (Bondy e Chvatal) cada vez que 
uma aresta é adicionada ao fecho de G.
Grafos Hamiltonianos
Corolário 6. Seja G um grafo 
(simples) com pelo menos 3 
vértices.Se c(G) é completo então 
G é hamiltoniano.
Observação: 
Como c(G) é claramente completo quando δ≥n/2. 
então o Teorema 4 (Dirac) é um corolário imediato do
Corolário 6.