MO417 - Questão para a prova oral

Número:

Enunciado: As afirmações abaixo descrevem a importância dos conceitos em fluxo maximal (maximum flow). Qual delas está incorreta?

a. Redes residuais (residual networks) são a estrutura usada para encontrar caminhos incrementantes (augmenting paths).
b. Caminhos incrementantes (augmenting paths) descrevem como aumentar o fluxo atual no grafo e a sua ausência indica que encontramos o fluxo maximal.
c. Cortes (cuts) descrevem o movito pelo qual a ausência de caminhos incrementantes implicam que encontramos o fluxo maximal.
d. Arestas antiparalelas (antiparallel edges), superfonte (supersource) e supersorvedouro (supersink) são formas de adaptar um grafo direcionado para que seja possível obter uma rede residual (residual network) a partir dele.
e. NDA

Idéia original de: Jorge Augusto Hongo

MO417 - Questão para a prova oral

Número:

Enunciado: Sobre o algoritmo de Dijkstra, quais das alternativas abaixo está correta?

a. O algoritmo relaxa cada aresta duas vezes
b. Dijkstra encontra os caminhos mais curtos mesmo com arestas de peso negativo, desde que não possuam ciclos negativos
c. O algoritmo funciona apenas se não houver ciclos, ou seja, se for um DAG (Directed Acyclic Graph)
d. O algoritmo se enquadra como um algoritmo guloso
e. NDA

Idéia original de: Jorge Augusto Hongo

MO417 - Questão para a prova oral

Número:

Enunciado: O algoritmo da busca em profundidade (depth-first search) pode classificar uma aresta (u, v) a partir da cor do vértice v. Quais dos critérios abaixo estão corretos?

I - BRANCO indica uma aresta de árvore (tree edge)
II - CINZA indica uma aresta de cruzamento (cross edge)
III - PRETO indica uma aresta de cruzamento (cross edge) ou uma aresta de avanço (forward edge) em grafos direcionados e não ocorre em grafos não-direcionados

a. apenas I
b. apenas II
c. I e II
d. I e III
e. NDA

Idéia original de: Jorge Augusto Hongo