MO417 - Questão para a prova oral

Número: 2009-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 necessariamente analisar todas as arestas do grafo para decidir sua inclusão na árvore.
5. NDA

Ideia original de: Luiz Augusto Muniz de Paula