MO417 - Questão para a prova oral

Número: 2010-083

Enunciado: Seja G=(V, E, w) um grafo orientado e ponderado, sendo w a função que associa um peso a cada aresta. Denote por δ(u,v) a distância, isto é, o peso de um caminho de peso mínimo entre u e v, se houver, ou ∞ caso contrário, Suponha que G é inicializado com d[v] ← ∞ e π[v] ← NIL para todos os vértices, a seguir fazemos d[s] ← 0, e que o único meio pelo qual d e o subgrafo de predecessores são mudados é através de alguma sequência de passos de relaxamento, usando a rotina RELAX abaixo. Com relação às propriedades de caminhos mínimos e relaxamento, qual das alternativas é INCORRETA:

RELAX(u, v, w)
    if d[v] > d[u] + w(u,v) then
        d[v] ← d[u] + w(u,v)
        π[v] ← u

1. Para todo (u,v) ∈ E, temos δ(s,v) < δ(s,u) + w(u,v)
2. d[v] ≥ δ(s,v), para todo v ∈ V
3. Se não existe caminho de s até v, então d[v] = δ(s,v) = ∞
4. Quando d[v] = δ(s,v) para todo v ∈ V, o subgrafo de predecessores é uma árvore de caminhos mínimos com raiz em s.
5. NDA

Ideia original de: Alexandre Toshio Hirata