Práctica de Teoría de Grafos
Algoritmos para la búsqueda de Árboles
Generadores Mínimos
Prim y Kruskal
Un árbol generador de un grafo G, es un subgrafo que es árbol
y contiene a todos los vértices del grafo.
Un árbol generador mínimo en un grafo conexo y ponderado
G, es un árbol generador de G de peso mínimo.
Se presentan a continuación dos métodos para construir un
árbol generador mínimo de un grafo conexo y ponderado de 'n'
vértices.
Algoritmo de Prim
(1957) (Jarník, 1930)
Algoritmo de Kruskal
(1956)
Victorino Sanz Prat (980079)
Facultad de Informática. UPM