Examen GRAFOS 2025/26-2 - Actividad 5 (2 puntos)

 

 

Se pide aplicar el algoritmo de Prim para encontrar un árbol generador minimal del grafo dado por la tabla de pesos. Interpretamos los ceros fuera de la diagonal como ausencia de arista. Por tanto, las aristas del grafo son:

AC = 3, AD = 7, AE = 9, AF = 7, BD = 4, BF = 4, CD = 1, CE = 5, DE = 6, EF = 3.

Aplicamos el algoritmo de Prim comenzando en el vértice A. En la tabla, una etiqueta de la forma (p, u) indica que el coste mínimo provisional para conectar ese vértice al árbol es p, usando como predecesor el vértice u. El símbolo ∗ indica que el vértice ya ha sido incorporado al árbol.

 

 

A partir de los predecesores finales, obtenemos las aristas del árbol generador minimal: AC, CD, DB, BF, FE.

Por tanto, T = {AC, CD, DB, BF, FE}.

El coste total es 3 + 1 + 4 + 4 + 3 = 15.