Matemáticas discretas: árboles de expansión

Un árbol de expansión de un grafo no dirigido $ G $ es un árbol que incluye mínimamente todos los vértices de $ G $. Un gráfico puede tener muchos árboles de expansión.

Ejemplo

Árbol de expansión mínimo

Un árbol de expansión con un peso asignado menor o igual al peso de cada árbol de extensión posible de un gráfico ponderado, conectado y no dirigido $ G $, se denomina árbol de expansión mínimo (MST). El peso de un árbol de expansión es la suma de todos los pesos asignados a cada borde del árbol de expansión.

Ejemplo

Algoritmo de Kruskal

El algoritmo de Kruskal es un algoritmo codicioso que encuentra un árbol de expansión mínimo para un gráfico ponderado conectado. Encuentra un árbol de ese gráfico que incluye todos los vértices y el peso total de todos los bordes del árbol es menor o igual que todos los árboles de expansión posibles.

Algoritmo

Step 1 - Organizar todos los bordes del gráfico dado $ G (V, E) $ en orden ascendente según su peso de borde.

Step 2 - Elija el borde ponderado más pequeño del gráfico y verifique si forma un ciclo con el árbol de expansión formado hasta ahora.

Step 3 - Si no hay un ciclo, incluya este borde en el árbol de expansión; de lo contrario, deséchelo.

Step 4 - Repita el Paso 2 y el Paso 3 hasta que queden $ (V-1) $ número de aristas en el árbol de expansión.

Problem

Suponga que queremos encontrar el árbol de expansión mínimo para el siguiente gráfico G utilizando el algoritmo de Kruskal.

Solution

A partir del gráfico anterior, construimos la siguiente tabla:

No de borde Par de vértices Peso del borde
E1 (a, b) 20
E2 (a, c) 9
E3 (a, d) 13
E4 (antes de Cristo) 1
E5 (b, e) 4
E6 (b, f) 5
E7 (discos compactos) 2
E8 (d, e) 3
E9 (d, f) 14

Ahora reorganizaremos la tabla en orden ascendente con respecto al peso del borde -

No de borde Par de vértices Peso del borde
E4 (antes de Cristo) 1
E7 (discos compactos) 2
E8 (d, e) 3
E5 (b, e) 4
E6 (b, f) 5
E2 (a, c) 9
E3 (a, d) 13
E9 (d, f) 14
E1 (a, b) 20

Como obtuvimos los 5 bordes en la última figura, detenemos el algoritmo y este es el árbol de expansión mínimo y su peso total es $ (1 + 2 + 3 + 5 + 9) = 20 $.

Algoritmo de Prim

El algoritmo de Prim, descubierto en 1930 por los matemáticos Vojtech Jarnik y Robert C. Prim, es un algoritmo codicioso que encuentra un árbol de expansión mínimo para un gráfico ponderado conectado. Encuentra un árbol de ese gráfico que incluye todos los vértices y el peso total de todos los bordes del árbol es menor o igual que todos los árboles de expansión posibles. El algoritmo de Prim es más rápido en gráficos densos.

Algoritmo

  • Inicialice el árbol de expansión mínimo con un solo vértice, elegido al azar del gráfico.

  • Repita los pasos 3 y 4 hasta que todos los vértices estén incluidos en el árbol.

  • Seleccione una arista que conecte el árbol con un vértice que todavía no esté en el árbol, de modo que el peso de la arista sea mínimo y la inclusión de la arista no forme un ciclo.

  • Agrega la arista seleccionada y el vértice que conecta con el árbol.

Problem

Suponga que queremos encontrar el árbol de expansión mínimo para el siguiente gráfico G usando el algoritmo de Prim.

Solution

Aquí comenzamos con el vértice 'a' y seguimos.

Este es el árbol de expansión mínimo y su peso total es $ (1 + 2 + 3 + 5 + 9) = 20 $.