MO417 - Questão para a prova oral

Número: 2010-104

Enunciado: O algoritmo de Johnson computa as distâncias mínimas (os custos dos menores caminhos) entre quaisquer pares de vértices de um grafo. Se o grafo possui ciclos negativos, não há caminhos mínimos definidos para determinados pares de vértices e o algoritmo retorna esta informação. Caso contrário, tais distâncias são calculadas empregando algoritmos eficientes. Para tal, um procedimento inicial modifica os pesos das arestas do grafo para que elas tenham valores não-negativos.
Sejam u e v um par de vértices do grafo passado como entrada. Para um caminho P entre eles, denote por W(P) seu custo no grafo original e por W'(P) seu custo quando se emprega a nova função de custo. Considere as afirmações a seguir:

• Para dois caminhos P e Q entre u e v, W(P) - W(Q) = W'(P) - W'(Q)
• Se W(P) é não negativo, então W(P) = W'(P)
• Se W(P) é não positivo, então W'(P) ≥ 0
• Se W(P) > 0 então W'(P) > 0

Quantas destas afirmações estão corretas?

1. 1
2. 2
3. 3
4. 4
5. NDA

Ideia original de: Daniel Cason