Grafos Un grafo en el ámbito de las ciencias de la computación es una estructura de datos, en concreto un tipo abstracto de datos (TAD), que consiste en un conjunto de nodos (también llamados vértices) y un conjunto de arcos (aristas) que establecen relaciones entre los nodos. El concepto de grafo TAD desciende directamente del concepto matemático de grafo. Informalmente se define como G = (V, E), siendo los elementos de V los vértices, y los elementos de E, las aristas (edges en inglés). Formalmente, un grafo, G, se define como un par ordenado, G = (V, E), donde V es un conjunto finito y E es un conjunto que consta de dos elementos de V. Un grafo está formado por un conjunto de nodos(o vértices) y un conjunto de arcos. Cada arco en un grafo se especifica por un par de nodos. TERMINOLOGÍA *.-Al número de nodos del grafo se le llama orden del grafo. *.-Un grafo nulo es un grafo de orden 0 (cero). *.-Dos nodos son adyacentes si hay un arco que los une. *.-En un grafo dirigido, si A es adyacente de B, no necesariamente B es adyacente de A *.-Camino es una secuencia de uno o mas arcos que conectan dos nodos. *.-Un grafo se denomina conectado cuando existe siempre un camino que une dos nodos cualesquiera y desconectado en caso contrario. *.-Un grafo es completo cuando cada nodo esta conectado con todos y cada uno de los nodos restantes. *.-El camino de un nodo así mismo se llama ciclo. Grafos dirigidos Un grafo dirigido G, también llamado digrafo o grafo, es lo mismo que un multigrafo, solo que cada arista e de G tiene una dirección asignada o , en otras palabras ,cada arista e está identificada por un par ordenado (u,v) de nodos G en vez del par desordenado [u.v]. Suponga que G es un grafo dirigido con una arista dirigida e=(u,v).Entonces e también se llama arco . Más aún se usa la siguiente terminología: (1) e empieza en u y termina en v (2) u es el origen o punto inicial de e ,y v es el destino o punto terminal de e . (3) u es un predecesor de v y v es un sucesor o vecino de u (4) u es adyacente hacia v y v es adyacente a u El grado de salida de un nodo u de G, escrito gradsal(u), es el número de aristas que empiezan en u similarmente , el grado de entrada u, escrito gradent(u), es el número de aristas que terminan en u. Un nodo u se llama fuente si tiene un grado de salida positivo y un grado de entrada nulo . Similarmente u se le llama sumidero si tiene un grado de salida nulo y un grado de entrada positivo. GRAFOS Y MULTIGRAFOS Un grafo G consiste en dos cosas: (1) Un conjunto V de elementos llamados nodos (o puntos o vértices) (2) Un conjunto E de aristas tales que cada arista e de E esta identificada por un único (desordenado) par [u,v] de nodos de V, denotado por e-[v,u]. A veces denotamos un grafo escribiendo G=(V,E) Suponga que e =[u,v]. entonces los nodos u y v se llaman extremos de e, y u y v se dice que son nodos adyacentes o vecinos. El grado de un nodo u, escrito grad(u), es el número de artistas que contienen a u.si grad(u)= 0, o sea, si u no pertenece a ninguna arista--- entonces se dice que u es un nodo aislado. Un camino P de longitud n desde un nodo u se define como la secuencia de n +1 nodos.

