Ejercicios resueltos de árboles de expansión mínima

Ordenar aristas por peso creciente:

CD(1), BC(2), AC(3), BD(4), DE(5), AB(6), BE(7), CE(8), AD(9)

MST de Kruskal: CD(1) + BC(2) + AC(3) + DE(5) = 11

MST de Prim: AC(3) + CD(1) + BC(2) + DE(5) = 11

Ambos algoritmos producen MSTs con el mismo peso total: 11

Las aristas seleccionadas son las mismas (aunque en diferente orden):

• Kruskal: {CD, BC, AC, DE}
• Prim: {AC, CD, BC, DE}

• Número de aristas: $n-1 = 5-1 = 4$ $\checkmark$
• Conecta todos los vértices $\checkmark$
• No contiene ciclos $\checkmark$
• Peso mínimo entre todos los árboles de expansión posibles $\checkmark$

Teorema: Si todas las aristas tienen pesos diferentes, el MST es único.

Demostración por contradicción:

Supongamos que existen dos MSTs diferentes: $T_1$ y $T_2$.

Como $T_1 \neq T_2$, existe al menos una arista $e \in T_1$ tal que $e \notin T_2$.

Sea $e$ la arista de menor peso de la diferencia simétrica $T_1 \triangle T_2$ (aristas que están en uno de los dos árboles pero no en el otro). Sin pérdida de generalidad, $e \in T_1$ y $e \notin T_2$.

Al añadir $e$ a $T_2$, se crea exactamente un ciclo $C$.

En este ciclo debe existir al menos una arista $f \neq e$ tal que $f \notin T_1$ (si no, $T_1$ contendría el ciclo $C$).

Análisis de pesos:

• $f \in T_2$ y $f \notin T_1$, luego $f$ está en la diferencia simétrica; por la elección de $e$ y porque los pesos son distintos: $w(e) < w(f)$
• $T_2 \cup \{e\} \setminus \{f\}$ es también un árbol de expansión, de peso $w(T_2) + w(e) - w(f) < w(T_2)$

Pero esto contradice que $T_2$ sea un MST.

Conclusión: El MST es único cuando todos los pesos son diferentes.

Considerar el grafo:

• Vértices: {A, B, C, D}
• Aristas: AB(1), AC(2), AD(2), BC(3), BD(3), CD(1)

MST 1 (usando Kruskal):

Orden de aristas: AB(1), CD(1), AC(2), AD(2), BC(3), BD(3)

• Añadir AB(1) → componentes: {A,B}, {C}, {D}
• Añadir CD(1) → componentes: {A,B}, {C,D}
• Añadir AC(2) → componentes: {A,B,C,D}

MST$_1$ = {AB, CD, AC}, peso = 4

MST 2 (modificando orden):

Orden alternativo: CD(1), AB(1), AD(2), AC(2), BC(3), BD(3)

• Añadir CD(1) → componentes: {A}, {B}, {C,D}
• Añadir AB(1) → componentes: {A,B}, {C,D}
• Añadir AD(2) → componentes: {A,B,C,D}

MST$_2$ = {CD, AB, AD}, peso = 4

Ambos árboles:

• Conectan todos los vértices $\checkmark$
• Tienen $n-1 = 3$ aristas $\checkmark$
• No contienen ciclos $\checkmark$
• Tienen el mismo peso total: 4 $\checkmark$

Conclusión: Cuando existen aristas con pesos iguales, pueden existir múltiples MSTs.

Estrategia: Para cada arista del MST, encontrar el mejor árbol de expansión que no incluye esa arista.

Algoritmo:

1. Encontrar el MST usando Prim → peso $W_1$
2. Para cada arista $e_i$ en el MST:
   • Calcular el mejor árbol de expansión sin $e_i$ → peso $W_i$
3. El segundo MST es el de menor peso entre todos los $W_i$

Vértices: {A, B, C, D, E, F}

Aristas con pesos:

AB(2), AC(3), AD(6), AE(8), AF(9)

BC(1), BD(4), BE(7), BF(5)

CD(2), CE(6), CF(8)

DE(3), DF(4)

