Seja G = (V, E) qualquer gráfico de aresta ponderado não direcionado conectado. Os pesos das arestas em E são positivos. Considere as seguintes declarações:

1. O caminho entre um par de vértices em uma árvore de abrangência mínima de um gráfico não direcionado é necessariamente o caminho mais curto (peso mínimo).
2. A árvore de abrangência mínima de G é sempre única e o caminho mais curto entre um par de vértices pode não ser exclusivo.

Qual das afirmações acima é / são necessariamente verdadeiras?
(A) (1) apenas
(B) (2) apenas
(C) ambos (1) e (2)
(D) nem (1) nem (2)

Resposta: (D)
Explicação: Visto que os pesos das arestas não são definidos . Se os pesos das bordas forem distintos, o MST é sempre exclusivo, mas pode não ser os caminhos mais curtos.

(A)---1----(B)----2---(C)
 \                    /
  ---------3----------

E, se os pesos das arestas não forem distintos, tanto o MST quanto os caminhos em curto não são exclusivos.

(A)---2----(B)----2---(C)
 \                    /
  ---------2----------

Portanto, ambas as afirmações são falsas.
A opção (D) está correta.
Teste desta questão

Aprenda todos os conceitos do GATE CS com aulas gratuitas ao vivo em nosso canal do youtube.