Question

Seja o cenário de um governador que seja melhorar o acesso entre um conjunto de cidades de uma região. Como os recursos são escassos, a equipe do governador precisa selecionar um conjunto de estradas nas quais serão investidos recursos. A equipe faz um levantamento do custo para melhorar as estradas entre cada duas cidades. Na figura abaixo, as cidades estão representas pelo conjunto de nós {0, 1, 2, 3, 4, 5} e o valor das arestas corresponde ao custo calculado pela equipe para melhorar a estradas entre os nós correspondentes.

O algoritmo de Prim identifica uma árvore geradora de mínimo custo a partir da escolha inicial de um nó aleatório e, a seguir, selecionando as arestas cujos pesos são os menores desde que não formem um ciclo, até que todos os nós sejam selecionados. No caso de empate no valor de arestas, uma é escolhida arbitrariamente.

Algoritmo de Prim

1. Selecione um nó aleatório

2. Crie conjunto de arestas como um conjunto vazio

3. Repita até que todos os nós estejam representados no conjunto de arestas

Selecione a menor aresta que se conecta aos nós presentes no conjunto de arestas

Inclua a aresta no conjunto de arestas





A figura abaixo ilustra como o algoritmo de Prim identifica uma árvore geradora de mínimo custo a partir da escolha inicial de um nó aleatório (no caso, o nó 0) e, a seguir, selecionando as arestas cujos pesos são os menores desde que não formem um ciclo, até que todos os nós sejam selecionados.

Aplique os conceitos apresentados para avaliar a veracidade das afirmações a seguir.

Um conjunto de arestas que compõem uma árvore geradora de mínimo custo para o grafo é {0-2, 2-1, 2-3, 3-5, 4-5}.

Um conjunto de arestas que compõem uma árvore geradora de mínimo custo para o grafo é {0-2, 2-1, 2-3, 2-5, 4-5}.

Um grafo pode ter mais que uma árvore geradora de mínimo custo.


II é verdadeira.


II e III são verdadeiras.


Todas são verdadeiras.


I e III são verdadeiras.


I é verdadeira.

Answer 1

Resposta: todas estão corretas.

Explicação:

Answer 2

Resposta: Todas estão corretas.

Explicação: as arestas (2-5) e (3-5) tem o mesmo peso (igual a 2).

Assim, tanto os caminhos por (2-5) ou por (3-5) resultarão o mínimo custo (itens I e II) estão corretos.

Como consequência o item III também será correto pois um mesmo grafo apresentou mínimo custo por dois caminhos diferentes.

[Confirmado pelo gabarito AVA]