PERCURSOS
André Falcão, Carlos Augusto, Rafael Broédel e Lucas Dipré
Serra
2011
Índice
1..................................................................O que é caminho e
circuito
1.1...............................................................Caminho
1.2...............................................................Circuito
1.3...............................................................Classificação
2..................................................................Caminhos Eulerianos
2.1...............................................................Definição
2.2...............................................................Como surgiu
2.3...............................................................Modelo do Problema
2.4 ..............................................................Caminho Aberto e
Caminho Fechado
2.5 ..............................................................Aplicações
3..................................................................Circuito Hamiltoniano
3.1...............................................................Verificação e
Classificação
3.2...............................................................O problema do caixeiro
viajante
4.................................................................Pseudocódigo
5.................................................................Exercícios
6.................................................................Referências
1) Caminhos e Circuitos
1.1) Caminho
É uma seqüência de vértices ligados por arestas. As
arestas fazem parte do caminho.
Caminho 1-2-4-1
Caminho 1-2-3-1
1.2) Circuito
É um caminho formado por x + 1 vértices. Deve começar
e terminar no mesmo vértice. Mesmo escolhendo o vértice
inicial ao acaso, ele continuará sendo um circuito.
A seqüência dos vértices x1, x2, x5, x4, x1 forma um circuito.
1.3) Classificação
Simples: Um caminho é considerado simples se ele não
contem a mesma aresta mais de uma vez.
Idêntico: Dois ciclos são idênticos quando um for obtido a
partir do outro através da troca de seus vértices. Em outras
palavras, iniciar o ciclo em outro vértice.
2) Caminhos Eulerianos
2.1) Definição:
Caminhos eulerianos são caminhos nos quais se utilizam todas as arestas uma
única só vez num determinado grafo.
2.2) Como Surgiu:
O caminho euleriano surgiu com o famoso problema das Sete
pontes de Königsberg (que foi uma das principais fundações
da teoria dos grafos), onde os moradores da cidade
de Königsberg (território da Prússia até 1945, atual Kaliningrado,
na Rússia), que é cortada pelo Rio Prególia, onde há duas
grandes ilhas que, juntas, formam um complexo que na época
continha sete pontes, discutiam nas ruas da cidade a possibilidade
de atravessar todas as pontes sem repetir nenhuma. Havia-se
tornado uma lenda popular à possibilidade da façanha quando
Euler, em 1736, provou que não existia caminho que possibilitasse
tais restrições.
Representação das pontes.
2.3) Modelo do Problema:
Euler usou um raciocínio muito simples. Transformou os caminhos em retas e
suas intersecções em pontos, criando possivelmente o primeiro grafo da história.
O Grafo utilizado como modelo é definido como:
V = { m | m é uma ilha ou uma margem }
A = { (m1,m2, p} | existe uma ponte p unindo as margens ou ilhas m1 e m2 }
Os conjuntos acima são apresentados, a seguir, na forma extensiva, contendo
todos seus elementos, extraídos do problema:
V = { 1, 2, 3, 4 }
A = { (1,3,e), (1,3,f), (1,2,a), (1,2,b), (1,4,d), (2,4,c), (3,4,g) }
Com isso, podemos construir o seguinte grafo:
Grafo G
Observação sobre o grafo G:
 Não Orientado: O mesmo caminho faz ligação de uma vértice a outra e
vice-verso, exemplo: o caminho “a” pode ser usado para ligar o vértice 1 ao
vértice 2, e o vértice 2 ao vértice 1, [(1,2,a), (2,1,a)].
 Multigrafo: Um vértice pode ter mais de um caminho para outro mesmo
vértice, como exemplo, os vértices 1 e 2 tem os caminhos “a” e “b” fazendo
ligação entre eles.
 Conexo: Todo vértice está ligado à pelo menos um outro vértice.
