¿Cuál es el número mínimo de árboles de expansión (MST) mínimos de la gráfica completa con N vértice?
Respuestas
2 para la respuesta № 1Creo que la respuesta es 1.
Es posible construir una gráfica completa conn nodos que tiene exactamente un MST. Para hacer esto, construya una gráfica con n nodos etiquetados 1, 2, 3, ..., n. Luego, agregue un borde de costo 0 de 1 a 2, de 2 a 3, de 3 a 4, ..., de n - 1 a n, y agregue bordes conectando cada par de nodos que haya costado 1. Claramente, la selección de todos los bordes de costo cero da un posible árbol de expansión de este gráfico, y es el árbol de expansión mínimo porque si se seleccionara cualquier otra opción de bordes, el costo sería al menos 1. Además, este es el único MST en el gráfico que ha costado 0, ya que si se seleccionara otro conjunto de bordes, ese conjunto tendría que incluir al menos un borde de costo al menos 1, por lo que el MST total habría costado al menos 1.
¡Espero que esto ayude!