Árboles generadores minimales

ARBOLES GENERADORES
Orlando Arboleda Molina
Escuela de Ingenier´a de Sistemas y Computacion de
ı
´
La Universidad del Valle

16 de septiembre de 2008

Contenido

´
Arboles generadores
Algoritmo busqueda por profundidad
´
Algoritmo busqueda en anchura
´

´
Arboles generadores m´nimos
ı
Algoritmo de Prim
Algoritmo de Kruskal

Contenido

´
Arboles generadores
Algoritmobusqueda por profundidad
´
Algoritmo busqueda en anchura
´

´
Arboles generadores m´nimos
ı
Algoritmo de Prim
Algoritmo de Kruskal

Figura: Ejemplo de un grafo

Problema: Que rutas pueden ser cerradas de tal manera que
se pueda seguir viajando entre cualquier par de ciudades ?.

´
Arboles generadores (o recubridor)
´
Arboles generadores (o recubridor)
Sea G un grafo simple.Un arbol generador (o recubridor) de G
´
es un subgrafo de G que es un arbol y contiene todos los
´
vertice de G.
´

Figura: Ejemplo de un arbol generador
´

Ejemplo: El arbol anterior es un arbol generador del problema
´
´
original.

´
Arboles generadores (2)

Nota: Un grafo simple con un a rbol cobertor debe ser conexo,
´
puesto que hay un camino en el arbol cobertor entrecualquier
´
par de vertices.
´

Teorema 1
Un grafo simple es conexo si y solo si admite un arbol cobertor.
´
Los algoritmos mas usados para construir arboles generadores
son: Busqueda en profundidad y Busqueda en amplitud.
´
´

Contenido

´
Arboles generadores
Algoritmo busqueda por profundidad
´
Algoritmo busqueda en anchura
´

´
Arboles generadores m´nimos
ı
Algoritmo dePrim
Algoritmo de Kruskal

Algoritmo busqueda por profundidad
´

Idea: Elegir un ve rtice arbitrario como ra´z del a rbol. Formar un
´
ı
´
camino que comienza en ese ve rtice an adiendo sucesivamente
´
˜
vertices y aristas, siendo cada nueva arista incidente con el
´
ultimo vertice del camino y un ve rtice que no esta en el camino.
´
´
´
´
Si el camino no pasa por todos losvertices del grafo, retroceder
´
al penultimo vertice e intentar un nuevo camino iniciando en el.
´
´
´
Tambien llamado de vuelta atras o retroceso (en ingles,
´
´
´
backtacking) puesto que el algoritmo retorna a los vertices
´
visitados previamente para adicionarlos al camino.

Algoritmo busqueda por profundidad (2
´

Procedimiento Profundidad ( G: grafo conexo de vertices
v1 ,v2 , . . . , vn )
T := arbol que consta solo del vertice v1
visitar(v1 )
Fin Procedimiento
Procedimiento visitar (v : vertice de G)
Para cada vertice w adyacente a v y aun no en T
Adicionar vertice w y arista {v , w } a T
visitar (w )
Fin Para
Fin Procedimiento

Algoritmo busqueda por profundidad (3
´

Figura: Ejemplo de un arbol generador
´

Ejercicio: Construir un a rbolgenerador usando el algoritmo de
´
bu squeda por profundidad, a partir del grafo anterior iniciando
´
en el vertice a.

Contenido

´
Arboles generadores
Algoritmo busqueda por profundidad
´
Algoritmo busqueda en anchura
´

´
Arboles generadores m´nimos
ı
Algoritmo de Prim
Algoritmo de Kruskal

Algoritmo busqueda en anchura
´

Idea: Elegir un vertice arbitrario como ra´z delarbol. Luego
´
ı
´
anadir todas las aristas incidentes con ese vertice (nivel 1 del
˜
´
arbol). Para cada vertice del nivel 1, visitados en orden, anadir
´
´
˜
todos los vertices incidentes con el siempre que no formen
´
ciclos.
El procedimiento se repite hasta que se adicionen todos los
vertices.
´

Algoritmo busqueda en anchura (2
´

Procedimiento Anchura ( G: grafo conexo devertices
v1 , v2 , . . . , vn )
T := arbol que consta solo del vertice v1
L := lista vacia
Mientras L no este vacia
borrar el primer vertice v de L
Para cada vertice w adyacente a v
Si w no esta en L y no esta en T
anadir el vertice w al final de la lista L
˜
anadir el vertice w y la arista {v , w } a T
˜
Fin Si
Fin Para
Fin Mientras
Fin Procedimiento

Algoritmo busqueda en...