Arboles Generadores

Arboles Generadores

Def.: 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.

5.6.4 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.


Mis sitios nuevos:
Emprendedores
Politica de Privacidad