Arboles Genaradores

Universidad Aut´noma de Chihuahua
o
Facultad de Ingenier´
ıa

Matem´ticas Discretas
a

Arboles Generadores.
Catedr´tico: Ing. Karla Bojorquez Guti´rrez.
a
e

Elaborado por:
Luis Angel Pereyra Villanueva 261804.
Dagoberto D´ Torres 265002.
ıaz
Eduardo L´pez Guevara 252145.
o
Fecha de entrega: Viernes 01 de Noviembre del 2013

1

1.

Introducci´n
o

En una ciudad almenos 5 carreteras deben limpiarse de nieve para poder asegurar que
hay un camino entre dos ciudades cualesquiera. La figura de la derecha muestra uno de los
conjuntos de carreteras, el subgrafo que representa estas carreteras es un arbol, puesto que
´
es conexo y tiene seis v´rtices y cinco aristas.
e

Definici´n: Sea G un grafo simple. Un ´rbol generador de G es un subgrafo
o
a
de G que esun ´rbol y contiene todos los v´rtices de G.
a
e
Esto nos dice que todo grafo simple que admite un arbol generador necesariamente es
´
conexo, puesto que existe un camino en el ´rbol generado entre dos v´rtices cualesquiera.
a
e
El reciproco tambi´n es cierto, esto es, todo grafo simple conexo tiene un ´rbol generador.
e
a
Teorema: Un grafo simple es conexo si, y solo si, admite un´rbol generador.
a
Suponemos que el grafo G es conexo, pero G no es un ´rbol y necesariamente debe
a
contener al menos un ciclo. Si eliminamos una arista de dichos ciclos, el subgrafo resultante que contiene a todos los v´rtices de G seguir´ siendo conexo. Si el subgrafo resultante
e
a
todav´ no es un arbol, es porque tiene otro ciclo, por lo cual se deber´ repetir el proceso
ıa
´
a
hastaque no queden ciclos. Este proceso es finito ya que el numero de aristas del grafo
es finito. Asi el resultado ser´ un arbol porque ser´ un grafo conexo y in ciclos, tambi´n
a
´
a
e
ser´ un arbol generador porque contiene todos los v´rtices de G.
a
´
e
El siguiente grafo es conexo, pero no es un arbol porque contiene ciclos.
´

2

Quitando la arista (a, e). De este modo eliminamos elciclo y el subgrafo resultante
todav´ es conexo y sigue conteniendo todos los v´rtices del grafo G.
ıa
e

Seguidamente quitamos la arista (e, f) para eliminar otro ciclo.

Finalmente, quitamos la arista (c, o) para obtener un grafo simple sin circuitos y as´ obı
tener un subgrafo que es a su vez un arbol generador, puesto que contiene todos los v´rtices
´
e
del grafo G.

3Construcci´n del arbol generador eliminando las aristas que forman ciclos:
o
´

2.

B´squeda en profundidad
u

El algoritmo procedente del teorema 1 no es suficiente, ya que se requiere identificar los
circuitos simples, por lo que es mas practico construir arboles generadores e ir a˜adiendo
n
aristas haciendo uso de dos algoritmos. El primero es de los algoritmos es usar una b´squeda
u
deprofundidad en donde construimos un ´rbol con ra´ y el ´rbol generador ser´ el grafo
a
ız
a
a
subsecuente. El siguiendo el siguiente procedimiento:
1. Escogemos arbitrariamente un v´rtice como la ra´ del grafo
e
ız
2. Formamos un camino tan largo como sea posible a˜adiendo aristas y v´rtices, en
n
e
donde las nuevas aristas son incidentes con el ultimo v´rtice del camino y el nuevo
´
ev´rtice se encuentra en el camino.
e
Nota: Si el camino m´s largo propuesto pasa por todos los v´rtices, el ´rbol generador
a
e
a
es dicho camino
3. Regresamos al pen´ltimo v´rtice del camino y si se puede formamos un nuevo camino
u
e
que pase por los v´rtices siempre que esto sea posible, en caso contrario retrocedemos
e
al v´rtice anterior y se hace lo mismo con este.
e
4. Serepite el proceso, comenzando en el ultimo v´rtice visitad de manera que vamos
´
e
retrocediendo mientras construimos caminos de longitud tan grande como sea posible,
ya que es un grafo con un n´mero finitos de aristas y es conexo, llegamos a generar
u
un ´rbol recubridor. Cada v´rtice final de un camino en alguna etapa del algoritmo
a
e
de b´squeda de profundidad es una hoja y cada v´rtice...