Arboles Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos. También se suele dar una definición recursiva: un árbol es una estructura en compuesta por un dato y varios árboles. Esto son definiciones simples. Pero las características que implican no lo son tanto. Definiremos varios conceptos. En relación con otros nodos: Nodo hijo: cualquiera de los nodos apuntados por uno de los nodos del árbol. En el ejemplo, 'L' y 'M' son hijos de 'G'. Nodo padre: nodo que contiene un puntero al nodo actual. En el ejemplo, el nodo 'A' es padre de 'B', 'C' y 'D'. Los árboles con los que trabajaremos tienen otra característica importante: cada nodo sólo puede ser apuntado por otro nodo, es decir, cada nodo sólo tendrá un padre. Esto hace que estos árboles estén fuertemente jerarquizados, y es lo que en realidad les da la apariencia de árboles. En cuanto a la posición dentro del árbol: Nodo raíz: nodo que no tiene padre. Este es el nodo que usaremos para referirnos al árbol. En el ejemplo, ese nodo es el 'A'. Nodo hoja: nodo que no tiene hijos. En el ejemplo hay varios: 'F', 'H', 'I', 'K', 'L', 'M', 'N' y 'O'. Nodo rama: aunque esta definición apenas la usaremos, estos son los nodos que no pertenecen a ninguna de las dos categorías anteriores. En el ejemplo: 'B', 'C', 'D', 'E', 'G' y 'J'. Otra característica que normalmente tendrán nuestros árboles es que todos los nodos contengan el mismo número de punteros, es decir, usaremos la misma estructura para todos los nodos del árbol. Esto hace que la estructura sea más sencilla, y por lo tanto también los programas para trabajar con ellos. Tampoco es necesario que todos los nodos hijos de un nodo concreto existan. Es decir, que pueden usarse todos, algunos o ninguno de los punteros de cada nodo. Un árbol en el que en cada nodo o bien todos o ninguno de los hijos existe, se llama árbol completo. En una cosa, los árboles se parecen al resto de las estructuras que hemos visto: dado un nodo cualquiera de la estructura, podemos considerarlo como una estructura independiente. Es decir, un nodo cualquiera puede ser considerado como la raíz de un árbol completo. Existen otros conceptos que definen las características del árbol, en relación a su tamaño: Orden: es el número potencial de hijos que puede tener cada elemento de árbol. De este modo, diremos que un árbol en el que cada nodo puede apuntar a otros dos es de orden dos, si puede apuntar a tres será de orden tres, etc. Grado: el número de hijos que tiene el elemento con más hijos dentro del árbol. En el árbol del ejemplo, el grado es tres, ya que tanto 'A' como 'D' tienen tres hijos, y no existen elementos con más de tres hijos. Nivel: se define para cada elemento del árbol como la distancia a la raíz, medida en nodos. El nivel de la raíz es cero y el de sus hijos uno. Así sucesivamente. En el ejemplo, el nodo 'D' tiene nivel 1, el nodo 'G' tiene nivel 2, y el nodo 'N', nivel 3. Altura: la altura de un árbol se define como el nivel del nodo de mayor nivel. Como cada nodo de un árbol puede considerarse a su vez como la raíz de un árbol, también podemos hablar de altura de ramas. El árbol del ejemplo tiene altura 3, la rama 'B' tiene altura 2, la rama 'G' tiene altura 1, la 'H' cero, etc. Los árboles de orden dos son bastante especiales, de hecho les dedicaremos varios capítulos. Estos árboles se conocen también como árboles binarios. Frecuentemente, aunque tampoco es estrictamente necesario, para hacer más fácil moverse a través del árbol, añadiremos un puntero a cada nodo que apunte al nodo padre. De este modo podremos avanzar en dirección a la raíz, y no sólo hacia las hojas. Es importante conservar siempre el nodo raíz ya que es el nodo a partir del cual se desarrolla el árbol, si perdemos este nodo, perderemos el acceso a todo el árbol. Los árboles tienen aplicaciones en diferentes ámbitos como por ejemplo: Diseño de compiladores, sistemas expertos, sistemas evolutivos, sistemas conscientes, manejo de directorios por ejemplo Mi PC dentro de Windows. Representación de un árbol genealógico. índices de bases de datos y mucha más Sin lugar tiene muchas aplicaciones, aunque su implementación no es tan usada como las base de datos tradicionales, pero actualmente existen modelos mediante los cuales un árbol puede ser representado en una lista dinámica simplemente o doblemente ligada, este modelo se presentará posteriormente. ¿Qué pueden almacenar? Si los árboles se implantan en estructuras de datos dinámicas, pueden contener los que se requiera, aunque también se pueden implantar en arreglos estáticos. Por ejemplo si se usa el lenguaje C y se opta por estructuras dinámicas en especial por la lista doblemente ligada, se puede definir un objetos llamado nodo de la siguiente forma: class nodo { public: //A continuacion los datos necesario para la propuesta(tonahtiu,2009) tipo de implantacion int padre, id; nodo *anterior, *siguiente; // A continuación los datos u objetos que se quieran almacenar en nodo int algun_dato; }; Como se puede apreciar en el programa anterior de agrega el dato algun_dato se aquí se pueden definir cualquier tipo y cantidad de datos que se requieran o bien otros objetos. Por lo cual se puede adaptar perfectamente a las necesidades del problema. ¿Cómo se pueden implantar? Existen tantas manera de representar estructuras de árbol como ideas surjan, por lo cual aquí solo se presenta una propuesta que considero que es sencilla y sirven para árboles de diversos niveles, grados de árbol y que puede cargarse en una lista simplemente ligada, misma que ya se ha presentado. http://www.youtube.com/watch?v=R06UpamwpgA