-
A árvore geradora mínima de um grafo conexo não direcionado construída com o algoritmo de Kruskal é única.
Essa parte está correta.
Nessa árvore geradora mínima, a substituição de arestas de mesmo peso não afetará o custo total da árvore.
A substituição de arestas pode gerar outros cíclos, outras arestas podem ser selecionadas para não gerar ciclos/laços. Outras arestas selecionadas afetarão o custo total da árvore.
-
Eu discordo do colega. Não sou desenvolvedor, então, me corrijam se eu estiver errado.
Eu discordo da primeira afirmação que diz que: "A árvore geradora mínima de um grafo conexo não direcionado construída com o algoritmo de Kruskal é única".
Isso está errado pois se tivermos o mesmo peso (custo) nas arestas entre pares de vértices distintos ainda não visitados, poderemos escolher qualquer um deles, desde que não seja formado um ciclo. Essa possibilidade de escolha resulta em árvores distintas e não árvores únicas.
A segunda parte pra mim está correta. Seguindo a mesma idéia, se tivermos o mesmo peso (custo) nas arestas entre pares de vértices distintos ainda não visitados, poderemos escolher qualquer um deles, desde que não seja formado um ciclo. Com isso teremos 2 ou mais árvores distintas, porém as duas com o mesmo custo total.
-
Gabarito Errado!
Você está correto Marcelo, podem existir várias árvores geradoras mínimas em um grafo.
Quanto a segunda parte, qualquer substituição de arestas de mesmo peso fará com que o custo continue o mesmo, é igual trocar 6 por meia dúzia.
-
O erro está na primeira sentença. Uma arvore geradora mínima por meio do algoritmo de kruskal pode não ser unica. Se existir aresta com o mesmo peso, o algoritmo de kruskal pode construir duas arvores geradoras minimas com o mesmo custo. A segunda setença está correta.
-
Prezados,
Uma árvore geradora mínima é o caminho mais curto de tal maneira que os arcos forneçam um caminho entre todos os pares de nós.
A depender do grafo, a árvore mínima pode não ser única, se 2 ou mais caminhos tiverem o mesmo tamanho, empatando em sendo o mais curto.
Portanto a questão está errada.