MO417 - Questão para a prova oral

Número: 2010-079

Enunciado: No grafo G abaixo está destacado, em vermelho, um caminho de peso mínimo do vértice A ao vértice D (A->B->C->D). Se uma constante S for somada ao peso de cada aresta do grafo G, para quais valores de S o caminho A->B->C->D continuará sendo mínimo? E se cada aresta do grafo G for multiplicada por P, para quais valores de P o caminho A->B->C->D continuará sendo mínimo?

Assinale a alternativa contendo intervalos de valores de S e P que mantém a minimalidade do caminho A->B->C->D:

1. S ≥ 1 e P > 0.
2. S ≤ 1 e P > 1.
3. S ≥ 0 e P ≥ 0.
4. S > 2 e P ≥ 0.
5. NDA

Ideia original de: Fábio Augusto Faria