Solução:
TEOREMA: Um grafo conexo é um grafo de Euler se e somente se todos os seus
vértices são de grau par (caminho fechado) ou existir exatamente dois vértices de
grau ímpar (caminho aberto).
2.4) Caminho Aberto e Caminho Fechado:
A diferença entre um caminho euleriano aberto e um fechado está no final do
caminho. Caso se parta e se chegue no mesmo vértice teremos um caminho
fechado. Caso a partida não coincida com a chegada teremos um caminho
euleriano aberto.
Exemplo Caminho Fechado:
Exemplo Caminho Aberto:
Prova:
Imagine que G seja um grafo de Euler. Então ele contém um caminho de Euler.
Seguindo esse caminho nota-se que chegamos num vértice 'entrando„ por uma
aresta e encontramos outra para 'sair' do vértice e continuar o caminho. Se
houver outras arestas adjacentes ao vértice, 'entramos' por uma destas arestas
e devemos encontrar uma, ainda não visitada, para 'sairmos' do vértice. Se
houver um número n ímpar de arestas em pelo menos um dos vértices, ao
realizar o caminhamento, em um determinando momento, „entramos‟ no vértice
e não haverá „saída‟ ainda não visitada. O caminhamento não pode continuar.
Solução:
Pela análise do grafo modelo G para o problema das pontes de Königsberg,
observa-se que para todo vértice seu grau é ímpar. Logo, o grafo G não é um
grafo de Euler. Isso significa que o problema não possui solução.
2.5) Aplicações:
As aplicações dos caminhos eulerianos se relacionam, basicamente, com
problemas de atendimento seqüencial, sobre um conjunto de usuários de um
serviço oferecido no interior de uma rede de tráfego, tais como, entrega de
correio, coleta de lixo, vendas por atacado, etc.
Imagine um carteiro que deve percorrer um roteiro todo dia. O problema é de
identificar esse roteiro de maneira a minimizar a distância total percorrida. Essa
situação pode ser representada por um grafo onde as arestas correspondem
às ruas e os vértices correspondem aos cruzamentos.
3) O Problema do Circuito de Hamilton
O famoso matemático William Rowan Hamilton (1805-1865) colocou um
problema em teoria de grafos que consistia em dizer se um caminho num grafo
é um caminho elementar que contém todos os vértices do grafo. Um ciclo
hamiltoniano é um ciclo que contém todos os vértices do grafo. Um grafo dizse grafo hamiltoniano se contém um ciclo hamiltoniano.
Tentativa e erro
O problema do ciclo Hamiltoniano pode ser resolvido para um determinado
grafo usando a técnica de tentativa e erro, a teoria do algoritmo é o seguinte:
Comece por um nó do grafo e tente alguns caminhos escolhendo diversos
arcos. Se o caminho resulta em um nó repetido, não é um ciclo, jogue-o fora e
tente um caminho diferente. Se o caminho pode ser completado para formar
um ciclo, verifique se todos os nós são visitados, se não jogue-o fora e tente
um caminho diferente. Continue assim até tentar todos os caminhos possíveis
ou encontrar um caminho que sirva.
Na teoria, para grafos muito pequenos esse algoritmo é razoavelmente
aceitável, mas para grafos mais robustos ele é ineficiente, pois vão existir
caminhos demais para se tentar.
Euler x Hamilton
Diferentemente de Leonhard Euler (1707-1783), Hamilton não conseguiu um
algoritmo simples para determinar, para um grafo arbitrário, se existe um
caminho Hamiltoniano. De fato existe uma teoria de que esse algoritmo nunca
será encontrado pois o algoritmo tem comprovadamente complexidade n² , e
com uma quantidade grande de caminhos fica impraticável uma resolução
como a encontrada por Euler em seu algoritmo.
3.1) Verificação e Classificação
Não existe uma equação polinomial absoluta para saber se um grafo tem ou
não requisitos para ser um circuito hamiltoniano. Apenas utilizando-se de
testes de caminhos no grafo para fazer a checagem, o que aumenta a
complexidade exponencialmente. No entanto, algumas condições permitem
verificar se um grafo é ou não hamiltoniano:
1. Se um n-grafo simples com três ou mais vértices satisfaz grau(v) + grau(w) ≥
n para quaisquer vértices não vizinhos um do outro, então o grafo é
hamiltoniano.
2. Se um grafo simples com três ou mais vértices, vértices esses que tem o
grau não inferior a metade do número de vértices. Então o grafo é
hamiltoniano.
3.2) O Problema do Caixeiro Viajante
Se considerarmos um grafo com peso, se existe um circuito hamiltoniano para
o grafo, podemos encontrar um peso mínimo? Esse é o famoso problema do
caixeiro viajante, que continua sofrendo com o problema da ineficiência do
algoritmo para um grafo arbitrário de tamanho mais robusto, mas com o
desenvolvimento de algoritmos como o do vizinho mais próximo torna possível
a verificação de grafos maiores, mas não de todo e qualquer grafo.
Exemplos
Exemplo de dois grafos que não admitem Circuito de Hamilton:
Segue-se o exemplo de um grafo que admite Circuito de Hamilton: um
ircuito poderá ser AHGFEDIBCA:
Reparemos que a figura anterior foi obtida da figura (b) acrescentando uma aresta,
a aresta CA.
4) Pseudocódigo
ALGORITMO CaminhodeEuler
CaminhoDeEuler (matriz n x n A)
//Determina se existe um caminho de Euler em um grafo conexo
//sem laços e com matriz de adjacências A
Variáveis Locais:
int total //numero de nos impares encontrados até agora
int grau //o grau do nó
int i,j //índices da matriz
total = 0
i=1
enquanto total<=2 e i<=n faça
grau=0
para j=1 até n faça
grau=grau+A[i,j]
fim do para
se impar(grau) entao
total = total + 1
fim do se
i=i+1
fim do enquanto
se total > 2 então
escreva ("Não Existe Caminho de Euler")
senão
escreva ("Existe Caminho de Euler")
fim do se
fim do CaminhoDeEuler
5) Exercícios
1-Julgue as Sentenças a Seguir:
a) Um Grafo com quatro nós Impares ainda pode ser conexo.
b) Existe um Caminho de Euler em qualquer grafo com um número par de nós
impares.
c) Existe um algoritmo O(n²) que testa a existência de um caminho de Euler
em um grafo com nós.
d) Um Circuito Hamiltoniano usa cada arco e cada nó do grafo exatamente
uma vez, exceto o nó que é ao mesmo tempo, Inicial e final.
e) Não se conhece nenhum algoritmo que resolva o problema do circuito
hamiltoniano.
2-Dado o Grafo a seguir:
1
2
4
3
5
6
Determine se o Grafo especificado tem o caminho de Euler de acordo com o
Teorema de Euler.
3- A partir da matriz a seguir, diga se existe um ciclo Euleriano:
0
2
1
0
0
2
0
1
0
0
1
1
0
1
1
0
0
1
0
2
0
0
1
2
0
Respostas:
1a) V
b) F
c) V
d) F
e) F
2- Sim, existe ciclo euleriano pois todos os nós tem grau par.
3- Não, pois os nós 1,2,4 e 5 tem grau impar, que vai contra o Teorema do
Caminho de Euler.
6) Referencias:
http://www6.ufrgs.br/espmat/disciplinas/novos_conteudos/modulo_I/conteudos1c.h
tm
http://www.felr.ufpa.br/images/ResumoTutoriaisCaldwell_Jnane.pdf
http://www.inf.ufsc.br/grafos/problema/pontes/grafos.html
GERSTING, J. L., Fundamentos Matemáticos para a Ciência da Computação,
Ed. LTC, 5ª Ed. 2008, Capítulo 6.2.
Imagens retiradas do Google Imagens.