Por supuesto.
Si realiza un resumen mental de un algoritmo de generación de MST como el de Kruskal, después de ordenar todos los bordes, intercambiar los bordes con pesos iguales en la lista ordenada los consideraría en diferentes órdenes. Esto puede conducir a nuevas órdenes de generaciones de conjuntos disjuntos (pasos intermedios del algoritmo de Kruskal) y, por lo tanto, en última instancia, múltiples árboles de expansión mínima únicos.
Sin embargo, déjame darte un ejemplo mucho más fácil de por qué son posibles múltiples árboles de expansión mínima. Considere el siguiente gráfico
- ¿Cómo se podrían analizar las publicaciones arbitrarias de Reddit para adivinar si el póster es suicida?
- ¿Cuánto estrés se le da a los algoritmos y las estructuras de datos en el curso de pregrado en CMI? ¿Se enseña programación competitiva allí?
- ¿Cuál es la mejor manera de ingresar al último proceso de aprendizaje de algoritmos de reconocimiento facial?
- ¿Alguien puede proporcionarme un algoritmo de muestra en CS para ISC 2017?
- ¿Cuántos niveles habrá en un árbol completamente binario si tiene n número de nodos?
Todos los 5 vértices dados forman un ciclo en el gráfico. Para generar el árbol de expansión mínimo, debemos eliminar un borde de este ciclo. Ahora, para decidir qué borde eliminar, hay un teorema que establece que en cualquier ciclo, el borde con el peso máximo no puede ser un pert del árbol de expansión mínimo (Definitivamente intente probar esto por su cuenta). Sin embargo, aquí todos los bordes tienen el mismo peso, por lo que podemos eliminar cualquier borde y seguir obteniendo un MST.
