GrafosHamiltonianos

Páginas: 6 (1315 palavras) Publicado: 31 de maio de 2015
Matemática Discreta – if670
Anjolina Grisi de Oliveira
Ciência da Computação
Colaboração: lnpa e ljacs

Teoria dos Grafos
Caminhos e Noção de Grafos com pesos

Caminhos e Isomorfismo


A existência de circuitos simples com um
tamanho n é uma invariante.

Caminhos e Isomorfismo


Além disso, caminhos podem ser usados para
construir mapeamentos, que podem ser
isomorfismos.

Caminho 1: u1, u4,u3, u2,
u5
Caminho 2: v3, v2, v1, v5, v4

Cortando caminhos entre vértices


Teorema:
– Seja G um grafo cuja matriz de adjacência A usa a
seguinte ordem nos vértices: v1, v2, …, vn. A
quantidade de caminhos diferentes de tamanho r de vi
para vj, onde r é um inteiro positivo é igual a ai,j entrada
da matriz Ar .
a,b,a,b,d
a,b,a,c,d
a,b,d,b,d
a,b,d,c,d
a,c,a,b,d
a,c,a,c,d
a,c,d,b,d
a,c,d,c,d Circuito Euleriano


Um circuito euleriano em um grafo G é um circuito
simples que contem cada aresta de G.

Teorema (Euler 1736)
Um multigrafo conectado G possui um
circuito euleriano se e somente se o
grau de cada vértice de G é par.


Prova
– Ida: Seja G um grafo euleriano. Por cada

ocorrência de vértice do circuito euleriano, existe
uma aresta que chega nesse vértice e outra que
sai dessevértice. Como toda aresta faz parte do
circuito, isto é, nenhuma aresta fica fora do ciclo,
necessariamente o número de arestas por cada
vértice é par.

– Volta: Suponhamos que todos os vértices possuem

grau par. Seja vi um vértice do grafo. Tentemos, a
partir de vi, construir um caminho que não passa
duas vezes pela mesma aresta, e até que não seja
possível continuar. Como todos os vértices
possuemum grau par, sempre será possível entrar
e sair de um vértice. A única exceção é o vértice vi
onde o caminho vai terminar. Se esse caminho,
que chamaremos C1, contém todas as arestas de
G, temos um ciclo euleriano. Senão, retiramos de
G todas as arestas que fazem parte de C1. No
grafo resultante G', todos os vértices também
possuem grau par e necessariamente um deles faz
parte de C1, senão o grafonão seria conexo.

– Volta (continuação): Recomeçamos o mesmo

processo com o grafo G', partindo de um vértice
comum com C1, obtendo assim um novo circuito
C2. A figura abaixo mostra que dois circuitos que
têm um vértice em comum podem formar um
circuito único: chegando no vértice comum em um
dos dois circuitos, continuamos o percurso no outro
circuito. Continuando esse processo,
necessariamenteobteremos um circuito único que
contém todas as arestas de G.

Pontes de Königsberg



É possível sair de uma das ilhas, passar uma
única vez por cada uma das pontes e retornar ao
ponto de origem?

Pontes de Königsberg



Como nem todos os vértices têm grau par, o grafo
não é euleriano. Logo, é impossível atravessar
todas as pontes uma só vez e voltar ao lugar de
partida.

Aplicação emjogos
Como fazer um desenho que comece a
partir de um ponto, retorne a esse ponto e o
lápis não seja levantado do papel?



Podemos construir um circuito euleriano.



Existem vários algoritmos para construir um
circuito euleriano.



Vamos estudar um baseado na prova do teorema
de Euler.

Algoritmo de Hierholzer
Algoritmo para a construção de um
ciclo euleriano sugerido a partir da
prova doteorema de Euler


Comece em qualquer vértice u e percorra
aleatoriamente as arestas ainda não visitadas a
cada vértice visitado até fechar um ciclo



Se sobrarem arestas não visitadas, recomece a
partir de um vértice do ciclo já formado

 Se

não existem mais arestas não visitadas,
construa o ciclo euleriano a partir dos ciclos
formados, unindo-os a partir de um vértice comum

Algoritmo deHierholzer

Ciclo 1: 1,2,5,9,10,11,6,3,1

Ciclo 2: 2,6,5,10,6,7,12,8,7,4,3,2

Ciclo Euleriano: 1,2,6,5,10,6,7,12,8,7,4,3,2,5,9,10,11,6,3,1

Algoritmo de Hierholzer

Ciclo 1: 1,2,5,9,10,11,6,3,1

Ciclo 2: 2,6,5,10,6,7,12,8,7,4,3,2

Ciclo Euleriano: 1,2,6,5,10,6,7,12,8,7,4,3,2,5,9,10,11,6,3,1

Caminhos Eulerianos


Teorema
– Um multigrafo conectado G possui um caminho
euleriano, mas que não é...
Ler documento completo

Por favor, assinar para o acesso.

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!