Trabalho

fIntrodu¸ao ` Teoria dos Grafos (MAC-5770) – IME-USP – Depto CC – Profa. Yoshiko c˜ a

Cap´ ıtulo 4 Grafos Hamiltonianos
PROBLEMA: “Volta ao redor do mundo” ´ E poss´vel achar um trajeto, passando ao longo das arestas do dodecaedro (Figura 2), que visita cada ı uma das cidades exatamente uma vez e termina na cidade de partida? [Brinquedos constru´ ıdos por William Hamilton, 1856 (Figura 1): vers˜o 3-dimensional e vers˜o planar.] a a

Figura 1 - William R. Hamilton

Figura 2 - Dodecaedro com nomes de 20 cidades

Figura 3 - Vers˜o planar a

1

Defini¸˜o. Um circuito (resp. caminho) que cont´m todos os v´rtices de um grafo ´ chamado ca e e e hamiltoniano. Um grafo hamiltoniano ´ um grafo que cont´m um circuito hamiltoniano. e e Problema 1: Dado um grafo G, decidir se G ´ hamiltoniano. e

Problema 2: Dado um grafo hamiltoniano G, encontrar um circuito hamiltoniano. Os problemas acima s˜o dif´ a ıceis! (O Problema 1 ´ NP-completo.) N˜o se conhece algoritmos e a polinomiais para se resolvˆ-los. e Teorema 4.1 (Condi¸˜o necess´ria para um grafo ser hamiltoniano) ca a Se G ´ um grafo hamiltoniano ent˜o para todo conjunto n˜o-vazio S ⊂ V (G), e a a c(G − S) ≤ |S|.

Condi¸˜es suficientes para um grafo ser hamiltoniano co
Teorema 4.2. (Dirac, 1952) Se G ´ um grafo simples de ordem n ≥ 3 e g(v) ≥ n/2 para todo v ∈ V (G), ent˜o G ´ e a e hamiltoniano. Prova 1. Suponha que a afirmac˜o seja falsa. Ent˜o existe um grafo simples n˜o-hamiltoniano a a a maximal G de ordem n ≥ 3 que satisfaz a condi¸˜o do teorema. Ou seja, (maximal no sentido de ca que) G ´ n˜o-hamiltoniano, mas para qualquer par de v´rtices n˜o-adjacentes u, v em G, temos e a e a que o grafo G + uv ´ hamiltoniano. e Claramente G n˜o ´ completo (todo grafo completo com pelo menos 3 v´rtices ´ obviamente a e e e hamiltoniano). Portanto, existem v´rtices u e v n˜o-adjacentes em G. Considere o grafo H := e a G + uv. Pela maximalidade de G, segue que H ´ hamiltoniano. Logo, todo circuito hamiltoniano e em H