687386_Unidade 02

Prévia do material em texto

1
Unidade II
Caminhos e Circuitos (1)
Pontifícia Universidade Católica de Minas Gerais
Prof. Pasteur Jr e Max do Val Machado 
1 Conjunto de transparências baseado no material da Profa. Raquel Mini
2
Caminhos e Circuitos
• Seqüência de arestas: seqüência 
alternada de vértices e arestas 
começando e terminando com vértice. 
Cada aresta é incidente ao vértice que a 
precede e a antecede
Ex.: v1 a v2 a v1 g v3
v1
v2v3
v4 v5
a
b
c
d e f
g
h
3
Caminhos e Circuitos
• Caminho: seqüência de arestas no qual 
nenhuma aresta aparece mais de uma 
vez
Ex.: v1 a v2 b v3 c v3 d v4 e v2 f v5
– Caminho aberto: vértice inicial é
diferente do vértice final
Ex.: v1 a v2 b v3 c v3
– Caminho fechado: caminhos que 
começam e terminam no mesmo vértice
Ex.: v1 a v2 b v3 c v3 g v1
v1
v2v3
v4 v5
a
b
c
d e f
g
h
4
Caminhos e Circuitos
• Caminho simples: caminho aberto no 
qual nenhum vértice aparece mais de 1 
vez. 
Ex.: v1 a v2 b v3 
• Circuito: caminho fechado no qual 
nenhum vértice (exceto o primeiro e o 
último) aparece mais de uma vez.
Ex.: v1 a v2 b v3 g v1
v1
v2v3
v4 v5
a
b
c
d e f
g
h
5
Caminhos e Circuitos
seqüência de arestas
caminho
aberto fechado
caminho 
simples
circuito
4
1
2 3
5
v1
v2v3
v4 v5
a
b
c
d e f
g
h
6
Caminhos e Circuitos
• TEOREMA: Se um grafo possui 
exatamente 2 vértices de grau ímpar, 
existe um caminho entre esses dois 
vértices.
• TEOREMA: Um grafo simples com n
vértices e k componentes possui no 
máximo (n-k)(n-k+1)/2 arestas.
• TEOREMA: O número mínimo de 
arestas de um grafo simples com n
vértices e k componentes é n-k.
7
Grafos Eulerianos
• As pontes de Königsberg: é possível 
começar em algum ponto (A, B, C ou 
D) andar por todas as pontes 
exatamente 1 vez e retornar ao ponto 
inicial?
A
B
C D
vértices: pontos de terra
aresta: pontes
A
C
B
D
8
Grafos Eulerianos
• O Problema do Explorador: um 
explorador deseja explorar todas as 
estradas entre um número de cidades. 
É possível encontrar um roteiro que 
passe por cada estrada apenas uma 
vez e volte a cidade inicial?
vértices: cidades
arestas: estradas
9
Grafos Eulerianos
• Problema: encontrar um caminho 
fechado que passe por todas as 
arestas uma única vez
(a) (b)
(c) (d)
10
Grafos Eulerianos
• Para grafos conexos, se é possível 
encontrar um caminho fechado que passe 
por todas as arestas uma única vez, 
dizemos que G é um grafo euleriano
• TEOREMA: Um grafo conexo é euleriano 
se, e somente se, todos os seus vértices 
tiverem grau par
11
Grafos Eulerianos
• Dominó: é possível arranjar todas as 
peças de um dominó em um caminho 
fechado?
Vértices: número
arestas: peça do dominó
1 2
4
12
Grafos Unicursais
• Um grafo G é dito unicursal se ele 
possuir um caminho aberto de euler, ou 
seja, se é possível percorrer todas as 
arestas de G apenas 1 vez sem retornar 
ao vértice inicial.
Caminho aberto de euler: a c d a b d e b
• Se adicionarmos uma aresta entre os 
vértices inicial e final do caminho aberto 
de euler, esse grafo passa a ser um 
grafo euleriano
a b
c
d
e
13
Grafos Unicursais
• Um grafo conexo é unicursal se, e 
somente se, ele possuir exatamente 2 
vértices de grau ímpar
• Casos:
– Grafo euleriano: todos os vértices de 
grau par
– Grafo unicursal: dois vértices de grau 
ímpar
14
Grafos Unicursais
• É possível fazer o desenho abaixo sem 
retirar o lápis do papel e sem retroceder?
• Quantos traços são necessários para 
traçar o diagrama abaixo? Ou seja, 
quantas vezes devemos retirar o lápis do 
papel para fazer o diagrama abaixo (sem 
retroceder)?
15
Grafos Hamiltonianos
• Um Circuito de Hamilton em um grafo 
conexo é um circuito que passa por 
todos os vértices do grafo uma única 
vez (exceto pelo vértice inicial)
• Todo grafo que possui um circuito de 
hamilton é chamado de grafo 
hamiltoniano
• O Circuito de hamilton de um grafo com 
n vértices contém n arestas
16
Grafos Hamiltonianos
• Um Caminho de Hamilton em um grafo 
conexo é um caminho simples que 
passa por todos os vértices do grafo 
exatamente uma única vez
• Considerações sobre grafos 
Hamiltonianos:
– O grafo deve ser conexo
– Loops e arestas paralelas podem ser 
desconsideradas
– Se um grafo é hamiltoniano, então a 
inclusão de qualquer aresta não 
atrapalha esta condição
17
Grafos Hamiltonianos
• TEOREMA DE ORE: Seja G um grafo 
simples com n vértices . Se para 
todo par de vértices não adjacentes v e 
w, a soma de seus graus for maior ou 
igual a n, então G é hamiltoniano.
– Exemplo:
• TEOREMA DE DIRAC. Seja G um grafo 
simples com n vértices tal que n >= 3
.Se o grau de cada vértice for n/2 no 
mínimo, então G é hamiltoniano.
– Exemplo:
�n≥ 3�
18
Grafos Hamiltonianos
• Esses teoremas deixam muito a desejar, 
veja só: 
• O grafo acima é Hamiltoniano e não
obedece a nenhum dos dois teoremas. 
• As condições dos dois teoremas são, 
portanto, suficientes, mas não
necessárias, ou seja, se forem
observadas, o grafo é hamiltoniano, mas
se não forem, pode ser que o grafo seja.
19
Grafos Hamiltonianos
• TEOREMA: Em um grafo completo com n
vértices, n ímpar e , existem 
circuitos hamiltonianos disjuntos de 
arestas.
• TEOREMA: Em um grafo completo com n
vértices, n par e , existem 
circuitos hamiltonianos disjuntos de 
arestas.
�n≥ 3� n− 1
2
�n≥ 4� n− 2
2
20
Grafos Hamiltonianos
• Seating Problem: 9 membros de um 
novo clube se encontram todos os dias 
para almoçar ao redor de uma mesa. 
Eles decidiram se sentarem de tal 
forma que em cada dia cada membro 
tenha vizinhos diferentes. Quantos 
dias serão necessários para 
percorrerem todas as configurações?
21
Grafos Hamiltonianos
• Cavalo do Xadrez: Um cavalo deve 
começar em alguma posição, visitar 
todas as posições exatamente uma 
vez e retornar à posição inicial.
⇒ Para qual tamanho do tabuleiro nxn
existe esse circuito?
⇒ Para qual nxn o grafo é
hamiltoniano?
�n≥ 3� n− 12
22
O Problema do Caixeiro Viajante
• Um caixeiro viajante deseja visitar um 
número de cidades e voltar ao ponto de 
origem de maneira que ele visite todas as 
cidades e percorra a menor distância 
possível. Como escolher sua rota?
Grafo com peso nas
arestas
– Vértices: cidades
– Arestas: estradas
A
EB
C D
9 6
8
73 2
5
83
6
⇒ Encontrar um circuito de hamilton 
de peso mínimo