Want to create interactive content? It’s easy in Genially!

Get started free

Árboles Generadores mínimos

Amy Glez

Created on March 16, 2025

Start designing with a free template

Discover more than 1500 professional designs like these:

Halloween Infographic

Halloween List 3D

Magic and Sorcery List

Journey Map

Versus Character

Akihabara Connectors Infographic Mobile

Mobile mockup infographic

Explore all templates

Transcript

Árboles Generadores mínimos

Un Árbol Generador Mínimo (AGM) es un subgrafo de un grafo conexo y ponderado que conecta todos los vértices con el menor peso total posible y sin formar ciclos.

Algoritmo de Kruskal

Este algoritmo selecciona las aristas de menor peso y las añade al árbol, evitando ciclos, hasta conectar todos los vértices.

Dato Histórico

Algortimo de Prim

Herramientas

El concepto de AGM fue introducido por el matemático checo Otakar Borůvka en 1926, quien desarrolló un algoritmo para minimizar el costo de electrificación en Moravia del Sur.

Comienza desde un vértice y expande el árbol seleccionando la arista de menor peso que conecta un vértice dentro del árbol con uno fuera de él.

Lenguajes como Python ofrecen bibliotecas, como NetworkX, que permiten implementar y visualizar AGMs de manera eficiente.

Aplicaciones prácticas

Diseño de Redes: En la planificación de redes eléctricas, de agua o de telecomunicaciones, los AGMs ayudan a minimizar costos al determinar la forma más eficiente de conectar todos los nodos. Optimización de Rutas: En logística y transporte, se utilizan para encontrar rutas que reduzcan distancias y costos operativos (Formella, 2008).

www.tupáginaweb.com