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 $.