MO417 - Questão para a prova oral

Número: 2010-087

Enunciado: Considere o grafo G = (V, E) acíclico orientado ponderado representado pela matriz de pesos abaixo. Armazenamos na linha u e coluna v o peso w da aresta (u,v). Quando (u,v) ∉ E, temos w = ∞ na matriz.

	A	B	C	D	E
A	∞	1	-2	∞	-3
B	∞	∞	3	-2	∞
C	∞	∞	∞	-2	-2
D	∞	∞	∞	∞	-1
E	∞	∞	∞	∞	∞

Denotando por δ(u, v) a distância entre u e v no grafo, qual das alternativas abaixo está incorreta?

1. δ(A, C) = -2
2. δ(B, D) = -2
3. δ(C, E) = -3
4. δ(A, E) = -4
5. NDA

Ideia original de: Maikon Cismoski dos Santos