Árbol de expansión mínimo

Yo creo que hay un pequeño error, para ir del nodo (g) al no (b), tiene un costo de 6, mientras que si lo hacemos directamente sin tener que pasar por el nodo (f) podría tener un costo mínimo de 5.

Árbol de expansión mínimo:
Elegimos el árbol de expansión mínimo desde un árbol de expansión libre (cíclico) mediante el siguiente algoritmo:

• Elegimos un nodo cualquiera y seguimos la conexión de menor coste
• Iteramos eligiendo la conexión de menor coste evitando los ciclos (evitar nodos ya alcanzados) hasta que hayamos seleccionados todos los nodos.

Nota:

• Una vez generado el árbol podemos hallar el coste total (mínimo) sumando los costes de cada nivel del árbol

Que buen tema y que bien explicado!

Resumen: Siempre elegir la ruta que tenga el menor coste.

Hay una forma de minizar los costos de expansión, en un árbol de expansión, con un algoritmo, que nos permite hacerlo. Primero, podemos empezar escogiendo un nodo, ya sea al azar, o premeditado. Segundo, una vez escogido nuestro nodo, empezamos a conectarlo con los demás nodos, pero con la regla de que tiene que ser la conexión más barata. Algo a tener en cuenta, que es no podemos generar ciclos mientras conectamos los nodos, debido a que no saldría nuestro árbol de la mejor manera. Luego después de tener todos los nodos conectados, sin generar ciclos, podemos dibujar aparte, nuestro nuevo árbol, recordando escribir el costo de cada ruta. Luego para ver el coste total, sumamos todos los costes y para ver el coste por nivel, sumamos los costes que hay por cada nivel.

Hay muchos juegos que se basan en este concepto

Árbol de expansión
• Es un árbol donde sus aristas tienen un numero asociado (grafo ponderado).
• Este numero representa un recuso o corso relacionado a los nodos.
.
Árbol de expansión mínimo
• Es un árbol de expansión donde la trayectoria se determina minimizando la distancia total es decir buscando los caminos de menor distancia.
• El árbol de expansión mínima es apropiado para problemas en los cuales la redundancia es expansiva o el flujo a lo largo de los arcos se considera instantáneo.
• Ejemplo: conectar todas las casas a la energía eléctrica, sistema de cableado telefónico, sistemas de tuberías de agua, etc.
• El coste total de nuestro árbol de expansión mínimo será la suma de todas las conexiones seleccionadas.
.
Algoritmo para hallar el árbol de expansión mínimo

1. Elegiremos un nodo cualquiera para ser nuestro nodo raíz.
2. Observamos las conexiones de nuestro nodo y escogemos la conexión de menor distancia.
3. Repetimos este proceso hasta conectar todos los nodos.
4. Debemos tener cuidado al conectar los nodos para evitar producir ciclos o rutas cerradas, porque no serviría el algoritmo.

Que interesante, sin duda que este curso en general te da muy buenas para programar

Eres de los pocos maestros de matemáticas que usa las herramientas gráficas de forma eficiente, además de que te apegas al rigor de los conceptos matemáticos, lo único que me hubiera gustado ver en este curso es la aplicación usando Python.

Excelente tema el de árboles, considero que tiene infinidas de aplicaciones.

Estos temas son tan fascinantes!!

En qué se aplicaría?

y si quisiera el árbol máximo tomaría los caminos con mayor costo

excelente curso, muy bien explicado

Es lo mismo que el algoritmo de Prim??

Muy buen tema, aplicable en muchas situaciones!

IMPORTANCIA de no seleccionar ciclos o rutas cerradas

Último nodo (d), tres opciones con diferentes costos

• Árbol de expansión mínimo: Es el árbol donde a partir de un vértice raíz se pueda conectar a todos los otros vértices usando los recursos mínimos.
• **Costo mínimo: **Se suman todos los valores de los costos de cada conexión.

Muy bien.

Interesante 😃

Interesante

A este tipo de árbol también le llaman ruta critica

Excelente clase.