Informacion

7.6 ARBOLES Y ARBOLES DE EXPANSIÓN
7.6.1 .- introducción
Unos de los grafos mas importantes son los grafos de árbol, y una de las formas mas especiales son los arboles de raíz junto con el árbol de análisis de las proposiciones , también son utilizados en los recursivos. Además de que se utilizan en muchos otros casos, por ejemplo en la computación se utiliza para la organización de lainformación de modo que se pueden efectuar operaciones de la información, también es fácil de utilizar para la organización de la información al momento de desglozarla. Redes de comunicación, esta se utiliza en todas las redes para acomodar la información.
7.6.2.- arboles libres
Existen dos grandes ramas de los arboles una de ellas son los arboles libres y la otra son los arboles de raíz, los arboleslibres son los que no están dirijidos, por todo lo contrario los arboles de raíz son los que están dirigidos a la información de la computación y de cualquier otro lugar que se ocupe.
Árbol libre: es un grafo sencillono dirigido también es conexo.
Demostración: se formula una demostración inductiva sean n=1 para la base. La hipótesis supone que si el árbol de k vértices debe de tener k-1 bordes. Y porlógica debe de ser un árbol con k+1 nodos y contiene k aristas, al igual que si se observa que cualquier árbol que tenga al menos 1 arista debe de contener 2 nodos con grado 1.

7.6.3.- arboles de expancion
Uno de los problemas mas importantes que esta muy asociados a una red presentada por grafos, esta serie de arboles de expansión debe de tener todos los nodos del grafo y algunas de susaristas, para asegurar su conectividad.
Definición:
Es un grafo convexo no dirigido G=(N,A) con un conjunto de nodos N que es un subgrafo de G, esto es un árbol aciclico y contiene N como nodos y A de aristas.
existen muchos enfoques para formar un árbol de expansión según el grafo dado , un enfoque consiste en ir eliminando los aristas asta que ya no quede ninguno de sus ciclos, si solo se eliminanlas aristas de los ciclos se convertirá en convexos y esto es realmente indispensable para crear un árbol.
Además un enfoque alterno es posiblemente mas eficiente para generar un árbol de expansión y para sacar el numero de sucesión que tiene es el n-1. Además un árbol que empiece con un nodo dera origen a un árbol cuya raíz sea v1, si se ignora el nodo raíz y la dirección del los nodos dirigidos esun árbol libre y la elaboración de un árbol libre debe de llevarlos BFS que incluyen los nodos v2, v5 y v6, con esto se supone que el árbol debe de ser adyacente para que con los arcos se vallan a parar en los nodos vq y v7.
También se puede obtener un árbol de expansión si se realiza una búsqueda en lo mas profundo de un grafo. Dado que los grafos dan lugar a los arboles de raiz. Acontinuacionde hablara de un árbol que fue realizado de uno en uno los nodos y que con el conjunto de estos se va ir quitando cada uno de las aristas de manera que se quede el árbol de una manera aciclica, los nodos se concideran como nodos en cada uno de los casos de la iteración.
Supóngase de nuevo que el grafo dado es el de la Figura 7.49a, y que el nodo inicial es v,. Inicialmente, Nodos contiene el nodovp y no se ha seleccionado ninguna arista. Comenzando en Vj, se desea seleccionar una arista que una a v} con algún otro nodo de Resto, que en este momento es el conjunto {v2, v3, v4, vs, v6, v?}. En este momento hay varias opciones posibles: las aristas {Vj, v2}, {Vj, v5) y {Vj, v6}. En este seguimiento se tomará la determinación basada en el orden numéricamente creciente de índices de nodos,hasta que se hayan seleccionado todas las aristas que preserven la aciclicidad del subgrafo. Por tanto, se selecciona v2 y la arista {Vj, v2}, dando lugar a los cambios Nodos = (vp v2} y Aristas = {(v,, v2}}. Hay que señalar que en la práctica es probable que se utilice un orden aleatorio de selección. A continuación se selecciona v5 y la arista {Vj, v5}, y después vg y la arista {vt, v6}. Llegados...