Aula07_grafos

Prévia do material em texto

Teoria dos Grafos
Valeriano A. de Oliveira
So
orro Rangel
Silvio A. de Araujo
Departamento de Matemáti
a Apli
ada
antunes�ibil
e.unesp.br, so
orro�ibil
e.unesp.br, saraujo�ibil
e.unesp.br
AULA 7
Grafos Hamiltonianos
Preparado a partir do texto:
Rangel, So
orro. Teoria do Grafos, Notas de aula, IBILCE, Unesp, 2002-2013.
Grafos Hamiltonianos
Introdução
Teoria dos Grafos (Antunes Rangel&Araujo) � 3
Um trajeto euleriano é 
ara
terizado pelo fato de in
luir todas as arestas
de um dado grafo, uma úni
a vez.
Entretanto os vérti
es podem se repetir em um trajeto euleriano. Surge
então a questão da possibilidade de se obter um trajeto fe
hado (não
ne
essariamente euleriano) que in
lua 
ada vérti
e uma úni
a vez
1
; 
omo
por exemplo, nos grafos abaixo:
1
Neste 
aso o trajeto será, na verdade, um 
ir
uito (
om n arestas).
De�nições
Teoria dos Grafos (Antunes Rangel&Araujo) � 4
De�nição 1. Um 
ir
uito hamiltoniano em um grafo 
onexo é um
ir
uito que 
ontém todos os vérti
es do grafo.
Um grafo é 
hamado de grafo hamiltoniano se possui um 
ir
uito
hamiltoniano.
Um grafo não-hamiltoniano é semi-hamiltoniano se possui um
aminho que 
ontém todos os seus vérti
es.
Exemplos:
Teoria dos Grafos (Antunes Rangel&Araujo) � 5
Os grafos abaixo não são hamiltonianos. Por que?
Quais são as 
ondições ne
essárias e su�
ientes para de�nir se um grafo
é hamiltoniano?
Teoria dos Grafos (Antunes Rangel&Araujo) � 6
Esta é uma questão em aberto e foi formulada pelo matemáti
o Sir
William Hamilton em 1859.
Teoria dos Grafos (Antunes Rangel&Araujo) � 7
Algumas 
onsiderações podem ser feitas:
1. Arestas paralelas e laços não podem perten
er a um 
ir
uito
hamiltoniano.
2. Se um vérti
e possui grau 2, as arestas a ele in
identes devem
perten
er ao 
ir
uito hamiltoniano.
3. Nenhum sub
ir
uito próprio, isto é, um 
ir
uito que não possui
todos os vérti
es de G, pode ser formado durante a 
onstrução do
ir
uito hamiltoniano.
4. Um vez in
luído um vérti
e, todas as arestas a ele in
identes e que
não foram inseridas no 
ir
uito podem ser des
onsideradas.
Exer
í
io
Teoria dos Grafos (Antunes Rangel&Araujo) � 8
Veri�
ar se o grafo abaixo é hamiltoniano:
Condição ne
essária e su�
iente?
Teoria dos Grafos (Antunes Rangel&Araujo) � 9
No 
aso de grafos eulerianos temos uma 
ondição ne
essária e su�
iente.
Porém, para grafos hamiltonianos não há. Na verdade, sabe-se pou
o em
geral sobre grafos hamiltonianos.
A maioria dos teoremas são da forma: �Se G possui arestas su�
ientes,
então G é hamiltoniano�.
Os dois teoremas mais 
elebrados estão enun
iados a seguir.
Teorema de Ore (1960)
Teoria dos Grafos (Antunes Rangel&Araujo) � 10
Teorema 2. Se G(V,A) é um grafo simples 
om n ≥ 3 vérti
es, e se
d(v) + d(w) ≥ n
para 
ada par de vérti
es não-adja
entes v e w, então G é hamiltoniano.
Demonstração: Pro
ederemos por 
ontradição. Suponha que G não é
hamiltoniano, mas satisfaz a hipótese.
Vamos supor ainda que G é �quase hamiltoniano�, no sentido de que a
adição de qualquer outra aresta torna-o hamiltoniano.
Se este não for o 
aso, adi
ionamos arestas extras até que o seja.
Observe que a adição de arestas não quebra a hipótese.
Teoria dos Grafos (Antunes Rangel&Araujo) � 11
Sejam v, w ∈ V vérti
es não-adja
entes (existe pelo menos um par, 
aso
ontrário, G seria 
ompleto e, por 
onseguinte, hamiltoniano).
Logo, a adição da aresta (v, w) torna G hamiltoniano, o que impli
a na
existên
ia de um 
aminho passando por todos os vérti
es:
v = v1 → v2 → · · · → vn = w.
v1
v2
vi-1 vi
vn-1 vn
.
.
.
.
.
.
Teoria dos Grafos (Antunes Rangel&Araujo) � 12
Por hipótese, d(v1) + d(vn) ≥ n, ou seja existe um 
onjunto E 
om ao
menos outras n− 2 aretas in
identes em {v1, vn}.
Logo, existem vérti
es vi e vi−1 tais que vi é adja
ente a v1 e vi−1 é
adja
ente a vn. De fato, se todas as arestas de E in
idem, digamos, em
v1, teríamos ao menos um par de arestas paralelas, 
ontradizendo o fato
de G ser simples. Similarmente se todas in
idem em vn. Veja a �gura.
Teoria dos Grafos (Antunes Rangel&Araujo) � 12
Por hipótese, d(v1) + d(vn) ≥ n, ou seja existe um 
onjunto E 
om ao
menos outras n− 2 aretas in
identes em {v1, vn}.
Logo, existem vérti
es vi e vi−1 tais que vi é adja
ente a v1 e vi−1 é
adja
ente a vn. De fato, se todas as arestas de E in
idem, digamos, em
v1, teríamos ao menos um par de arestas paralelas, 
ontradizendo o fato
de G ser simples. Similarmente se todas in
idem em vn. Veja a �gura.
v1
v2
vi-1 vi
vn-1 vn
.
.
.
.
.
.
n-3 novas arestas
Teoria dos Grafos (Antunes Rangel&Araujo) � 13
v1
v2
vi-1 vi
vn-1 vn
.
.
.
.
.
.
Mas neste 
aso, temos um 
ir
uito hamiltoniano:
em 
ontradição à suposição de que não é hamiltoniano.
Teoria dos Grafos (Antunes Rangel&Araujo) � 13
v1
v2
vi-1 vi
vn-1 vn
.
.
.
.
.
.
Mas neste 
aso, temos um 
ir
uito hamiltoniano:
v1 → v2 → · · · → vi−1 → vn → vn−1 → · · · → vi+1 → vi → v1,
em 
ontradição à suposição de que G não é hamiltoniano. �
Teorema de Dira
 (1952)
