4.3.2. Árboles de expansión.
Definición: Un árbol de expansión de un grafo no dirigido G=(V, A) y conexo es un subgrafo G’=(V, A’) no dirigido, conexo y sin ciclos.
Ejemplo: si el grafo ND es conexo, el árbol abarcador (en profundidad o anchura) es un árbol de expansión.
Si el grafo es ponderado, el coste del árbol de expansión será la suma de los costes de las aristas.
Problema del árbol de expansión de coste mínimo:
Dado un grafo ponderado no dirigido, encontrar el árbol de expansión de menor coste.
Escoger un vértice cualquiera v. El árbol consta sólo del nodo v.
Del resto de vértices, buscar el que esté más próximo a v (con una arista (w, v) de mínimo costo). Añadir w y la arista (w, v) al árbol.
Buscar el vértice más próximo a cualquiera de estos dos, añadir ese vértice y la arista al árbol de expansión.
Así sucesivamente hasta haber añadido los n vértices.