MO417- QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Dado o grafo abaixo:

É correto afirmar:

1. O algoritmo de Dijkstra retorna os caminhos máximos.
2. Bellman-Ford é o melhor algoritmo para encontrar os caminhos mínimos neste grafo.
3. Se Bellman-Ford for executado utilizando a mesma ordem de visitação de Dijkstra, eles terão o mesmo tempo de execução.
4. Pode-se encontrar os caminhos mínimos a partir de qualquer origem em tempo O(V + E)
5. NDA 

Ideia original de: Anderson Carlos Sousa e Santos

MO417 - Questão para a prova oral

Número:

Enunciado: Considere uma busca em profundidade no grafo abaixo.

Definimos d[u] como o carimbo de tempo registrado quando u é descoberto e f[u] como o carimbo de tempo registrado quando a busca termina de examinar a lista de adjacências de u.  Visto que a busca pode iniciar a partir de qualquer vértice, é possível afirmar que:

1. Se d[A] > d[E] então f[A] > f[E]
2. Se d[A] < d[B] então f[B] > f[C]
3. Se f[F] < f[B] então d[B] < d[F]
4. Se d[F] < d[B] então d[B] = d[F] + 2
5. NDA