1s2020-j702-l3

Prévia do material em texto

J702 :: Teoria de Grafos
Lista #3
Questão 1. Utilize o Algoritmo de Dijkstra para encontrar o caminho mı́nimo
entre o vértice s e todos os vértices dos grafos G1 e G2 abaixo. Como resposta fi-
nal, você deve redesenhar o grafo identificando, para cada vértice v ∈ V (G), duas
coisas. Primeiro, o valor do custo do caminho mı́nimo de s à v; esse valor pode ser
anotado dentro de cada vértice. Segundo, você deve apresentar a árvore de caminhos
mı́nimos, destacando quais são as arestas que identificam os predecessores de cada
vértice. Neste desenho, não é necessário colocar os custos das arestas.
Atenção: para que todos os alunos tenham a mesma resolução, as vizinhanças
devem ser visitadas sempre em ordem alfabética. Ou seja, se um vértice x tem
vizinhança N(x) = {g, w, z, h, p, a}, por exemplo, você deve relaxar as arestas na
seguinte ordem: xa, xg, xh, xp, xw, xz.
s
b
c
d
e
t
47.1
−31.2
17.3
19.4
−23.5
29.6
−53.7
59.8
Figura 1: Grafo G1.
1
s
a
bc
d
e
f
g
h
i
4
9
6
−3
1 −1
2
2
3
−1 −1
7
8
4−3
Figura 2: Grafo G2.
Questão 2. Utilize o Algoritmo de Bellman-Ford para encontrar o caminho
mı́nimo entre o vértice s e todos os vértices dos grafos H1 e H2 abaixo, quando
posśıvel. Se não houver ciclo negativo no grafo, você deve redesenhar o grafo identi-
ficando o valor do custo do caminho mı́nimo de s à v e a árvore de caminhos mı́nimos,
assim como na Questão 1. Caso contrário, ou seja, se existir um ciclo negativo, você
deve destacá-lo no desenho.
Atenção: Você deve utilizar a ordenação das arestas dada na questão. Note que
nos dois grafos, as arestas foram substitúıdas por arcos. Sua execução do algoritmo
deve seguir o relaxamento de arestas saindo dos vértices apenas.
2
s
u
v
w
x
y
z
−3
4
−5
7
−2
2
1
Ordem das arestas: wx, vs, uw, xz, sy, xv, su
Figura 3: Grafo H1.
sj
k l
47
−14
41
−19
44
−26
Ordem das arestas: kj, lk, sl, js, ks, jl
Figura 4: Grafo H2.
3