3.4.2. Árboles de expansión mínimos.

• Definición: Un árbol de expansión de un grafo G=(V, A) no dirigido y conexo es un subgrafo
  G’=(V, A’) conexo y sin ciclos.
• Ejemplo: los árboles de expansión en profundidad y en anchura de un grafo conexo. 
• En grafos con pesos, el costo del árbol de expansión es la suma de los costes de las aristas.

• Problema del árbol de expansión de costo mínimo:

       Dado un grafo ponderado no dirigido, encontrar el árbol de expansión de menor costo.

•          Problema: conectar todas las computadoras con el menor costo total.

•          Solución: algoritmos clásicos de Prim y Kruskal.