MO417 - Questão para a prova oral

Número: 2010-082

Enunciado: Seja G = (V, E) um grafo com pesos nas arestas. Considere as seguintes afirmações:

I. Seja M uma árvore geradora mínima de G. O caminho mínimo em M entre qualquer par de vértices s e t é também um caminho mínimo em G.
II. Seja P um caminho mínimo entre dois vértices s e t de G. Se incrementarmos os pesos de cada aresta de G em uma unidade, P continuará sendo um caminho mínimo de s a t.
III. Na execução do algoritmo de Bellman-Ford, após relaxar |V| - 1 vezes todas as arestas de G, ele verifica se existe um ciclo negativo em G em tempo O(|V|).

Assinale a alternativa correta:

1. Apenas as afirmações I e II são falsas.
2. Apenas as afirmações I e III são falsas.
3. Apenas as afirmações II e III são falsas.
4. Todas as afirmações são falsas.
5. NDA

Ideia original de: Marcos Vinícius Mussel Cirne