29 de julio - JoseA4718/Portafolio-I-2020 GitHub Wiki

Árbol de expansión mínima

En un subconjunto del grafo que contiene todos los vértices cuyas aristas tienen la suma de los pesos mínimos. Un árbol es un subconjunto del grafo que está conectado y no tiene ciclos. Si este árbol tiene n vértices tiene que poseer n-1 aristas. Existe únicamente una ruta entre dos vértices cualquiera. Si se agrega un vértice más se generaría un ciclo y pararía de ser árbol de expansión mínima. El árbol de expansión se encuentra mediante los algoritmos de Prim y Kruskal.

Algoritmo de Prim

El árbol crece por etapas. Va revisando vértice por vértice el camino más barato que puede tomar y lo va guardando, si al revisar otro vértice y se da cuenta que se podía llegar de manera más barata que lo guardado hasta esa posición se altera el camino que va generando el algoritmo, así hasta que todos los vértices tengan por lo menos una arista tocándolos, o en otras palabras, que ya se complete el árbol de expansión mínima.

Algoritmo de Kruskal

Se ponen todas las aristas en orden ascendente sobre el peso, primero el más barato y de último el más caro, junto a los vértices que esta arista incorpora, tomando como inicio el primero que se pone se van aceptando las aristas si no forman ciclos y rechazando si sí los forma. De esta manera quedarán como aceptadas solo las aristas con menor peso que no generan ciclos. Por ende, devuelve el árbol de expansión mínima.