sábado, 18 de maio de 2013

tha

MO417 - Questão para a prova oral

Número:

Enunciado: Considere o grafo direcional ponderado G abaixo, onde a fonte é o vértice t.


Considere as seguintes afirmações abaixo e assinale a alternativa correta:

I) Ao aplicarmos o algoritmo de Bellman-Ford em G, relaxando as arestas na ordem (u,v), (u,x), (u,z), (v,u), (v,z), (v,x), (x,z), (t,u), (t,x), o algoritmo com o código abaixo retorna TRUE.
BELLMAN-FORD(G,w,s)
INITIALIZE-SINGLE-SOURCE(G,s)
para i=1 ate |V[G]| -1

   para cada aresta (u,v) pertencente a E[G]
       RELAX(u,v,w)
   para cada aresta (u,v) pertencente a E[G]
      se (v.d > u.d + w(u,v))
           return FALSE
return TRUE

II) Se eliminássemos a aresta de peso negativo (v,u) do grafo G, poderíamos aplicar o algoritmo de Dijkstra no grafo alterado, G', cujo código segue abaixo.
DIJKSTRA(G,w,s)
INITIALIZE-SINGLE-SOURCE(G,s)
S = vazio
Q = V[G]
while Q != vazio
    u = EXTRACT-MIN(Q)
    S = S U {u}
    para cada vértice v pertencente a G.Adj[u]
         RELAX(u,v,w)
Dado que o laço while itera |V| vezes, após a quarta iteração do laço teríamos a seguinte situação (obs: vertice.d representa o peso de um caminho mínimo da fonte até o vértice v):
S = {t,u,x,v}; t.pai = NILL; t.d = 0; u.pai = t; u.d = 7; v.pai = u; v.d = 15; x.pai = u; x.d = 9; z.pai = u; z.d = 18.

III) Se retirássemos a aresta (v,u) do grafo G, obtendo o grafo G', seria possível fazer uma ordenação topológica dos vértices do grafo G' e encontrar caminhos mínimos de fonte única, obtendo a situação final (obs: vertice.d representa o peso de um caminho mínimo da fonte até o vértice v):
t.pai = NILL; t.d = 0; u.pai = t; u.d = 7; v.pai = u; v.d = 15; x.pai = u; x.d = 9; z.pai = v; z.d = 17.

A) Apenas III é correta
B) Apenas II é correta
C) II e III são corretas
D) I e II são corretas
E) N.D.A


Ideia original de: Thaís Harumi Ussami

Nenhum comentário:

Postar um comentário