Teoria dos Grafos

Valeriano A. de OliveiraSocorro Rangel

Departamento de Matemtica Aplicadaantunes@ibilce.unesp.br, socorro@ibilce.unesp.br

Grafos Hamiltonianos

Preparado a partir do texto:Rangel, Socorro. Teoria do Grafos, Notas de aula, IBILCE, Unesp, 2002-2013.

Grafos Hamiltonianos

Grafos Hamiltonianos O Problema do Caixeiro Viajante Digrafos Hamiltonianos

IntroduoGrafos Hamiltonianos O Problema do Caixeiro Viajante Digrafos Hamiltonianos

Teoria dos Grafos 3

Um trajeto euleriano caracterizado pelo fato de incluir todas as arestasde um dado grafo, uma nica vez.

Entretanto os vrtices podem se repetir em um trajeto euleriano. Surgeento a questo da possibilidade de se obter um trajeto fechado (nonecessariamente euleriano) que inclua cada vrtice uma nica vez1; comopor exemplo, nos grafos exibidos a seguir.

1Neste caso o trajeto um circuito com n arestas.

DefiniesGrafos Hamiltonianos O Problema do Caixeiro Viajante Digrafos Hamiltonianos

Teoria dos Grafos 4

Definio 1. Um circuito hamiltoniano em um grafo conexo umcircuito que contm todos os vrtices do grafo.

Um grafo chamado de grafo hamiltoniano se possui um circuitohamiltoniano.

Um grafo no-hamiltoniano semi-hamiltoniano se possui umcaminho que contm todos os seus vrtices (caminho hamiltoniano)

Exemplos:

Grafos Hamiltonianos O Problema do Caixeiro Viajante Digrafos Hamiltonianos

Teoria dos Grafos 5

Os grafos abaixo no so hamiltonianos. Por que?

Quais so as condies necessrias e suficientes para definir se um grafo hamiltoniano?

Grafos Hamiltonianos O Problema do Caixeiro Viajante Digrafos Hamiltonianos

Teoria dos Grafos 6

Esta uma questo em aberto e foi formulada pelo matemtico SirWilliam Hamilton em 1859.

Grafos Hamiltonianos O Problema do Caixeiro Viajante Digrafos Hamiltonianos

Teoria dos Grafos 7

Algumas consideraes podem ser feitas:

1. Arestas paralelas e laos no podem pertencer a um circuitohamiltoniano.

2. Se um vrtice possui grau 2, as arestas a ele incidentes devempertencer ao circuito hamiltoniano.

3. Nenhum subcircuito prprio, isto , um circuito que no possuitodos os vrtices de G, pode ser formado durante a construo docircuito hamiltoniano.

4. Um vez includo um vrtice, todas as arestas a ele incidentes e queno foram inseridas no circuito podem ser desconsideradas.

ExerccioGrafos Hamiltonianos O Problema do Caixeiro Viajante Digrafos Hamiltonianos

Teoria dos Grafos 8

Verificar se o grafo abaixo hamiltoniano:

Grafos Hamiltonianos O Problema do Caixeiro Viajante Digrafos Hamiltonianos

Teoria dos Grafos 9

Para que tipo de grafo podemos garantir a existncia de um circuitohamiltoniano?

Definio 2. Um Grafo Completo um grafo simples tal que existeuma aresta entre cada par de vrtices.

Um grafo completo com n vrtices denotado por Kn.

Exemplos:

Grafos Hamiltonianos O Problema do Caixeiro Viajante Digrafos Hamiltonianos

Teoria dos Grafos 10

Como obter um circuito hamiltoniano em um grafo completo Kn, comn 3?

Numere os vrtices do grafo de 1 a n. Como existe uma aresta entrecada par de vrtices, a sequncia 1, 2, . . . , n um circuito hamiltoniano.

Quantos circuitos hamiltonianos um grafo completo possui? Vamosexaminar o K4:

Os circuitos {a, b, c, d, a} e {a, d, c, b, a} so diferentes ou iguais?

Grafos Hamiltonianos O Problema do Caixeiro Viajante Digrafos Hamiltonianos

Teoria dos Grafos 11

Partindo do vrtices 1, temos n 1 escolhas de arestas para fazer.

Em seguida, a partir do vrtice 2, temos n 2 arestas para escolher;

e assim por diante at a escolha da ltima aresta.

Ou seja, h (n 1)! possibilidades; e se considerarmos que circuitos dotipo {vi1 , vi2 , . . . , vin , vi1} so iguais ao circuito{vi1 , vin , vin1, . . . , vi2 , vi1}, teremos que o nmero total de circuitos dado por (n 1)!/2.

Teorema 3. Em um grafo completo com n vrtices existem (n 1)/2circuitos hamiltonianos aresta-disjuntos, se n 3 mpar.

Demonstrao. Exerccio.

Condio necessria e suficiente?Grafos Hamiltonianos O Problema do Caixeiro Viajante Digrafos Hamiltonianos

Teoria dos Grafos 12

No caso de grafos eulerianos temos uma condio necessria e suficientefacilmente verificvel.

Porm, para grafos hamiltonianos no h. Na verdade, sabe-se pouco emgeral sobre grafos hamiltonianos.

A maioria dos teoremas so da forma: Se G possui arestas suficientes,ento G hamiltoniano.

Os dois teoremas mais celebrados esto enunciados a seguir.

Teorema de Ore (1960)Grafos Hamiltonianos O Problema do Caixeiro Viajante Digrafos Hamiltonianos

Teoria dos Grafos 13

