Ejercicios Resueltos De Arbol De Minima Expansion
El Árbol de Mínima Expansión (AME), también conocido como Minimum Spanning Tree (MST), es un concepto fundamental en teoría de grafos. Básicamente, dado un grafo conectado y ponderado, un AME es un subgrafo que conecta todos los vértices sin ciclos y con el menor peso total posible.
¿Qué significa esto? Imagina una red de ciudades que necesitas conectar con carreteras. Cada carretera tiene un costo asociado (por ejemplo, longitud o precio de construcción). El AME es el conjunto de carreteras que conecta todas las ciudades con el costo total más bajo posible, sin crear rutas redundantes.
Existen varios algoritmos para encontrar el AME, pero dos de los más comunes son el algoritmo de Prim y el algoritmo de Kruskal. Veamos un ejemplo resuelto con el algoritmo de Kruskal:
Must Read
Ejemplo: Tenemos un grafo con 5 vértices (A, B, C, D, E) y las siguientes aristas con sus pesos:
- A-B: 4
- A-C: 2
- B-C: 1
- B-D: 5
- C-D: 8
- C-E: 10
- D-E: 2
Solución con el algoritmo de Kruskal:
- Ordenar las aristas por peso de menor a mayor: B-C (1), A-C (2), D-E (2), A-B (4), B-D (5), C-D (8), C-E (10).
- Seleccionar la arista de menor peso (B-C) y agregarla al AME. Nuestro AME actual: B-C (Peso total: 1).
- Seleccionar la siguiente arista de menor peso (A-C) y agregarla al AME. Nuestro AME actual: B-C, A-C (Peso total: 3).
- Seleccionar la siguiente arista de menor peso (D-E) y agregarla al AME. Nuestro AME actual: B-C, A-C, D-E (Peso total: 5).
- Seleccionar la siguiente arista de menor peso (A-B). Agregarla al AME. Nuestro AME actual: B-C, A-C, D-E, A-B (Peso total: 9).
- Verificar que todas las ciudades (vértices) estén conectadas. A, B, C, D, y E están todos conectados a través de las aristas seleccionadas.
El árbol de mínima expansión final tiene las aristas B-C, A-C, D-E y A-B, con un peso total de 9. Observa que aunque existen otras rutas posibles para conectar todas las ciudades, ninguna tendrá un costo total menor a 9.
El algoritmo de Kruskal funciona seleccionando las aristas de menor peso, siempre y cuando no creen un ciclo. Un ciclo es una ruta que regresa al mismo vértice sin pasar por vértices nuevos.
En resumen, el Árbol de Mínima Expansión es una herramienta poderosa para optimizar la conexión en redes donde el costo es un factor crítico. Entender los algoritmos para encontrarlo, como Kruskal y Prim, te permite aplicar este concepto en diversas áreas, desde la planificación de redes de telecomunicaciones hasta la logística y el transporte.
