MO417 - Questão para a prova oral

Número: 117

Enunciado:
Qual das afirmativas abaixo é VERDADEIRA:

1. Busca em profundidade sempre pode ser usada para determinar o menor caminho entre dois vértices.
2. Considerando uma busca em profundidade em um grafo: para todo vértice v, a primeira aresta percorrida a partir de v sempre é classificada como uma aresta de árvore.
3. Para grafos direcionados, se o vértice u foi descoberto antes do vértice v em uma busca em profundidade, então a aresta (v,u) é de retorno.
4. O algoritmo de Kruskal, usado para achar a árvore geradora mínima, não precisa analisar todas as arestas do grafo.
5. NDA

Autor(a): Luiz Augusto Muniz de Paula