EF(1)

Aplicando Prim desde A:

MST principal: {AB(2), BC(1), CD(2), DE(3), EF(1)}, peso = 9

Para cada arista del MST, calcular el mejor árbol sin ella:

Sin AB(2): Necesitamos conectar A al resto

• Mejor opción: AC(3)
• Árbol: {AC(3), BC(1), CD(2), DE(3), EF(1)}, peso = 10

Sin BC(1): Necesitamos reconectar $\{A,B\}$ con $\{C,D,E,F\}$

• Mejor opción: AC(3)
• Árbol: {AB(2), AC(3), CD(2), DE(3), EF(1)}, peso = 11

Sin CD(2): Necesitamos alternativa C-D

• Mejor opción: BD(4)
• Árbol: {AB(2), BC(1), BD(4), DE(3), EF(1)}, peso = 11

Sin DE(3): Necesitamos alternativa D-E

• Mejor opción: DF(4) + EF(1) ya está
• Árbol: {AB(2), BC(1), CD(2), DF(4), EF(1)}, peso = 10

Sin EF(1): Necesitamos alternativa E-F

• Mejor opción: DF(4)
• Árbol: {AB(2), BC(1), CD(2), DE(3), DF(4)}, peso = 12

Segundo MST: Peso = 10 con dos opciones equivalentes:

1. {AC(3), BC(1), CD(2), DE(3), EF(1)}
2. {AB(2), BC(1), CD(2), DF(4), EF(1)}

Pasos principales:

1. Ordenar aristas: $O(m \log m)$
2. Procesar aristas: $m$ iteraciones
3. Union-Find por arista: $O(\alpha(n))$ amortizado

Complejidad total de Kruskal: $O(m \log m + m \cdot \alpha(n))$

Como $\alpha(n)$ es prácticamente constante: $O(m \log m)$

En términos de $n$: Como $m \leq \binom{n}{2} = \frac{n(n-1)}{2}$:

$O(m \log m) = O(m \log n^2) = O(m \log n)$

Con heap binario:

1. Inicialización: $O(n)$
2. Extraer mínimo: $n$ veces, $O(\log n)$ cada vez → $O(n \log n)$
3. Actualizar claves: Hasta $m$ actualizaciones, $O(\log n)$ cada una → $O(m \log n)$

Complejidad total de Prim: $O((n + m) \log n)$

Con heap de Fibonacci:

• Extraer mínimo: $O(n \log n)$ total
• Decrease-key: $O(m)$ total amortizado
• Complejidad total: $O(n \log n + m)$

Grafos dispersos ($m = O(n)$):

• Kruskal: $O(n \log n)$
• Prim (heap binario): $O(n \log n)$
• Prim (heap Fibonacci): $O(n \log n)$

Grafos densos ($m = O(n^2)$):

• Kruskal: $O(n^2 \log n)$
• Prim (heap binario): $O(n^2 \log n)$
• Prim (heap Fibonacci): $O(n^2 + n \log n) = O(n^2)$

Kruskal:

• Lista de aristas: $O(m)$
• Union-Find: $O(n)$
• Total: $O(m + n)$

Prim:

• Heap: $O(n)$
• Arrays auxiliares: $O(n)$
• Total: $O(n)$

Usar Kruskal cuando:

• El grafo es disperso ($m \ll n^2$)
• Las aristas se pueden ordenar fácilmente
• Se necesita paralelización (más fácil con Kruskal)

Usar Prim cuando:

• El grafo es muy denso
• Se dispone de heap de Fibonacci
• Se trabaja con grafos donde $n$ es pequeño pero $m$ es grande

Caso especial - Prim con matriz de adyacencia:

Para grafos muy densos, Prim se puede implementar con complejidad $O(n^2)$ sin usar heap:

Para cada vértice no en MST:

Encontrar el de menor distancia al MST: O(n)

Total: n iteraciones $\times$ O(n) = O(n²)

Conclusión:

• Grafos dispersos: Ambos $O(n \log n)$, empate
• Grafos densos: Prim es superior, especialmente con heap de Fibonacci o implementación $O(n^2)$