Teorema 4. Se G(V,A) um grafo simples com n 3 vrtices, e se

d(v) + d(w) n

para cada par de vrtices no-adjacentes v e w, ento G hamiltoniano.

Demonstrao: Procederemos por contradio. Suponha que G no hamiltoniano, mas satisfaz a hiptese.

Vamos supor ainda que G quase hamiltoniano, no sentido de que aadio de qualquer outra aresta torna-o hamiltoniano.

Se este no for o caso, adicionamos arestas extras at que o seja.

Observe que a adio de arestas no quebra a hiptese.

Grafos Hamiltonianos O Problema do Caixeiro Viajante Digrafos Hamiltonianos

Teoria dos Grafos 14

Sejam v, w V vrtices no-adjacentes (existe pelo menos um par, casocontrrio, G seria completo e, por conseguinte, hamiltoniano).

Logo, a adio da aresta (v, w) torna G hamiltoniano, o que implica naexistncia de um caminho passando por todos os vrtices:

v = v1 v2 vn = w.

v1v2

vi-1 vi

vn-1 vn

..

..

..

Grafos Hamiltonianos O Problema do Caixeiro Viajante Digrafos Hamiltonianos

Teoria dos Grafos 15

Por hiptese, d(v1) + d(vn) n, ou seja existe um conjunto E com aomenos outras n 2 aretas incidentes em {v1, vn}.

Logo, existem vrtices vi e vi1 tais que vi adjacente a v1 e vi1 adjacente a vn. De fato, se todas as arestas de E incidem, digamos, emv1, teramos ao menos um par de arestas paralelas, contradizendo o fatode G ser simples. Similarmente se todas incidem em vn. Veja a figura.

v1v2

vi-1 vi

vn-1 vn

..

..

..

n novas arestas

Grafos Hamiltonianos O Problema do Caixeiro Viajante Digrafos Hamiltonianos

Teoria dos Grafos 16

v1v2

vi-1 vi

vn-1 vn

..

..

..

Mas neste caso, temos um circuito hamiltoniano:

v1 v2 vi1 vn vn1 vi+1 vi v1,

em contradio suposio de que G no hamiltoniano.

Teorema de Dirac (1952)Grafos Hamiltonianos O Problema do Caixeiro Viajante Digrafos Hamiltonianos

Teoria dos Grafos 17

Teorema 5. Se G um grafo simples com n 3 vrtices, e se

d(v) n

2

para cada vrtice v, ento G hamiltoniano.

Demonstrao. Temos que

d(v) + d(w) n

2+

2

2= n

para cada par de vrtices v e w (adjacentes ou no-adjacentes). Seguedo Teorema de Ore que G hamiltoniano.

ExerccioGrafos Hamiltonianos O Problema do Caixeiro Viajante Digrafos Hamiltonianos

Teoria dos Grafos 18

Verificar os dois teoremas atravs dos seguintes grafos:

Condio NecessriaGrafos Hamiltonianos O Problema do Caixeiro Viajante Digrafos Hamiltonianos

Teoria dos Grafos 19

Teorema 6. Se G(V,A) um grafo hamiltoniano, ento para todosubconjunto no-vazio, S V , o grafo G S possui no mximo |S|componentes.

Demonstrao. Seja C um ciclo hamiltoniano de G. Ao percorrer asarestas de C, quando passamos por um componente de G, ao deixar estecomponente temos, necessariamente, que passar por algum vrtice de S.

A cada passagem por um componente de G temos que usar um vrticediferente de S ao deixarmos o componente.

Consequentemente, a quantidade de vrtices de S deve ser maior ouigual ao nmero de componentes de G.

ExemplosGrafos Hamiltonianos O Problema do Caixeiro Viajante Digrafos Hamiltonianos

Teoria dos Grafos 20

O Problema do Caixeiro

Viajante

Grafos Hamiltonianos O Problema do Caixeiro Viajante Digrafos Hamiltonianos

Colocao do ProblemaGrafos Hamiltonianos O Problema do Caixeiro Viajante Digrafos Hamiltonianos

Teoria dos Grafos 22

Um viajante necessita visitar um certo nmero de cidadesdurante uma viagem e retornar ao lugar de origem de talmaneira que cada cidade visitada exatamente uma vez e quea distncia total percorrida seja a menor possvel. Dada edistncia entre as cidades, que rota ele deve escolher?

Como resolver este problema?

Vamos representar o problema acima atravs de um grafo valorado. SejaV o conjunto de cidades, A o conjunto das estradas interligando ascidades e o valor de cada aresta como sendo a distncia entre asrespectivas cidades.

Grafos Hamiltonianos O Problema do Caixeiro Viajante Digrafos Hamiltonianos

Teoria dos Grafos 23

Vamos supor que o viajante deseja visitar 5 cidades cujas estradasexistentes entre cada par de cidade estejam representadas atravs doseguinte grafo:

Em princpio, este problema pode ser resolvido determinando-se todas asrotas possveis e escolhendo a que resultar na menor distncia percorrida.Neste exemplo, uma possvel rota dada por: {A,B,C,D,E,A} cujadistncia 5 + 2 + 4 + 3 + 4 = 18km.

A rota tima : {A,C,B,D,E,A} cuja distncia 14km.

Grafos Hamiltonianos O Problema do Caixeiro Viajante Digrafos Hamiltonianos

Teoria dos Grafos 24

Esta tcnica eficiente?

Considere que o problema que envolva 10 cidades.

O nmero mximo de possveis rotas seria de 9