MO417 - Questão para a prova oral

Número: 2010-089

Enunciado: Considere o grafo G abaixo:



Em qual das alternativas estão todas as arestas que pertencem à árvore de caminhos mínimos com origem no vértice a? Suponha que a árvore é construída relaxando-se todas as arestas saindo de cada vértice, sendo os vértices tomados numa ordem topológica de G.

1. (a,c) (a,b) (a,e) (b,d) (d,f).
2. (a,c) (a,b) (a,e) (b,f) (c,d).
3. (a,c) (a,e) (e,b) (b,d) (d,f).
4. (a,c) (a,e) (e,b) (b,f) (c,d).
5. NDA

Ideia original de: Fábio Augusto Faria