MO417 - Questão para a prova oral

Número:

Enunciado: Dado uma rede de fluxo abaixo com fonte S e sorvedouro T, após executar o algoritmo de Ford-Fulkerson, qual o corte mínimo correspondente ao fluxo máximo de 12?

A) ({s, a}, {b, c, d, t})
B) ({s, c}, {a, b, d, t})
C) ({s, a, b}, {c, d, t})
D) ({s, c, d}, {a, b, t})
E) N.D.A

Ideia original de: Thaís Harumi Ussami

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

MO417 - Questão para a prova oral

Número:

Enunciado: Considere um grafo não orientado G com vértices pertencentes ao conjunto {40, 98, 7, 105, 20, 13, 10, 3, 49, 402} e arestas entre x e y quando x mod y = 0. Considere também a operação CONNECTED-COMPONENTS com o seguinte código abaixo:

CONNECTED-COMPONENTS(G)
para cada vertice v pertencente a V[G]
     MAKE-SET(v)
para cada aresta (u,v) pertencente a E[G]
     if (FIND-SET(u) != FIND-SET(v))
            UNION(u,v)

Com relação às quatro afirmações abaixo, assinale a alternativa correta:
I. O grafo G possui um total de 6 arestas.
II. Durante a execução de CONNECTED-COMPONENTS sobre G, FIND-SET e UNION são chamados respectivamente16 e 6 vezes.
III. O grafo G possui 3 componentes conexas.
IV. Um componente conexo do grafo G é {40, 20, 10}.

A) As afirmações II e IV são corretas
B) As afirmações I, II e IV são corretas
C) As afirmações I e III são corretas
D) Apenas a afirmação I é correta
E) N.D.A

Ideia original de: Thaís Harumi Ussami