Considere el siguiente gráfico no dirigido con pesos de borde como se muestra:
El número de árboles de expansión de peso mínimo del gráfico es ___________.
(A) 3
(B) 4
(C) 5
(D) 2
Respuesta: (A)
Explicación: Según el árbol de expansión mínimo de Kruskal usando :
Ahora, hay 3 bordes entre estos componentes para conectarlos.
De acuerdo con el algoritmo de Kruskal, incluiremos primero los bordes de pesos mínimos si no hay un ciclo resultante.
Pero, solo necesitamos un borde para formar el árbol de expansión, y tenemos 3 opciones para un borde.
Por lo tanto, el número de árboles de expansión es 3.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA