****** Teoría de Grafos & Árboles ******

Teoría Grafos :


Los Grafos  permiten expresar de una forma visualmente muy sencilla y efectiva las relaciones que se dan entre elementos, un grafo se representa gráficamente como un conjunto de puntos y estas unidos por lineas.
Un grafo es una terna G = (V,A,j ), en donde V y A son conjuntos finitos, y j es una aplicación que hace corresponder a cada elemento de A un par de elementos de V. Los elementos de V y de A se llaman, respectivamente, "vértices" y "aristas" de G, y j asocia entonces a cada arista con sus dos vértices.

• El conjunto V: son los puntos llamados vértice, los cuales conforman el grafo.
• El conjunto A: son las lineas llamadas aristas o arcos  que comunican los vertices entre ellas, si la arista carece de dirección se denota indistintamente {a, b} o {b, a}, siendo a y b los vértices que une, si {a ,b} es una arista, a los vértices a y b se les llama sus extremos.

Los datos contienen, en algunos casos, relacionesentre ellos que no es necesariamente jerárquica.

• Grafos No Dirigidos: son aquellos en los cuales los lados no están orientados (No    son flechas).

• Grafos Dirigidos: son aquellos en los cuales los lados están orientados con flechas. 

Teoría de Árboles:

Tienen una estructura dinámica que organiza información de forma jerárquica  con un único punto de entrada y una serie de caminos que van abriéndose en cada punto hacia sus sucesores ya sean elementos u objetos de información los cuales están relacionados entre si.

Las aplicaciones de los arboles binarios son muy variadas ya que se les puede utilizar para representar una estructura, el árbol se caracteriza porque  tiene una raíz y los dos que parten de el llamados nodo izquierdo y nodo derecho, algo muy importante saber es que los nodos tienen como máximo dos hijos

En un árbol binario todos sus subárboles son también árboles binarios. 

• Clasificación de los árboles binarios 

* Árbol binario distinto: es cuando se presentan dos estructuras diferentes.

* Árbol binario similar:   es cuando su información es diferente pero su estructura es                  similar.

* Árbol binario equivalentes: es cuando la información que con tiene los nodos son iguales  y cuando su estructura es idéntica.

* Árbol binario complementos: son aquellos arboles en los que todos sus nodos excepto los del ultimo nivel,tiene dos hijos; el subárbol izquierdo y el subárbol derecho.

• Busqueda de un árbol binario

El árbol binario de búsqueda es una estructura sobre la cual se pueden realizar eficientemente las operaciones de búsqueda, inserción y eliminación.

Para la búsqueda del árbol binario depende de un campo dado cuyos valores son distintos y deben estar ordenados para que su búsqueda sea eficaz.

• Recorridos de los Árboles

Recorrido Preorden: En el que se procesa el nodo y después se procesan recursivamente sus hijos.

Recorrido Postorden: Donde el nodo dado se procesa después de haber procesado recursivamente a sus hijos.

Recorrido Inorden: En este se procesa recursivamente el hijo izquierdo, luego se procesa el nodo actual y finalmente se procesa  recursivamente el hijo derecho.

Alexandra Longas
Ing. de Sistemas