arboles grafoas






ARBOLES GRAFOS

Profesora: Bachilleres:
Mónica Alvarado Pedro Cabeza
CI: V- 24.708.551
Leonardo Cermeño
CI: V- 20.683.860
ASIGNATURA: ESTRUCTURA DE DATOS María Pírela
CI: V- 21.066.570Gabriel Rojas
CI: V- 21.362.981
Víctor Fernández
CI: V- 24.8273233

II SEMESTRE DE INFORMATICA DIURNO.
INTRODUCCION
El origen de la teoría de grafos se remonta al siglo XVIII con el problema de los puentes de Königsberg, el cual consistía en encontrar un camino que recorriera los siete puentes del río pregel (54°42′12″N 20°30′56″E / 54.70333, 20.51556) en la ciudad de Königsberg, actualmenteKaliningrado, de modo que se recorrieran todos los puentes pasando una sola vez por cada uno de ellos. El trabajo de Leonhard Euler sobre el problema titulado Solutio problematis ad geometriam situs pertinentis, (La solución de un problema relativo a la geometría de la posición) en 1736, es considerado el primer resultado de la teoría de grafos. También se considera uno de los primeros resultadostopológicos en geometría (que no depende de ninguna medida). Este ejemplo ilustra la profunda relación entre la teoría de grafos y la topología.
Actualmente ha tenido mayor preponderancia en el campo de la informática, las ciencias de la computación y telecomunicaciones












ARBOLES GRAFOS
Un árbol es un grafo en el que cualesquiera dos vértices están conectadospor exactamente un camino. Un bosque es una unión disjunta de árboles. Un árbol a veces recibe el nombre de árbol libre.
Un árbol 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ñade alguna arista se forma un ciclo.
G es conexo y si se le quita alguna arista deja de ser conexo.
G es conexo yel grafo completo de 3 vértices  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.TIPOS DE ARBOL

1. Grafo unidireccional simple G es un bosque si no tiene ciclos simples.

2. Á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.


3. Árbol con raíz: Sellama así si cada vértice ha sido designado raíz, en cuyo caso las aristas tienen una orientació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; véase árbol (programación).

4. Á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}.

5. Árbol regular u homogéneo: Es un árbol en el que cada vértice tiene el mismo grado.
















































OPERACIONES COMUNES EN LOS ÁRBOLES

Enumerar todos los elementos.
Buscar un elemento.
Dado un nodo, listar los hijos (si loshay).
Borrar un elemento.
Eliminar un subárbol (algunas veces llamada podar).
Añadir un subárbol (algunas veces llamada injertar).
Encontrar la raíz de cualquier nodo.
Por su parte, la representación puede realizarse de diferentes formas. Las más utilizadas son:
Representar cada nodo como una variable en el heap, con punteros a sus hijos y a su padre.
Representar el árbol con un array donde...