árbol De Expansión Mínima Ejercicios Resueltos

Entendamos el Árbol de Expansión Mínima (AEM). Imagina una red de ciudades conectadas por carreteras. Queremos conectar todas las ciudades usando la mínima cantidad de carretera posible. ¡Eso es un AEM! Técnicamente, es un subconjunto de las aristas de un grafo conectado, sin ciclos, que conecta todos los vértices con el peso total mínimo.

Ejercicio Resuelto #1: Kruskal

Kruskal es un algoritmo popular para encontrar AEM. Suena complicado, pero es bastante sencillo. Aquí te va el paso a paso:

Ordena las aristas: Toma todas las carreteras (aristas) y ordénalas de la más corta (menos pesada) a la más larga.
Elige la más corta: Empieza con la carretera más corta.
¿Crea un ciclo?: Si agregar esta carretera crearía un circuito (ciclo) en la red, ¡recházala!
Agrégala (si no hay ciclo): Si no crea un ciclo, agrégala a tu "árbol" de carreteras seleccionadas.
Repite: Repite los pasos 2-4 hasta que todas las ciudades (vértices) estén conectadas.

Ejemplo: Tenemos 5 ciudades (A, B, C, D, E) y las siguientes distancias (pesos): AB=3, AC=6, BC=4, BD=5, CE=7, DE=2. Sigamos Kruskal:

Must Read

DE (2) - La agregamos.
AB (3) - La agregamos.
BC (4) - La agregamos.
BD (5) - La agregamos.
AC (6) - La RECHAZAMOS porque crea un ciclo (A-B-C).
CE (7) - La agregamos.

¡Listo! Hemos conectado todas las ciudades con el AEM. El peso total es 2 + 3 + 4 + 5 + 7 = 21.

Árbol de expansión mínima: Ejercicio resuelto a mano | Paso a paso

Ejercicio Resuelto #2: Prim

Otro algoritmo útil es el de Prim. A diferencia de Kruskal, Prim construye el árbol "desde cero", agregando vértices uno a la vez.

Elige un inicio: Selecciona una ciudad al azar como punto de partida.
Arista más cercana: Encuentra la carretera más corta que conecta tu "árbol" actual con una ciudad que aún no está en el árbol.
Agrega la ciudad: Añade esa ciudad y la carretera al árbol.
Repite: Repite los pasos 2-3 hasta que todas las ciudades estén en el árbol.

Ejemplo: Usemos las mismas ciudades y distancias del ejemplo anterior (A, B, C, D, E; AB=3, AC=6, BC=4, BD=5, CE=7, DE=2). Empecemos en A.

Árbol de Expansión Mínima - Algoritmo de Kruskal - YouTube

Iniciamos en A.
La carretera más corta desde A es AB (3). Agregamos B.
Ahora, las carreteras más cortas desde A o B son BC (4) (desde B). Agregamos C.
La carretera más corta desde A, B o C es BD (5) (desde B). Agregamos D.
Finalmente, la carretera más corta desde A, B, C o D es DE (2) (desde D) o CE(7) (desde C). Escogemos DE. Agregamos E.

Obtuvimos un AEM con las aristas AB, BC, BD, y DE. El peso total es 3 + 4 + 5 + 2 = 14. Nota importante: Dependiendo del punto de partida, el árbol puede lucir diferente, pero el peso total del AEM siempre será el mismo (si el grafo tiene un único AEM).