lunes, 7 de diciembre de 2009

Arboles Generadores

 Un árbol T, subgrafo de un grafo G que contenga todos los vértices de G se denómina Arbol Generador de G.

A esta característica general es posible agregar ciertos teoremas de modo de detallar aún más el alcance de la definición. Es asi como el Grafo que contiene a T debe ser conexo, pues de lo contrario no existiría un subgrafo que contuviera todos sus vértices.
En general un grafo G tendrá varios árboles generadores ,como el del ejemplo 1 el cual tiene a lo menos dos arboles generadores T1 yT2.
Algoritmos para hallar un árbol generador , que se base en el teorema de que el grafo G debe ser conexo, pueden ser los que se realizan a través de los métodos llamados buscar primero a lo ancho , buscar primero a lo largo y el de regreso al nivel anterior.

ARBOLES GENERADORES
Debido a que los arboles son estructuras mas simples de manejar que los grafos, es conveniente cuando tenemos un grafo conexo, construir un árbol que contenga todos los nodos: de esta forma es posible visitar todos los nodos con una estructura mas eficiente y donde es posible visitar todos los nodos con una estructura mas eficiente y donde es posible implementar de una forma mas directa los algoritmo para el manejo de la información.
Definición: un árbol generador T de un grafo conexo G un árbol que es subgrafo de G y que contiene todos los nodos.
un árbol generador es: T1=( ( a,b), (a,d),(b,c),(c,f),(d,e) ) El cual lo podríamos dibujar
También el árbol T2 es otro árbol generador T2= ( (b,a),(b,c),(b,c),(b,e),(c,f) )
El cual se puede representar como
Hay varias formas de crear los arboles generadores, dos de las mas comunes e importantes son las de los algoritmos.

No hay comentarios:

Publicar un comentario