BOSQUE

Bosques y  componentes conexos

Un bosque es un conjunto de árboles o de otra manera podemos decir que un bosque es un grafo acíclico, de dice que el grafo es acíclico si no se tiene ningún ciclo simple.

La figura muestra un bosque, el cual está compuesto por tres árboles.

Un componente conexo es cada árbol que conforma al bosque.

Sea G un grafo un árbol abarcador de G es un grafo conexo que tienen los mismos vértices que G y no tiene ciclos.

A continuación se muestra los dos algoritmos para calcular el árbol abarcador de costo mínimo.

1. Algoritmo de Kruskal
2. Algoritmo de Prim

El primer algoritmo consiste en elegir las aristas de menor peso hasta conseguir el árbol de peso mínimo, en otras palabras podemos decir que este algoritmo busca un subconjunto de grafos que formando un árbol incluya a todos los vértices y el valor de los arcos sea mínimo

El segundo algoritmo consiste en ir borrando las aristas de mayor peso y que no sean aristas de separación.

Si tenemos un grafo G y calculamos el árbol abarcador atravéz de los dos algoritmos tendremos el mismo costo mínimo, en algunos casos se podrá tener el mismo árbol en ambos algoritmos pero en otros no.

Los siguientes link muestran ejemplos de cómo encontrar el árbol abarcador de costo mínimo atravéz de los dos algoritmos que ya conocemos.(Vicente, 2014)

BIBLIOGRAFÍA: 

Vicente, A. p. (21 de 05 de 2014). MATEMATICAS DISCRETAS. Recuperado el 21 de 05 de 2014, de LA M DISCRETA: http://lamdiscreta.wordpress.com/page/2/