MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-064

Enunciado: Seja G o grafo com 5 nós e 7 arestas abaixo. É gerado uma minimum spanning tree T de G.

Qual a ordem de inserção das arestas em T se utilizarmos o algoritmo de Kruskal para gerar T? E qual será a ordem se utilizarmos o algoritmo de Prim, utilizando o vértice a como origem, para montar T?

A) Para o alg. Kruskal: (c,e), (b,e), (a,b), (a,e), para o alg. Prim: (a,b), (b,e), (c,e), (a,e);
B) Para o alg. Kruskal: (c,e), (b,e), (a,b), (d,e), para o alg. Prim: (a,b), (a,e), (b,c), (d,e);
C) Para o alg. Kruskal: (c,e), (b,e), (a,b), (d,e), para o alg. Prim: (a,b), (b,e), (c,e), (d,e);
D) Para o alg. Kruskal: (d,e), (a,b), (b,e), (c,e), para o alg. Prim: (a,b), (b,e), (c,e), (d,e);
E) NDA

Obs: as arestas não são direcionadas, dessa forma, para uma aresta e entre x e y, tanto (x,y) quanto (y,x) podem ser utilizados para representar e.

Ideia original de: Félix Carvalho Rodrigues