Teoria dos Grafos (Antunes Rangel&Araujo) � 14
Teorema 3. Se G é um grafo simples 
om n ≥ 3 vérti
es, e se
d(v) ≥
n
2
para 
ada vérti
e v, então G é hamiltoniano.
Demonstração. Temos que
d(v) + d(w) ≥
n
2
+
2
2
= n
para 
ada par de vérti
es v e w (adja
entes ou não-adja
entes). Segue
do Teorema de Ore que G é hamiltoniano.
Exer
í
io
Teoria dos Grafos (Antunes Rangel&Araujo) � 15
Veri�
ar os dois teoremas através dos seguintes grafos:
Condição Ne
essária
Teoria dos Grafos (Antunes Rangel&Araujo) � 16
Teorema 4. Se G(V,A) é um grafo hamiltoniano, então para todo
sub
onjunto não-vazio, S ⊆ V , o grafo G− S possui no máximo |S|
omponentes.
Demonstração. Seja C um 
i
lo hamiltoniano de G. Ao per
orrer as
arestas de C, quando passamos por um 
omponente de G, ao deixar este
omponente temos, ne
essariamente, que passar por algum vérti
e de S.
A 
ada passagem por um 
omponente de G temos que usar um vérti
e
diferente de S ao deixarmos o 
omponente.
Consequentemente, a quantidade de vérti
es de S deve ser maior ou
igual ao número de 
omponentes de G.
Exemplos
Teoria dos Grafos (Antunes Rangel&Araujo) � 17
Teoria dos Grafos (Antunes Rangel&Araujo) � 18
Para que tipo de grafo podemos garantir a existên
ia de um 
ir
uito
hamiltoniano?
De�nição 5. Um Grafo Completo é um grafo simples tal que existe
uma aresta entre 
ada par de vérti
es.
Um grafo 
ompleto 
om vérti
es é denotado por .
Exemplos:
Teoria dos Grafos (Antunes Rangel&Araujo) � 18
Para que tipo de grafo podemos garantir a existên
ia de um 
ir
uito
hamiltoniano?
De�nição 6. Um Grafo Completo é um grafo simples tal que existe
uma aresta entre 
ada par de vérti
es.
Um grafo 
ompleto 
om n vérti
es é denotado por Kn.
Exemplos:
Teoria dos Grafos (Antunes Rangel&Araujo) � 19
Como obter um 
ir
uito hamiltoniano em um grafo 
ompleto Kn, 
om
n ≥ 3?
Numere os vérti
es do grafo de 1 a n. Como existe uma aresta entre
ada par de vérti
es, a sequên
ia 1, 2, . . . , n é um 
ir
uito hamiltoniano.
Quantos 
ir
uitos hamiltonianos um grafo 
ompleto possui? Vamos
examinar o K4:
Os 
ir
uitos {a, b, c, d, a} e {a, d, c, b, a} são diferentes ou iguais?
Teoria dos Grafos (Antunes Rangel&Araujo) � 20
Partindo do vérti
es 1, temos n− 1 es
olhas de arestas para fazer.
Em seguida, a partir do vérti
e 2, temos n− 2 arestas para es
olher;
e assim por dianteaté a es
olha da última aresta.
Ou seja, há (n− 1)! possibilidades; e se 
onsiderarmos que 
ir
uitos do
tipo {vi1 , vi2 , . . . , vin , vi1} são iguais ao 
ir
uito
{vi1 , vin , vin−1, . . . , vi2 , vi1}, teremos que o número total de 
ir
uitos é
dado por (n− 1)!/2.
Teorema 7. Em um grafo 
ompleto 
om n vérti
es existem (n− 1)/2
ir
uitos hamiltonianos aresta-disjuntos, se n ≥ 3 é ímpar.
Demonstração. Exer
í
io.
O Problema do Caixeiro
Viajante
Colo
ação do Problema
Teoria dos Grafos (Antunes Rangel&Araujo) � 22
Um viajante ne
essita visitar um 
erto número de 
idades
durante uma viagem e retornar ao lugar de origem de tal
maneira que 
ada 
idade é visitada exatamente uma vez e que
a distân
ia total per
orrida seja a menor possível. Dada e
distân
ia entre as 
idades, que rota ele deve es
olher?
Como resolver este problema?
Vamos representar o problema a
ima através de um grafo valorado. Seja
V o 
onjunto de 
idades, A o 
onjunto das estradas interligando as
idades e o valor de 
ada aresta 
omo sendo a distân
ia entre as
respe
tivas 
idades.
Teoria dos Grafos (Antunes Rangel&Araujo) � 23
Vamos supor que o viajante deseja visitar 5 
idades 
ujas estradas
existentes entre 
ada par de 
idade estejam representadas através do
seguinte grafo:
Em prin
ípio, este problema pode ser resolvido determinando-se todas as
rotas possíveis e es
olhendo a que resultar na menor distân
ia per
orrida.
Neste exemplo, uma possível rota é dada por: {A,B,C,D,E,A} 
uja
distân
ia é 5 + 2 + 4 + 3 + 4 = 18km.
A rota ótima é: {A,C,B,D,E,A} 
uja distân
ia é 14km.
Teoria dos Grafos (Antunes Rangel&Araujo) � 24
Esta té
ni
a é e�
iente?
Considere que o problema que envolva 10 
idades.
O número máximo de possíveis rotas seria de 9! = 362.880.
Uma máquina equipada 
om um programa que 
onseguisse examinar 1
milhão de rotas por segundo levaria 0, 36s para en
ontrar a melhor rota.
Se dobrássemos o número de 
idades, teríamos que examinar
1, 22× 1017 rotas (19!) e o mesmo programa levaria aproximadamente
3.800 anos para en
ontrar a melhor rota!
Exer
í
ios
Teoria dos Grafos (Antunes Rangel&Araujo) � 25
1. Quais dos grafos abaixo é hamiltoniano e/ou Euleriano? Exiba um
ir
uito hamiltoniano e/ou trajeto euleriano em 
aso positivo.
2. Dê um exemplo de um grafo não hamiltoniano 
om n vérti
es tal
que d(v) ≥ (n− 1)/2.
3. Dê um exemplo de um grafo hamiltoniano que não satisfaça o
Teorema de Dira
.
4. Dê um exemplo de um grafo que seja euleriano e hamiltoniano.
Digrafos Hamiltonianos
De�nições
Teoria dos Grafos (Antunes Rangel&Araujo) � 27
De�nição 8. Um digrafo D é dito ser hamiltoniano se possuir um
ir
uito orientado que in
lua todos os seus vérti
es.
Um digrafo não-hamiltoniano é dito ser semi-hamiltoniano se possuir um
aminho orientado que in
lua todos os seus vérti
es.
Pou
o sabe-se sobre digragos hamiltonianos.
Muitos teoremas para grafos hamiltonianos não são generalizados
fa
ilmente para digrafos.
Teorema de Dira
 (para digrafos)
Teoria dos Grafos (Antunes Rangel&Araujo) � 28
Seja D um digrafo fortemente 
onexo 
om n vérti
es. Se
ds(v) ≥
n
2
e de(v) ≥
n
2
para todo vérti
e v de D, então D é hamiltoniano.