MO417 - 1ª QUESTÃO PARA A PROVA ORAL

Número:
Enunciado: Dada a rede de fluxo abaixo com origem "s" e sorvedor "t", determine o valor do fluxo, o fluxo máximo e o corte mínimo s-t, respectivamente.

a) 15 , 21 , ({s,a,b,c,d,e} {t})
b) 15 , 23 , ({a,b,c,d,e} {s,t})
c) 15 , 21 , ({s,a,b,c,d} {e,t})
d) 23 , 23 , ({s,a,b,c} {d,e,t})
e) NDA

Ideia original de: Lucas Oliveira Batista

MO417 - 2ª QUESTÃO PARA A PROVA ORAL

Número:
Enunciado: Sobre o método de Ford-Fulkerson e suas implementações podemos afirmar:

I) Em uma rede de fluxo, um corte (S,T) é definido como um corte em que a origem "s" e o sorvedor "t" encontram-se em conjuntos diferentes.
II) Em uma rede de fluxo, o fluxo máximo com origem "s" e sorvedor "t" é igual a capacidade do corte máximo (S,T)
III) O algoritmo de Edmonds-Karp tem complexidade O(VE²), pois utiliza a busca em largura O(VE) para calcular caminhos aumentantes.
IV) Em uma rede de fluxo G com origem "s" e sorvedor "t", se existe um caminho de "s" até "t" sobre a rede residual Gf então o fluxo em G não é máximo.

a) I, III e IV são verdadeiras
b) II e III são verdadeiras
c) III e IV são verdadeiras
d) I e IV são verdadeiras
e) NDA

Ideia original de: Lucas Oliveira Batista

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Considerando os algoritmos de Bellman-Ford, Dag-Shortest-Paths ou Dijkstra, analise os grafos abaixo e indique quais destes algoritmos podem ser utilizados para encontrar um caminho mais curto a partir do vértice s.

 Grafo 1:

Grafo 2:

Grafo 3:

a) Grafo 1: Dijkstra e Dag-Shortest-Paths. Grafo 2: Bellman-Ford e Dijkstra. Grafo 3: Dag-Shortest-Paths e Bellman-Ford

b) Grafo 1: Bellman-Ford. Grafo 2: Bellman-Ford e Dag-Shortest-Paths. Grafo 3: Bellman-Ford e Dijkstra

c) Grafo 1: Nenhum dos algoritmos. Grafo 2: Bellman-Ford e Dag-Shortest-Paths. Grafo 3: Bellman-Ford e Dijkstra

d) Grafo 1: Bellman-Ford. Grafo 2: Bellman-Ford e Dag-Shortest-Paths. Grafo 3: Bellman-Ford, Dag-Shortest-Paths e Dijkstra

e) NDA

Ideia original de: Lucas Oliveira Batista

MO417-QUESTÃO PARA A PROVA ORAL -1ª QUESTÃO

Número:

Enunciado: Quais das arestas devem ser removidas do grafo abaixo para que seja possível obter uma ordenação topológica?

a) 9 e 3

b) 8 e 5

c) 1 e 10

d) 9 e 1

e) NDA

Ideia original de: Lucas Oliveira Batista

MO417 - QUESTÃO PARA A PROVA ORAL - 2ª QUESTÃO

Número:

Enunciado: Marque a alternativa que NÃO corresponde a uma possível “breadth-first tree”, construída pela busca em largura com origem no vértice 1 sobre o grafo abaixo:

a)                                                                                b)

                                              

                

 c)                                                                              d)

e) NDA

Ideia original de: Lucas Oliveira Batista