Resolución de problemas para árboles de expansión mínimos (Kruskal y Prim)

El árbol de expansión mínimo (MST) es un tema importante para GATE. Por lo tanto, discutiremos cómo resolver diferentes tipos de preguntas basadas en MST. Antes de comprender este artículo, debe comprender los conceptos básicos de MST y sus algoritmos (algoritmo de Kruskal y algoritmo de Prim ).

Tipo 1. Preguntas conceptuales basadas en MST:
hay algunas propiedades importantes de MST sobre la base de las cuales se pueden hacer preguntas conceptuales como:

• El número de aristas en MST con n Nodes es (n-1).
• El peso de MST de un gráfico siempre es único. Sin embargo, puede haber diferentes formas de obtener este peso (si hay bordes con los mismos pesos).
• El peso de MST es la suma de los pesos de los bordes en MST.
• La longitud máxima de la ruta entre dos vértices es (n-1) para MST con n vértices.
• Solo existe una ruta de un vértice a otro en MST.
• La eliminación de cualquier borde de MST desconecta el gráfico.
• Para un gráfico que tiene bordes con distintos pesos, MST es único.

Que – 1. Sea G un grafo conexo no dirigido con distinto peso de arista. Sea emax la arista con peso máximo y emin la arista con peso mínimo. ¿Cuál de las siguientes afirmaciones es falsa? (GATE CS 2000)
(A) Cada árbol de expansión mínimo de G debe contener emin.
(B) Si emax está en un árbol de expansión mínimo, entonces su eliminación debe desconectar G
(C) Ningún árbol de expansión mínimo contiene emax
(D) G tiene un árbol de expansión mínimo único

Solución: Como los pesos de borde son únicos, solo habrá un emin de borde y se agregará a MST, por lo tanto, la opción (A) siempre es verdadera.
Como el árbol de expansión tiene un número mínimo de aristas, la eliminación de cualquier arista desconectará el gráfico. Por lo tanto, la opción (B) también es cierta.
Como todos los pesos de los bordes son distintos, G tendrá un árbol de expansión mínimo único. Entonces, la opción (D) es correcta.
La opción C es falsa ya que emax puede ser parte de MST si otros bordes con pesos menores están creando un ciclo y el número de bordes antes de agregar emax es menor que (n-1).

Tipo 2. Cómo encontrar el peso del árbol de expansión mínimo dado el gráfico:
este es el tipo de pregunta más simple basado en MST. Para resolver esto usando el algoritmo de Kruskal,

• Organizar los bordes en orden no decreciente de pesos.
• Agregue los bordes uno por uno si no crean un ciclo hasta que obtengamos n-1 número de bordes donde n es el número de Nodes en el gráfico.

Que – 2. Considere un gráfico no dirigido completo con el conjunto de vértices {0, 1, 2, 3, 4}. La entrada Wij en la array W a continuación es el peso de la arista {i, j}. ¿Cuál es el peso mínimo posible de un árbol de expansión T en este gráfico tal que el vértice 0 sea un Node hoja en el árbol T? (GATE CS 2010)

(A) 7
(B) 8
(C) 9
(D) 10

Solución: En la array de adyacencia del grafo de 5 vértices (v1 a v5), las aristas dispuestas en orden no decreciente son:

(v1,v2), (v1,v4), (v4,v5), (v3,v5), (v1,v5), 
(v2,v4), (v3,v4), (v1,v3), (v2,v5), (v2,v3) 

Tal como está dado, el vértice v1 es un Node de hoja, debe tener solo un borde incidente. Por lo tanto, lo consideraremos al final. Considerando los vértices v2 a v5, las aristas en orden no decreciente son:

(v4,v5), (v3,v5), (v2,v4), (v3,v4), (v2,v5), (v2,v3)

Al agregar los tres primeros bordes (v4,v5), (v3,v5), (v2,v4), no se crea ningún ciclo. Además, podemos conectar v1 a v2 usando edge (v1,v2). El peso total es la suma del peso de estos 4 bordes, que es 10.

Tipo 3. ¿Cuántos árboles de expansión mínimos son posibles usando el algoritmo de Kruskal para un gráfico dado?

• Si todos los pesos de los bordes son distintos, el árbol de expansión mínimo es único.
• Si dos aristas tienen el mismo peso, entonces tenemos que considerar ambas posibilidades y encontrar posibles árboles de expansión mínimos.

Que – 3. El número de árboles de expansión mínimos distintos para el siguiente gráfico ponderado es ____ (GATE-CS-2014)

(A) 4
(B) 5
(C) 6
(D) 7

Solución: Hay 5 aristas con peso 1 y agregarlas todas en MST no crea un ciclo.
Como el gráfico tiene 9 vértices, necesitamos un total de 8 aristas, de las cuales se han agregado 5. De los 3 restantes, un borde está fijo representado por f.

Para los 2 bordes restantes, uno debe elegirse entre c o d o e y otro entre a o b. Los negros restantes siempre crearán un ciclo, por lo que no se consideran. Entonces, los MST posibles son 3*2 = 6.

Tipo 4. De las secuencias dadas, ¿cuál no es la secuencia de aristas agregada al MST usando el algoritmo de Kruskal?
Para resolver este tipo de preguntas, trate de averiguar la secuencia de aristas que puede producir Kruskal. La secuencia que no coincida será la respuesta.

Que – 4. Considere el siguiente gráfico:

¿Cuál de los siguientes NO es la secuencia de aristas agregadas al árbol de expansión mínimo usando el algoritmo de Kruskal? (GATE-CS-2009)
(A) (b,e), (e,f), (a,c), (b,c), (f,g), (c,d)
(B) (b ,e), (e,f), (a,c), (f,g), (b,c), (c,d)
(C) (b,e), (a,c), (e ,f), (b,c), (f,g), (c,d)
(D) (b,e), (e,f), (b,c), (a,c), (f ,g), (c,d)

Solución: los algoritmos de Kruskal agregan los bordes en orden no decreciente de sus pesos, por lo tanto, primero ordenamos los bordes en orden no decreciente de peso como:

(b,e), (e,f), (a,c), (b,c), (f,g), (a,b), (e,g), (c,d), (b,d), (e,d), (d,f).

Primero agregará (b,e) en MST. Luego, agregará (e,f) y (a,c) (ya sea (e,f) seguido de (a,c) o viceversa) debido a que ambos tienen el mismo peso y al agregarlos no se creará ciclo.
Sin embargo, en la opción (D), (b,c) se ha agregado a MST antes de agregar (a,c). Entonces no puede ser la secuencia producida por el algoritmo de Kruskal.