Grafos

REPUBLICA BOLIVARIANA DE VENEZUELA.

MINISTERIO DEL PODER POPULAR PARA LA DEFENSA.

UNIVERSIDAD NACIONAL EXPERIMENTAL POLITECNICA DE

LA FUERZA ARMADA NACIONAL.

NUCLEO TRUJILLO.

























DATOS:

YOHANA DOS SANTOS

MARIA AGUILAR

SEMESTRE: V SECCION: 01

INGENIERIA EN SISTEMA



BETIJOQUE, 04 DE NOVIEMBRE DEL 2012ÁRBOLES (TEORÍA DE GRAFOS)
Árbol:
es el nombre que se le da a un grupo Versátil de estructuras de datos. Se pueden utilizar para implementar un número de interfaces abstractas, incluida la interfaz List, pero las aplicaciones en las que resultan más útiles emplean estructuras de ramas de árboles para representar alguna propiedad de los elementos de los datos o para optimizar ciertos métodos.Un árbol es un grafo en el que dos vértices cualesquiera están conectados por exactamente un camino. Un bosque es una unión disjunta de árboles. Un árbol a veces recibe el nombre de árbol libre.
DEFINICIONES:
Es un grafo simple unidireccional G que satisface alguna de las siguientes condiciones equivalentes:
• G es conexo y no tiene ciclos .
• G no tiene ciclos y, si se añadealguna arista se forma un ciclo.
• G es conexo y si se le quita alguna arista deja de ser conexo.
• G es conexo y el grafo completo de 3 vértices [pic] no es un menor de G.
• Dos vértices cualesquiera de G están conectados por un único camino simple.
Si G tiene muchos vértices, n, entonces las definiciones anteriores son también equivalentes a cualquiera de las siguientes condiciones:• G es conexo y tiene n − 1 aristas.
• G es conexo y sin ciclos.
• Cualesquiera 2 vértices están unidos por una única trayectoria.
Un grafo unidireccional simple G es un bosque si no tiene ciclos simples.
Un árbol es un grafo conexo y sin ciclos. Un árbol es un grafo simple pues los bucles son ciclos de longitud uno y un par de aristas paralelas originan un ciclo delongitud dos.
• Un árbol dirigido: Es un grafo dirigido que sería un árbol si no se consideraran las direcciones de las aristas. Algunos autores restringen la frase al caso en el que todas las aristas se dirigen a un vértice particular, o todas sus direcciones parten de un vértice particular.
• Un árbol con raíz: Si cada vértice ha sido designado raíz, en cuyo caso las aristas tienen unaorientación natural hacia o desde la raíz. Los árboles con raíz, a menudo con estructuras adicionales como orden de los vecinos de cada vértice, son una estructura clave en informática.
• Un árbol etiquetado: Es un árbol en el que cada vértice tiene una única etiqueta. Los vértices de un árbol etiquetado de n vértices reciben normalmente las etiquetas {1,2,..., n}.
• Un árbol regular uhomogéneo: es un árbol en el que cada vértice tiene el mismo grado.
Formalmente, podemos definir un árbol de la siguiente forma:
• Caso base: un árbol con sólo un nodo (es a la vez raíz del árbol y hoja).
• Un nuevo árbol a partir de un nodo [pic]y [pic]árboles [pic]de raíces [pic]con [pic]elementos cada uno, puede construirse estableciendo una relación padre-hijo entre [pic]y cada una delas raíces de los [pic]árboles. El árbol resultante de [pic]nodos tiene como raíz el nodo [pic], los nodos [pic]son los hijos de [pic]y el conjunto de nodos hoja está formado por la unión de los [pic]conjuntos hojas iníciales. A cada uno de los árboles [pic]se les denota ahora subárboles de la raíz.
Una sucesión de nodos del árbol, de forma que entre cada dos nodos consecutivos de la sucesión hayauna relación de parentesco, decimos que es un recorrido árbol. Existen dos recorridos típicos para listar los nodos de un árbol: primero en profundidad y primero en anchura. En el primer caso, se listan los nodos expandiendo el hijo actual de cada nodo hasta llegar a una hoja, donde se vuelve al nodo anterior probando por el siguiente hijo y así sucesivamente. En el segundo, por su parte,...