MO417 - Questão para a prova oral

Número: 127

Enunciado:
Considere o grafo G = (V, E) onde todas as arestas tem custos ESTRITAMENTE positivos (> 0). Sabendo que |V| é suficientemente grande e |E| também é suficientemente grande vamos escolher dois vértices u e v. Após a escolha um algoritmo de caminho mais curto (um para todos) é executado com origem em u.
Considere então o caminho de u para v (u->v) e seja i um vértice deste caminho.
A alternativa INCORRETA é:

1. Pode existir um cíclo em UM DOS CAMINHOS mínimos.
2. Podem existir outros caminhos u->v (diferentes do caminho encontrado pelo algoritmo) que também são mínimos
3. O caminho u->i também é mínimo
4. O caminho i->v também é mínimo
5. NDA

Autor(a): Bruno Conti Marini