Grafos - Caminhos
Caminhos Máximo / Mínimo:
Utilizando um grafo para representar estradas que unem
cidades, sendo os nós as cidades e os arcos as distâncias entre
as cidades, pergunta-se:
- Quais os caminhos (se existir algum) que ligam Spa à Rec?
- Existindo mais de um caminho, qual o mais curto?
Rio
30
Spa
10
10
Vit
5
7
40
Sal
Rec
5
Nat
15
<(Spa,Sal),(Sal,Nat),(Nat,Rec)>
<(Spa,Rio),(Rio,Vit),(Vit,Rec)>
<(Spa,Rio),(Rio,Nat),(Nat,Rec)>
<(Spa,Rec)>
= 30
= 45
= 52
= 40
Caminho Mínimo
Algoritmo de Dijkstra para Caminho Mínimo:
- Inserir o nó origem na árvore
- Enquanto o nó destino não está na árvore faça:
- Calcule a distância para todos os nós vizinhos dos nós que estão na árvore
- Selecione o nó com a menor distância total e insira-o na árvore
Simulação para o grafo:
Aplicações
1: Caminhos a partir de x
2: Escolhido menor: xa
4: Escolhido menor: xab
3: Caminhos a partir de x,a
Aplicações
5: Caminhos a partir de x,a,b
6: Escolhido menor: xad
Aplicações
7: Caminhos a partir de x,a,b,d
8: Escolhido menor: xac
Aplicações
9: Caminhos a partir de x,a,b,c,d
10: Escolhido menor: xady
Caminho Euleriano
O matemático suíço Leonhard Euler (pronuncia-se “óiler”)
(1707-1783) ficou curioso devido a uma charada popular
sobre o lugarejo de Königsberg (uma cidade da antiga
Prússia, mais tarde chamada de Kaliningrado, na Rússia).
c
c
a
b
d
b
A charada era determinar se uma pessoa poderia passear
pela cidade passando apenas uma vez por cada ponte.
Caminho Euleriano
Euler teve a brilhante idéia de apresentar esta charada
como um grafo. As pontes são as arestas e os trechos de
terra (chamados de a até d) são os vértices.
c
a
d
b
Um caminho Euleriano em um grafo G é um caminho que
une as arestas exatamente uma vez.
Caminho Euleriano
Existe um caminho Euleriano em um grafo conexo se, e
somente se, não houver nenhum ou existirem no máximo
dois vértices ímpares.
No caso de não haver vértices ímpares, o caminho pode
começar em qualquer vértice e terminará neste mesmo
vértice; para o caso de haver dois vértices ímpares, o
caminho deve começar em um vértice ímpar e terminar
no outro”.
Caminho Hamiltoniano
Um caminho hamiltoniano é um caminho que permite
passar por todos os vértices de um grafo G, não repetindo
nenhum. Se com esse caminho é possível descrever um
ciclo, este é denominado ciclo hamiltoniano (ou circuito
hamiltoniano) em G. Um grafo que possua tal circuito é
chamado de grafo hamiltoniano.
Caminho Hamiltoniano
 Suponha que um caixeiro viajante deseja visitar N
cidades (vértices) de uma certa localização e que, entre
alguns pares de cidades existem rotas (arcos ou arestas),
através das quais ele pode viajar a partir de uma cidade
para outra.
 Cada rota tem um número associado, que pode
representar a distância ou o custo necessário para
percorrê-la.
 Assim, o caixeiro viajante deseja encontrar um caminho
que passe por cada uma das N cidades apenas uma vez,
e além disso que tenha um custo menor que certo valor;
onde o custo do caminho é a soma dos custos das rotas
percorridas. Note que a existência de tal caminho nem
sempre é possível.