UNIDAD 3. ESTRUCTURAS NO LINEALES


COMPETENCIA ESPECIFICA:
  • Aplicar las principales estructuras de datos no lineales

Para el examen del dia viernes 4 de mayo consultar los siguientes archivos:

(Solo Tema de Arboles hasta recorridos)

ESTRUCTURAS DE DATOS NO LINEALES
  • ESTRUCTURAS NO LINEALES: A las estructuras de datos no lineales se les llama tbié tt ddt lti l dtambién estructuras de datos multienlazadas.
● Cada elemento puede estar enlazado a cualquier otro componentes.


ARBOLES
El árbol binario de búsqueda con su estructura en árbol permite que cada nodo apunte a otros dos nodos: uno que le precede en la lista y otro que lo sigue. Los nodos apuntados pueden ser cualesquiera de la lista siempre que satisfagan esta regla básica: El nodo a la izquierda contiene un valor más pequeño que el nodo que el nodo que le apunta y el nodo a la derecha contiene un valor más grande.
Los arboles representan la estructura no lineales y dinámica de datos. Dinámica puesto que la estructura de árbol puede cambiar durante la ejecución de un programa. No lineales puesto que a cada elemento del árbol puede seguirle varios elementos.
ARBOLES GENERALES
Árbol se define como una estructura jerárquica de forma descendente que se utiliza para almacenar información para su posterior procesamiento.
Gráficamente pueden representarse una estructura de árbol de diferentes formas y todas ellas son equivalentes, entre ellas tenemos:
• Diagrama de Venn• Anidación de paréntesis
• Notación decimal de Dewey
• Notación identada
• Gráficas (grafos) Arboles generales y binarios Otra definición de árbol general sería, estructura de datos representada con nodos y diferentes cantidades sucesiones.
REPRESENTACION EN MEMORIA DE ARBOLES
Existen dos formas de representar un Árbol en Memoria:
1- Mediante Listas Enlazadas: Utilizando la firma de las listas lineales. Los Nodos del árbol binario serán representados como registros que contendrán como mínimo tres campos. En un campo se almacenará la información del nodo y los dos campos restantes se utilizarán para apuntar los arboles izquierdo y derecho respectivamente del nodo en cuestión.

2- Representación Secuencial: Se utiliza un arreglo simple en el cual la raíz ocupara la posición uno y sus hijos estarán en la posición 2*k para el hijo izquierdo y 2*k+1 para el hijo derecho
Ejem:
Ejem.png

external image placeholder?w=NaN&h=NaN
|| || ||


La representación y terminología de los árboles se realiza con las típicas notaciones de las relaciones familiares en los árboles genealógicos: padre, hijo, hermano, ascendente, descendiente, etc.
TERMINOLOGÍA DEL ARBOL GENERAL:
RAIZ DEL ÁRBOL: Todos los árboles que no están vacíos tienen un único nodo raíz. Todos los demás elementos o nodos se derivan o descienden de él. El nodo raíz no tiene padre, es decir, no es el hijo de ningún elemento.
NODO: Son los vértices o elementos del árbol.
NODO TERMINAL U HOJA: Es aquel que no contiene ningún subárbol.
A cada nodo que no es hoja se asocia uno o varios subárboles llamados descendientes o hijos. De igual forma, cada nodo tiene asociado un antecesor o ascendiente llamado padre.
Los nodos de un mismo padre se llaman Hermanos.
Los nodos con uno o dos subárboles no son hojas ni raíz, se llaman Nodos Interiores o Internos.
Una colección de dos o más árboles se llama bosque.
Todos los nodos tienen un solo padre (excepto la raíz) que no tiene padre.
Se denomina camino el enlace entre dos nodos consecutivos, y rama es un camino que termina en una hoja.
Cada nodo tiene asociado un número de nivel que se determina por la longitud del camino desde el raíz al nodo específico.
La altura o profundidad de un árbol es el número máximo de nodos de una rama. Equivale al nivel más alto de los nodos más 1.
Se denomina recorrido de un árbol el proceso que permite acceder una sola vez a cada uno de los nodos del árbol. Cuando un árbol se recorre, el conjunto completo de nodos se examina.
Existen muchos modos para recorrer un árbol binario. Por ejemplo existen seis diferentes recorridos generales en un árbol binario simétricos dos a dos.
Los algoritmos de recorrido de un árbol binario representan tres tipos de actividades comunes:
• Visitar el nodo raíz
• Recorrer el subárbol izquierdo
• Recorrer el subárbol derecho
Estas tres acciones repartidas en diferentes órdenes proporcionan los diferentes recorridos del árbol. Los más frecuentes tienen siempre en común recorrer primero el subárbol izquierdo y luego el subárbol derecho. Los algoritmos anteriores se llaman pre -orden, post-orden, in-orden y su nombre refleja el momento en que se visita el nodo raíz.
PRE-ORDEN:Una solución, que minimiza en muchos casos el espacio de búsqueda sería disponer los nodos en el arreglo a partir del recorrido en pre orden del árbol, con lo cual se garantiza que una vez ubicado el índice del padre, los hijos estarán siempre en posiciones posteriores en el arreglo. En muchos casos se aprecia que para muchos nodos, sus hijos quedan dispuestos en el arreglo a continuación de él. Aquí el tiempo de ejecución continua siendo de orden n.
IN-ORDEN: También llamado orden simétrico (aunque este nombre sólo cobra significado en los árboles binarios) consiste en recorrer en primer lugar A1, luego la raíz y luego cada uno de los hijos A2... Ak en orden simétrico.
POST-ORDEN: También llamado orden posterior consiste en recorrer en primer cada uno de los hijos A1, A2 ... Ak en orden posterior y por último la raíz.
BALANCEO DE ÁRBOLES BINARIOS


La idea central es realizar reacomodos o balanceos, después de inserciones o eliminaciones de elementos. Estos árboles también reciben el nombre de AVL en honor a sus inventores, dos matemáticos rusos, G. M. Adelson-Velskii y E. M. Landis.
En un árbol balanceado se debe cumplir la siguiente condición: “Para todo nodo T del árbol, la altura de los subárboles izquierdo y derecho no deben diferir en más de una unidad”.


Balanceo.jpg






GRAFOS
Es un diagrama que consiste de puntos (llamados nodos) unidos por líneas (llamadas arcos). Cada arco en un grafo se especifica por medio de un par de nodos.


Grafo.jpg




Un grafo es un objeto matemático que se utiliza para representar circuitos, redes, etc. Los grafos son muy utilizados en computación, ya que permiten resolver problemas muy complejos.
El estudio de grafos es una rama de la algoritmia muy importante.
TIPOS DE GRAFOS
LAZO: Cuando un arco sale y regresa al mismo nodo sin tocar otro nodo diferente.
Lazo.jpg




LADOS PARALELOS: Cuando 2 arcos salen y ambos llegan a otro nodo.
Lado.jpg




GRAFO SIMPLE: Es aquel grafo que no tiene ni lazos, ni lados paralelos.
Simple.jpg




REPRESENTACION DE GRAFOS EN MEMORIA
Un camino de longitud n de V a W es una sucesión de lados que va de V a W y la cual tiene n lados distintos entre sí.
Un camino simple de longitud n de V a W es una de la forma (V0, V1, V2...Vn) en donde V0=V y Vn =W,y VV0,V1,Vn son distintos entre sí.
Un circuito o ciclo es un camino de V a V.
Un circuito simple es un circuito de la forma: (V0, V1, V2...Vn) en donde V0=Vn y V0, V1...Vn-1 son distintos entre sí.
Memoria.jpg




De acuerdo a la figura anterior se tiene:
SUCESION DE LADOS
¿CAMINO?
¿CAMINO SIMPLE?
¿CIRCUITO?
¿CIRCUITO SIMPLE?
(a,b,d,c,b,a)
NO
NO
NO
NO
(f,e,b,d,c,b,a)
SI
NO
NO
NO
(f,e,b,d)
SI
SI
NO
NO
(b,f,e,b,d,c,b)
SI
NO
SI
NO
(e,f,b,e)
SI
NO
SI
NO



CLASES PARA LA IMPLEMENTACION DE GRAFOS


CIRCUITO DE HAMILTON: Es cuando se inicie en un nodo y termina en el mismo pasando exactamente una vez por cada nodo.
CIRCUITO DE VENN EULER: Este circuito se da en grafos donde se realiza un camino donde se puede pasar solo una vez por cada arco.
El factor de peso o Ponderación se da en un grafo en el cual hay datos asociados con un arco.


INTEGRANTES DE EQUIPO:

  • ERIKA ESCARCEGA RODRIGUEZ
    • SANDRA LIZZETH LOPEZ ALAVEZ
      • MINERVA MATLALCUATZI CRUZ
        • ALEJANDRO VAZQUEZ MUÑOZ
          • VIRIDIANA XOCHITIOTZI CUATECONTZI
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><<
_

Equipo 3 (El Mejor)

Josue Sanchez Zempoaltecatl

Miguel Nazaret Flores Arenas



¿Qué es una estructura no lineal?

Es una estructura donde se tienen relaciones no lineales y no secuenciales, se pueden encontrar colecciones no ordenadas de elementos del mismo tipo, donde no hay repeticiones; entonces una estructura de datos no lineales, se caracteriza por no existir una relación de sus elementos, es decir que un elemento puede estar con cero, uno o mas elementos.
Las estructuras no lineales de datos más generales son los árboles donde no existe ninguna relación de orden Predefinida.
Esta estructura se usa principalmente para representar datos con una relación jerárquica entre sus elementos, como por ejemplo registros, árboles genealógicos y tablas de contenidos.


Tipos de estructuras no lineales

  • Arboles
  • Grafos



Árbol


ž 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.

ARBOL.png



      • Nodo hijo:** cualquiera de los nodos apuntados por uno de los nodos del árbol. En el ejemplo, 'L' y 'M' son hijos de 'G'.

UNIDAD 3. ESTRUCTURAS NO LINEALES


COMPETENCIA ESPECIFICA:
  • Aplicar las principales estructuras de datos no lineales

Para el examen del dia viernes 4 de mayo consultar los siguientes archivos:

(Solo Tema de Arboles hasta recorridos)

ESTRUCTURAS DE DATOS NO LINEALES
  • ESTRUCTURAS NO LINEALES: A las estructuras de datos no lineales se les llama tbié tt ddt lti l dtambién estructuras de datos multienlazadas.
● Cada elemento puede estar enlazado a cualquier otro componentes.


ARBOLES
El árbol binario de búsqueda con su estructura en árbol permite que cada nodo apunte a otros dos nodos: uno que le precede en la lista y otro que lo sigue. Los nodos apuntados pueden ser cualesquiera de la lista siempre que satisfagan esta regla básica: El nodo a la izquierda contiene un valor más pequeño que el nodo que el nodo que le apunta y el nodo a la derecha contiene un valor más grande.
Los arboles representan la estructura no lineales y dinámica de datos. Dinámica puesto que la estructura de árbol puede cambiar durante la ejecución de un programa. No lineales puesto que a cada elemento del árbol puede seguirle varios elementos.
ARBOLES GENERALES
Árbol se define como una estructura jerárquica de forma descendente que se utiliza para almacenar información para su posterior procesamiento.
Gráficamente pueden representarse una estructura de árbol de diferentes formas y todas ellas son equivalentes, entre ellas tenemos:
• Diagrama de Venn• Anidación de paréntesis
• Notación decimal de Dewey
• Notación identada
• Gráficas (grafos) Arboles generales y binarios Otra definición de árbol general sería, estructura de datos representada con nodos y diferentes cantidades sucesiones.
REPRESENTACION EN MEMORIA DE ARBOLES
Existen dos formas de representar un Árbol en Memoria:
1- Mediante Listas Enlazadas: Utilizando la firma de las listas lineales. Los Nodos del árbol binario serán representados como registros que contendrán como mínimo tres campos. En un campo se almacenará la información del nodo y los dos campos restantes se utilizarán para apuntar los arboles izquierdo y derecho respectivamente del nodo en cuestión.

2- Representación Secuencial: Se utiliza un arreglo simple en el cual la raíz ocupara la posición uno y sus hijos estarán en la posición 2*k para el hijo izquierdo y 2*k+1 para el hijo derecho
Ejem:
Ejem.png

external image placeholder?w=NaN&h=NaN
|| || ||

La representación y terminología de los árboles se realiza con las típicas notaciones de las relaciones familiares en los árboles genealógicos: padre, hijo, hermano, ascendente, descendiente, etc.
TERMINOLOGÍA DEL ARBOL GENERAL:
RAIZ DEL ÁRBOL: Todos los árboles que no están vacíos tienen un único nodo raíz. Todos los demás elementos o nodos se derivan o descienden de él. El nodo raíz no tiene padre, es decir, no es el hijo de ningún elemento.
NODO: Son los vértices o elementos del árbol.
NODO TERMINAL U HOJA: Es aquel que no contiene ningún subárbol.
A cada nodo que no es hoja se asocia uno o varios subárboles llamados descendientes o hijos. De igual forma, cada nodo tiene asociado un antecesor o ascendiente llamado padre.
Los nodos de un mismo padre se llaman Hermanos.
Los nodos con uno o dos subárboles no son hojas ni raíz, se llaman Nodos Interiores o Internos.
Una colección de dos o más árboles se llama bosque.
Todos los nodos tienen un solo padre (excepto la raíz) que no tiene padre.
Se denomina camino el enlace entre dos nodos consecutivos, y rama es un camino que termina en una hoja.
Cada nodo tiene asociado un número de nivel que se determina por la longitud del camino desde el raíz al nodo específico.
La altura o profundidad de un árbol es el número máximo de nodos de una rama. Equivale al nivel más alto de los nodos más 1.
Se denomina recorrido de un árbol el proceso que permite acceder una sola vez a cada uno de los nodos del árbol. Cuando un árbol se recorre, el conjunto completo de nodos se examina.
Existen muchos modos para recorrer un árbol binario. Por ejemplo existen seis diferentes recorridos generales en un árbol binario simétricos dos a dos.
Los algoritmos de recorrido de un árbol binario representan tres tipos de actividades comunes:
• Visitar el nodo raíz
• Recorrer el subárbol izquierdo
• Recorrer el subárbol derecho
Estas tres acciones repartidas en diferentes órdenes proporcionan los diferentes recorridos del árbol. Los más frecuentes tienen siempre en común recorrer primero el subárbol izquierdo y luego el subárbol derecho. Los algoritmos anteriores se llaman pre -orden, post-orden, in-orden y su nombre refleja el momento en que se visita el nodo raíz.
PRE-ORDEN:Una solución, que minimiza en muchos casos el espacio de búsqueda sería disponer los nodos en el arreglo a partir del recorrido en pre orden del árbol, con lo cual se garantiza que una vez ubicado el índice del padre, los hijos estarán siempre en posiciones posteriores en el arreglo. En muchos casos se aprecia que para muchos nodos, sus hijos quedan dispuestos en el arreglo a continuación de él. Aquí el tiempo de ejecución continua siendo de orden n.
IN-ORDEN: También llamado orden simétrico (aunque este nombre sólo cobra significado en los árboles binarios) consiste en recorrer en primer lugar A1, luego la raíz y luego cada uno de los hijos A2... Ak en orden simétrico.
POST-ORDEN: También llamado orden posterior consiste en recorrer en primer cada uno de los hijos A1, A2 ... Ak en orden posterior y por último la raíz.
BALANCEO DE ÁRBOLES BINARIOS


La idea central es realizar reacomodos o balanceos, después de inserciones o eliminaciones de elementos. Estos árboles también reciben el nombre de AVL en honor a sus inventores, dos matemáticos rusos, G. M. Adelson-Velskii y E. M. Landis.
En un árbol balanceado se debe cumplir la siguiente condición: “Para todo nodo T del árbol, la altura de los subárboles izquierdo y derecho no deben diferir en más de una unidad”.


Balanceo.jpg






GRAFOS
Es un diagrama que consiste de puntos (llamados nodos) unidos por líneas (llamadas arcos). Cada arco en un grafo se especifica por medio de un par de nodos.


Grafo.jpg




Un grafo es un objeto matemático que se utiliza para representar circuitos, redes, etc. Los grafos son muy utilizados en computación, ya que permiten resolver problemas muy complejos.
El estudio de grafos es una rama de la algoritmia muy importante.
TIPOS DE GRAFOS
LAZO: Cuando un arco sale y regresa al mismo nodo sin tocar otro nodo diferente.
Lazo.jpg




LADOS PARALELOS: Cuando 2 arcos salen y ambos llegan a otro nodo.
Lado.jpg




GRAFO SIMPLE: Es aquel grafo que no tiene ni lazos, ni lados paralelos.
Simple.jpg




REPRESENTACION DE GRAFOS EN MEMORIA
Un camino de longitud n de V a W es una sucesión de lados que va de V a W y la cual tiene n lados distintos entre sí.
Un camino simple de longitud n de V a W es una de la forma (V0, V1, V2...Vn) en donde V0=V y Vn =W,y VV0,V1,Vn son distintos entre sí.
Un circuito o ciclo es un camino de V a V.
Un circuito simple es un circuito de la forma: (V0, V1, V2...Vn) en donde V0=Vn y V0, V1...Vn-1 son distintos entre sí.
Memoria.jpg




De acuerdo a la figura anterior se tiene:
SUCESION DE LADOS
¿CAMINO?
¿CAMINO SIMPLE?
¿CIRCUITO?
¿CIRCUITO SIMPLE?
(a,b,d,c,b,a)
NO
NO
NO
NO
(f,e,b,d,c,b,a)
SI
NO
NO
NO
(f,e,b,d)
SI
SI
NO
NO
(b,f,e,b,d,c,b)
SI
NO
SI
NO
(e,f,b,e)
SI
NO
SI
NO



CLASES PARA LA IMPLEMENTACION DE GRAFOS


CIRCUITO DE HAMILTON: Es cuando se inicie en un nodo y termina en el mismo pasando exactamente una vez por cada nodo.
CIRCUITO DE VENN EULER: Este circuito se da en grafos donde se realiza un camino donde se puede pasar solo una vez por cada arco.
El factor de peso o Ponderación se da en un grafo en el cual hay datos asociados con un arco.


INTEGRANTES DE EQUIPO:

  • ERIKA ESCARCEGA RODRIGUEZ
    • SANDRA LIZZETH LOPEZ ALAVEZ
      • MINERVA MATLALCUATZI CRUZ
        • ALEJANDRO VAZQUEZ MUÑOZ
          • VIRIDIANA XOCHITIOTZI CUATECONTZI
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><<
_

Equipo 3 (El Mejor)


Josue Sanchez Zempoaltecatl

Miguel Nazaret Flores Arenas





¿Qué es una estructura no lineal?

Es una estructura donde se tienen relaciones no lineales y no secuenciales, se pueden encontrar colecciones no ordenadas de elementos del mismo tipo, donde no hay repeticiones; entonces una estructura de datos no lineales, se caracteriza por no existir una relación de sus elementos, es decir que un elemento puede estar con cero, uno o mas elementos.
Las estructuras no lineales de datos más generales son los árboles donde no existe ninguna relación de orden Predefinida.
Esta estructura se usa principalmente para representar datos con una relación jerárquica entre sus elementos, como por ejemplo registros, árboles genealógicos y tablas de contenidos.


Tipos de estructuras no lineales

  • Arboles
  • Grafos



Árbol


ž 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.

ARBOL.png



      • 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'.


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'.


Un árbol en el que en cada nodo o bien todos o ninguno de los hijos existe, se llama árbol completo



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.

Árboles generales

Intuitivamente el concepto de árbol implica una estructura en la que los datos se organizan de modo que los elementos de información están relacionados entre si a través de ramas. El árbol genealógico es el ejemplo típico más representativo del concepto de árbol general.

Árboles binarios

Es un árbol en el que ningún nodo puede tener mas de dos subárboles. En un árbol binario, cada nodo puede tener cero, uno o dos hijos (subárboles). Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho.

Operaciones en árboles binarios



ž Determinar su altura

ž Determinar su número de elementos

ž Hacer una copia

ž Visualizar el árbol binario en pantalla o en impresora

ž Determinar si dos árboles binarios son idénticos

ž Borrar (eliminar el árbol)

ž Si es un árbol de expresión, evaluar la expresión

ž Si es un árbol de expresión, obtener la forma de paréntesis de la expresión.





GRAFOS

Son estructuras de datos más generales que los árboles.

•Permiten modelar relaciones no necesariamente jerárquicas entre elementos de un conjunto.
•Se utilizan para representar mapas de rutas, organización de procesos, espacios de búsqueda para juegos, circuitos lógicos, etc.

Sin_título.png




Tipos de grafos

Grafo completo:

•Dos vértices diferentes cualesquiera del conjunto V son adyacentes.

Sin_título2.png



Grafo conexo:
•Para cualquier par de vértices v, w del conjunto V, existe una cadena que los une.
Grafo fuertemente conexo:
•Para cualquier par de vértices v, w del conjunto V, existe una camino que vaya de v a w.

Sin_título3.png


Grafo planar:
•Es posible dibujarlo en un plano sin que se crucen los arcos.
•Problema típico:
•3 casas y 3 servicios.
•Se trata de establecer si es posible llevar las tuberías de agua, gas y electricidad, sobre un mismo plano, a 3 casas vecinas.
•El problema se reduce a determinar si el grafo que representa la solución es planar.
•Vértices: casas y servicios.
•Arcos: tuberías.

Sin_título4.png

Grafos isomorfos:
•Tienen la misma estructura, aunque tengan diferentes contenidos y/o identificadores de los vértices.
Sin_título5.png
¿Cómo se implementan en java?
Árboles Binarios: Implementación de forma Recursiva
Sin_título.jpg
En esta forma de implementación, un árbol puede definirse como un dato (al que llamamos raíz) seguido de un subárbol izquierdo y otro subárbol derecho.
public class ArbolB<E>{
private E raiz;
private ArbolB<E> izq;
private ArbolB<E> der;

[...]
}
Grafo: Implementación
tgrafo Crear(void){
tnodo aux;

aux = (tnodo)malloc(sizeof(struct nodo));
if (aux == NULL) {
error(\"Error en Crear.\");
} else {
aux->nodo = 0;
aux->etiq = NULL;
aux->ady = NULL;
aux->inc = NULL;
aux->sig = NULL;
return aux;


_



ESTRUCTURAS DE DATOS NO LINEALES.


Estructura de datos no lineales: árboles y grafos.

Grafos:

Un grafo (específicamente, grafo simple no dirigido) es un par G D .V; E/ D .V .G/; V .E//, donde V es un conjunto finito no vacío de elementos llamados vértices y E es un conjunto de pares desordenados de elementos distintos de V llamados aristas. Es decir, una arista e 2 E tiene la forma fu; vg, donde u; v 2 V y u 6D v.
La terminología en teoría de grafos varía muchísimo: prácticamente no hay dos textos que adopten la misma. En particular, los vértices de un grafo también reciben a veces el nombre de nodos, y las aristas arcos, ejes o líneas.
Clasificación de grafos

Los grafos se pueden clasificar en dos grupos: dirigidos y no dirigidos. En un grafo no dirigido el par de vértices que representa un arco no está ordenado. Por lo tanto, los pares (v1, v2) y (v2, v1) representan el mismo arco. En un grafo dirigido cada arco está representado por un par ordenado de vértices, de forma que y representan dos arcos diferentes.

Ejemplos
G1 = (V1, A1)V1 = {1, 2, 3, 4} A1 = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}G2 = (V2, A2)V2 = {1, 2, 3, 4, 5, 6} A2 = {(1, 2), (1, 3), (2, 4), (2, 5), (3, 6)}G3 = (V3, A3)V3 = {1, 2, 3} A3 = { <1, 2>, <2, 1>, <2, 3> }


  • Grafo regular: Aquel con el mismo grado en todos los vértices. Si ese grado es k lo llamaremos k-regular.

Por ejemplo, el primero de los siguientes grafos es 3-regular, el segundo es 2-regular y el tercero no es regular
  • Grafo bipartito: Es aquel con cuyos vértices pueden formarse dos conjuntos disjuntos de modo que no haya adyacencias entre vértices pertenecientes al mismo conjunto

Ejemplo.- de los dos grafos siguientes el primero es bipartito y el segundo no lo es
  • Grafo completo: Aquel con una arista entre cada par de vértices. Un grafo completo con n vértices se denota Kn.

  • Un grafo bipartito regular: se denota Km,n donde m, n es el grado de cada conjunto disjunto de vértices
A continuación ponemos los dibujos de K1,2, K3,3, y K2,5
external image Image6015.gif
  • Grafo nulo: Se dice que un grafo es nulo cuando los vértices que lo componen no están conectados, esto es, que son vértices aislados.
  • Grafos Isomorfos: Dos grafos son isomorfos cuando existe una correspondencia biunívoca (uno a uno), entre sus vértices de tal forma que dos de estos quedan unidos por una arista en común.



  • Grafos Conexos: Un grafo se puede definir como conexo si cualquier vértice V pertenece al conjunto de vértices y es alcanzable por algún otro. Otra definición que dejaría esto más claro sería: "un grafo conexo es un grafo no dirigido de modo que para cualquier par de nodos existe al menos un camino que los une".
external image Image6016.gif


Recorrido de un grafo.

Recorrer un grafo significa tratar de alcanzar todos los nodos que estén relacionados con uno que llamaremos nodo de salida. Existen básicamente dos técnicas para recorrer un grafo: el recorrido en anchura; y el recorrido en profundidad.
  • Recorrido en anchura: El recorrido en anchura supone recorrer el grafo, a partir de un nodo dado, en niveles, es decir, primero los que están a una distancia de un arco del nodo de salida, después los que están a dos arcos de distancia, y así sucesivamente hasta alcanzar todos los nodos a los que se pudiese llegar desde el nodo salida.

  • Recorrido en profundidad: el recorrido en profundidad trata de buscar los caminos que parten desde el nodo de salida hasta que ya no es posible avanzar más. Cuando ya no puede avanzarse más sobre el camino elegido, se vuelve atrás en busca de caminos alternativos, que no se estudiaron previamente.



Representación de grafos en programas.
Hay tres maneras de representar un grafo en un programa: mediante matrices, mediante listas y mediante matrices dispersas.
  • Representación mediante matrices: La forma más fácil de guardar la información de los nodos es mediante la utilización de un vector que indexe los nodos, de manera que los arcos entre los nodos se pueden ver como relaciones entre los índices. Esta relación entre índices se puede guardar en una matriz, que llamaremos de adyacencia.

  • Representación mediante listas: En las listas de adyacencia lo que haremos será guardar por cada nodo, además de la información que pueda contener el propio nodo, una lista dinámica con los nodos a los que se puede acceder desde él. La información de los nodos se puede guardar en un vector, al igual que antes, o en otra lista dinámica.

  • Representación mediante matrices dispersas: Para evitar uno de los problemas que teníamos con las listas de adyacencia, que era la dificultad de obtener las relaciones inversas, podemos utilizar las matrices dispersas, que contienen tanta información como las matrices de adyacencia, pero, en principio, no ocupan tanta memoria como las matrices, ya que al igual que en las listas de adyacencia, sólo representaremos aquellos enlaces que existen en el grafo.


APLICACIÓN DE LOS GRAFOS.

Grafos: Entre las múltiples aplicaciones que tienen estas estructuras podemos mencionar:•Para modelar diversas situaciones tales como: sistemas de aeropuertos, flujo de tráfico, y responder a preguntas como: ¿Qué tiempo es más corto?, ¿Cómo es más barato?, o ¿Qué camino es más corto?. •Los grafos también son utilizados para realizar planificación de actividades, tareas del computador, planificar operaciones en lenguaje de máquinas para minimizar tiempo de ejecución.¿Qué tarea debo hacer primero?. •Para representar circuitos eléctricos, de aguas etc... , y preguntar, están todas las componentes conectadas.


ÁRBOLES.


Terminología
􀂉 Nodo: los vértices o elementos de un árbol.
􀂉 Enlace/arco/arista: Conexión entre dos nodos
consecutivos.
􀂉 Los nodos pueden ser:
Nodo raíz: nodo superior de la jerarquía.
Nodo terminal u hoja: nodo que no contienen ningún subárbol.
Nodos interiores: nodos con uno o más subárboles; nodos que no
son hojas.
Descendientes o hijos: cada uno de los subárboles de un nodo.
Ascendiente, antecesor o padre: nodo de jerarquía superior a
uno dado.
Nodos hermanos: nodos del mismo padre.
􀂉 Bosque: colección de árboles.

Árboles binarios
􀂉 Un árbol general sería un árbol en el que cada nodo puede tener un
número ilimitado de subárboles.
􀂉 Un árbol binario sería un conjunto de 0 o más nodos en el cual
existe un nodo raíz y cada uno de los nodos, incluido el raíz podrán
tener 0, 1 o dos subárboles:
● Subárbol izquierdo y subárbol derecho
􀂉 Terminología:
Árboles similares: árboles con la misma estructura.
Árboles equivalentes: árboles con la misma estructura y contienen la
misma información.
Árboles completos o árboles perfectos: todos los nodos, excepto
las hojas, tienen grado 2.
􀀹􀀹 Un árbol binario de nivel n tiene 2n-1 nodos.
Árbol equilibrado: un árbol en el que las alturas de los dos
subárboles de cada uno de los nodos tiene como máximo una diferencia
de una unidad.
Árbol degenerado: todos sus nodos sólo tienen un subárbol.


Implementación de árboles binarios.
􀂉 El almacenamiento será un array de nodos.
􀂉 El tipo árbol será un índice de array.
􀂉 Cada nodo tendrá los campos raíz de tipo TipoElemento, hizq de tipo
árbol y hder de tipo árbol.
● Los punteros hizq e hder serían índices del array.
● Un valor -1 en el hijo derecho podría corresponder a un elemento que no contiene un nodo
válido.

const
MaxArbol = …
tipos
… = TipoElemento
entero = árbol
registro = nodo
TipoElemento = raíz
árbol = hizq, hder
fin_registro
array[1..MaxArbol] de nodo = almacenamiento
var
almacenamiento : alm
EQUIPO:

Rosa Arianna Paredes Gonzalez.
Edgar Lozano Velazquez.
Jose Luis Cocoletzi Lopez.
Ricardo Daniel Juarez Hernandez.
Michel Alain Nophal Hernandez.


ÁrbolesFiled under General
Un árbol es una estructura de datos dinámica ( las estructuras del árbol pueden cambiar durante la ejecución del programa ) no lineal ( puesto que a cada elemento del árbol puede seguirle varios elementos ) y homogénea en el que cada elemento puede tener varios elementos posteriores y solamente un elemento anterior. Es una estructura jerárquica aplicada sobre una colección de elementos u objetos llamados nodos, de los cuales uno es conocido como raíz , además se crea una relación de parentesco entre los nodos dando lugar a términos como padre, hijo, hermano, antecesor, sucesor, ancestro, etc.
Un árbol es una estructura que está compuesta por un dato y varios árboles. 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 una árbol completo.
external image pic.php?u=19319TEqXa&i=1115858
En relación con otros nodos:
  • Nodo Padre: Nodo que contiene un puntero al nodo actual. En un árbol un nodo solo puede tener un nodo padre.. X es padre de Y sí y solo sí el nodo X apunta a Y, tambien se dice que X es antecesor de Y. En la figura B es padre de E y F.
  • Nodo Hijo: Cualquiera de los nodos apuntados por uno de los nodos del aŕbol. Un nodo puede tener varios hijos.. X es hijo de Y, sí y solo sí el nodo X es apuntado por Y. Tambien se dice que X es descenciente directo de Y. En la figura : E es hijo de B.
  • Hermano: Dos nodos serán hermanos si son descencientes directos de un mismo nodo. En la figura Ey F son hermanos.
En cuanto a la posición dentro del árbol:
  • Nodo Raíz: Es el único nodo del árbol que no tiene padre. Este es el nodo que usaremos para referirnos al árbol. En la figura A es el nodo raíz.
  • Nodo Hoja: Nodo que no tiene hijos. Se llama hoja o terminal a aquellos nodos que no tienen ramificaciones ( hijos ). En la figura .. N es un nodo hoja.
  • Nodo Interior: Es un nodo que no es raíz ni hoja. En la figura .. D es un nodo interior.
  • 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. Podríamos decir que nuestro árbol de ejemplo es de orden tres.
  • 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, el de sus hijos uno y asi sucesivamente. En el ejemplo, el nodo D tiene nivel 1, el nodo G tiene nivel 2 y el nodo N nivel 3.
  • Rama: Es el camino desde el nodo raíz a una hoja. En el ejemplo A-B-E-K y A-B-F son ramas.
  • 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, tambien podemos hablar de altura de ramas, el máximo número de nodos que hay que recorrer para llegar de la raíz a una de las hojas. El árbol de la Figura tiene altura 3, la rama B tiene altura 2, la rama G tiene altura 1 y la N cero.
  • Peso: Es el número de nodos del árbol sin contar la raíz.
  • Camino: Es una consecuencia de nodos, en el que dos nodos consecutivos cualesquiera son padre e hijo. En el ejemplo A-D-H y A-C-G-M son caminos.
  • Longitud de camino: Es el número de arcos que deben ser recorridos para llegar desde la raíz al nodo X. Por definición la raíz tiene longitud de camino 1, y sus descendientes directos longitud de camino 2 y así sucesivamente. En nuestro árbol de ejemplo G tiene longitud de camino 3 y N tiene longitud de camino 4.

Grafo

En matemáticas y ciencias de la computación, un grafo (del griego grafos: dibujo, imagen) ográfica es el principal objeto de estudio de la teoría de grafos.
Informalmente, un grafo es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto.
Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas).
Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre unidades que interactúan unas con otras. Por ejemplo, una red de computadoras puede representarse y estudiarse mediante un grafo, en el cual los vértices representan terminalesy las aristas representan conexiones (las cuales, a su vez, pueden ser cables o conexiones inalámbricas).

Tipos de grafos
Existen dos tipos de grafos los no dirigidos y los dirigidos.
• No dirigidos: son aquellos en los cuales los lados no están orientados (No son flechas). Cada lado se representa entre paréntesis, separando sus vértices por comas, y teniendo en cuenta (Vi,Vj)=(Vj,Vi).

external image Image156.gif
• Dirigidos: son aquellos en los cuales los lados están orientados (flechas). Cada lado se representa entre ángulos, separando sus vértices por comas y teniendo en cuenta <Vi ,Vj>!=<Vj ,Vi>. En grafos dirigidos, para cada lado <A,B>, A, el cual es el vértice origen, se conoce como la cola del lado y B, el cual es el vértice destino, se conoce como cabeza del lado.

external image img7.png
Se dice que el grafo G = (V, E) es
a) Un grafo regular de grado n si todos sus vértices tienen grado n.
b) Un grafo completo si cada par de vértices está unido por una arista. Se denota por Kn al grafo completo de n vértices
c) Un ciclo si V = {v1, v2, . . . vn}, n³> 3, y E = (v1, v2), (v2, v3), . . . , (vn, v1). Se denota por Cn al ciclo de n vértices
d)Una rueda si V = {v0, v1, v2, . . . vn}, n n> 3, y E = {(v1, v2), (v2, v3), . . . , (vn, v1), {(v1, v0), (v2, v0), . . . , (vn, v0) }. Se denota por Wn a la rueda de n+1 vértices
e)Un cubo si sus vértices y aristas están relacionados como los de un cubo n-dimensional. Se denota por Qn al cubo asociado al cubo n-dimensional.
f)Un grafo bipartido si V=V 1 UV 2 y cada arista de E une un vértice de V1 y otro de V2
g)Un grafo bipartido completo si V=V 1 UV 2 y dos vértices de V están unidos por una arista de E si y solo si un vértice está en V1 y el otro en V2. Se denota por Kr,s al grafo bipartido completo donde V1 tiene r vértices y V2 tiene s vértices


Yves Geraud MendozaCarlos Omar Pérez Cortes

  • Nodo padre: nodo que contiene un puntero al nodo actual. En el ejemplo, el nodo 'A' es padre de 'B', 'C' y 'D'.


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'.


Un árbol en el que en cada nodo o bien todos o ninguno de los hijos existe, se llama árbol completo



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.

Árboles generales

Intuitivamente el concepto de árbol implica una estructura en la que los datos se organizan de modo que los elementos de información están relacionados entre si a través de ramas. El árbol genealógico es el ejemplo típico más representativo del concepto de árbol general.

Árboles binarios

Es un árbol en el que ningún nodo puede tener mas de dos subárboles. En un árbol binario, cada nodo puede tener cero, uno o dos hijos (subárboles). Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho.

Operaciones en árboles binarios



ž Determinar su altura

ž Determinar su número de elementos

ž Hacer una copia

ž Visualizar el árbol binario en pantalla o en impresora

ž Determinar si dos árboles binarios son idénticos

ž Borrar (eliminar el árbol)

ž Si es un árbol de expresión, evaluar la expresión

ž Si es un árbol de expresión, obtener la forma de paréntesis de la expresión.





GRAFOS

Son estructuras de datos más generales que los árboles.

•Permiten modelar relaciones no necesariamente jerárquicas entre elementos de un conjunto.
•Se utilizan para representar mapas de rutas, organización de procesos, espacios de búsqueda para juegos, circuitos lógicos, etc.

Sin_título.png




Tipos de grafos

Grafo completo:

•Dos vértices diferentes cualesquiera del conjunto V son adyacentes.

Sin_título2.png



Grafo conexo:
•Para cualquier par de vértices v, w del conjunto V, existe una cadena que los une.
Grafo fuertemente conexo:
•Para cualquier par de vértices v, w del conjunto V, existe una camino que vaya de v a w.

Sin_título3.png


Grafo planar:
•Es posible dibujarlo en un plano sin que se crucen los arcos.
•Problema típico:
•3 casas y 3 servicios.
•Se trata de establecer si es posible llevar las tuberías de agua, gas y electricidad, sobre un mismo plano, a 3 casas vecinas.
•El problema se reduce a determinar si el grafo que representa la solución es planar.
•Vértices: casas y servicios.
•Arcos: tuberías.

Sin_título4.png

Grafos isomorfos:
•Tienen la misma estructura, aunque tengan diferentes contenidos y/o identificadores de los vértices.
Sin_título5.png
¿Cómo se implementan en java?
Árboles Binarios: Implementación de forma Recursiva
Sin_título.jpg
En esta forma de implementación, un árbol puede definirse como un dato (al que llamamos raíz) seguido de un subárbol izquierdo y otro subárbol derecho.
public class ArbolB<E>{
private E raiz;
private ArbolB<E> izq;
private ArbolB<E> der;

[...]
}
Grafo: Implementación
tgrafo Crear(void){
tnodo aux;

aux = (tnodo)malloc(sizeof(struct nodo));
if (aux == NULL) {
error(\"Error en Crear.\");
} else {
aux->nodo = 0;
aux->etiq = NULL;
aux->ady = NULL;
aux->inc = NULL;
aux->sig = NULL;
return aux;


_


ESTRUCTURAS DE DATOS NO LINEALES.

Estructura de datos no lineales: árboles y grafos.


Grafos:

Un grafo (específicamente, grafo simple no dirigido) es un par G D .V; E/ D .V .G/; V .E//, donde V es un conjunto finito no vacío de elementos llamados vértices y E es un conjunto de pares desordenados de elementos distintos de V llamados aristas. Es decir, una arista e 2 E tiene la forma fu; vg, donde u; v 2 V y u 6D v.
La terminología en teoría de grafos varía muchísimo: prácticamente no hay dos textos que adopten la misma. En particular, los vértices de un grafo también reciben a veces el nombre de nodos, y las aristas arcos, ejes o líneas.

Clasificación de grafos

Los grafos se pueden clasificar en dos grupos: dirigidos y no dirigidos. En un grafo no dirigido el par de vértices que representa un arco no está ordenado. Por lo tanto, los pares (v1, v2) y (v2, v1) representan el mismo arco. En un grafo dirigido cada arco está representado por un par ordenado de vértices, de forma que y representan dos arcos diferentes.

Ejemplos
G1 = (V1, A1)V1 = {1, 2, 3, 4} A1 = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}G2 = (V2, A2)V2 = {1, 2, 3, 4, 5, 6} A2 = {(1, 2), (1, 3), (2, 4), (2, 5), (3, 6)}G3 = (V3, A3)V3 = {1, 2, 3} A3 = { <1, 2>, <2, 1>, <2, 3> }

  • Grafo regular: Aquel con el mismo grado en todos los vértices. Si ese grado es k lo llamaremos k-regular.

Por ejemplo, el primero de los siguientes grafos es 3-regular, el segundo es 2-regular y el tercero no es regular
  • Grafo bipartito: Es aquel con cuyos vértices pueden formarse dos conjuntos disjuntos de modo que no haya adyacencias entre vértices pertenecientes al mismo conjunto

Ejemplo.- de los dos grafos siguientes el primero es bipartito y el segundo no lo es
  • Grafo completo: Aquel con una arista entre cada par de vértices. Un grafo completo con n vértices se denota Kn.

  • Un grafo bipartito regular: se denota Km,n donde m, n es el grado de cada conjunto disjunto de vértices
A continuación ponemos los dibujos de K1,2, K3,3, y K2,5
external image Image6015.gif
  • Grafo nulo: Se dice que un grafo es nulo cuando los vértices que lo componen no están conectados, esto es, que son vértices aislados.
  • Grafos Isomorfos: Dos grafos son isomorfos cuando existe una correspondencia biunívoca (uno a uno), entre sus vértices de tal forma que dos de estos quedan unidos por una arista en común.



  • Grafos Conexos: Un grafo se puede definir como conexo si cualquier vértice V pertenece al conjunto de vértices y es alcanzable por algún otro. Otra definición que dejaría esto más claro sería: "un grafo conexo es un grafo no dirigido de modo que para cualquier par de nodos existe al menos un camino que los une".
external image Image6016.gif


Recorrido de un grafo.

Recorrer un grafo significa tratar de alcanzar todos los nodos que estén relacionados con uno que llamaremos nodo de salida. Existen básicamente dos técnicas para recorrer un grafo: el recorrido en anchura; y el recorrido en profundidad.
  • Recorrido en anchura: El recorrido en anchura supone recorrer el grafo, a partir de un nodo dado, en niveles, es decir, primero los que están a una distancia de un arco del nodo de salida, después los que están a dos arcos de distancia, y así sucesivamente hasta alcanzar todos los nodos a los que se pudiese llegar desde el nodo salida.


  • Recorrido en profundidad: el recorrido en profundidad trata de buscar los caminos que parten desde el nodo de salida hasta que ya no es posible avanzar más. Cuando ya no puede avanzarse más sobre el camino elegido, se vuelve atrás en busca de caminos alternativos, que no se estudiaron previamente.



Representación de grafos en programas.
Hay tres maneras de representar un grafo en un programa: mediante matrices, mediante listas y mediante matrices dispersas.
  • Representación mediante matrices: La forma más fácil de guardar la información de los nodos es mediante la utilización de un vector que indexe los nodos, de manera que los arcos entre los nodos se pueden ver como relaciones entre los índices. Esta relación entre índices se puede guardar en una matriz, que llamaremos de adyacencia.


  • Representación mediante listas: En las listas de adyacencia lo que haremos será guardar por cada nodo, además de la información que pueda contener el propio nodo, una lista dinámica con los nodos a los que se puede acceder desde él. La información de los nodos se puede guardar en un vector, al igual que antes, o en otra lista dinámica.


  • Representación mediante matrices dispersas: Para evitar uno de los problemas que teníamos con las listas de adyacencia, que era la dificultad de obtener las relaciones inversas, podemos utilizar las matrices dispersas, que contienen tanta información como las matrices de adyacencia, pero, en principio, no ocupan tanta memoria como las matrices, ya que al igual que en las listas de adyacencia, sólo representaremos aquellos enlaces que existen en el grafo.


APLICACIÓN DE LOS GRAFOS.
Grafos: Entre las múltiples aplicaciones que tienen estas estructuras podemos mencionar:•Para modelar diversas situaciones tales como: sistemas de aeropuertos, flujo de tráfico, y responder a preguntas como: ¿Qué tiempo es más corto?, ¿Cómo es más barato?, o ¿Qué camino es más corto?. •Los grafos también son utilizados para realizar planificación de actividades, tareas del computador, planificar operaciones en lenguaje de máquinas para minimizar tiempo de ejecución.¿Qué tarea debo hacer primero?. •Para representar circuitos eléctricos, de aguas etc... , y preguntar, están todas las componentes conectadas.

ÁRBOLES.


Terminología
􀂉 Nodo: los vértices o elementos de un árbol.
􀂉 Enlace/arco/arista: Conexión entre dos nodos
consecutivos.
􀂉 Los nodos pueden ser:
Nodo raíz: nodo superior de la jerarquía.
Nodo terminal u hoja: nodo que no contienen ningún subárbol.
Nodos interiores: nodos con uno o más subárboles; nodos que no
son hojas.
Descendientes o hijos: cada uno de los subárboles de un nodo.
Ascendiente, antecesor o padre: nodo de jerarquía superior a
uno dado.
Nodos hermanos: nodos del mismo padre.
􀂉 Bosque: colección de árboles.

Árboles binarios
􀂉 Un árbol general sería un árbol en el que cada nodo puede tener un
número ilimitado de subárboles.
􀂉 Un árbol binario sería un conjunto de 0 o más nodos en el cual
existe un nodo raíz y cada uno de los nodos, incluido el raíz podrán
tener 0, 1 o dos subárboles:
● Subárbol izquierdo y subárbol derecho
􀂉 Terminología:
Árboles similares: árboles con la misma estructura.
Árboles equivalentes: árboles con la misma estructura y contienen la
misma información.
Árboles completos o árboles perfectos: todos los nodos, excepto
las hojas, tienen grado 2.
􀀹􀀹 Un árbol binario de nivel n tiene 2n-1 nodos.
Árbol equilibrado: un árbol en el que las alturas de los dos
subárboles de cada uno de los nodos tiene como máximo una diferencia
de una unidad.
Árbol degenerado: todos sus nodos sólo tienen un subárbol.


Implementación de árboles binarios.
􀂉 El almacenamiento será un array de nodos.
􀂉 El tipo árbol será un índice de array.
􀂉 Cada nodo tendrá los campos raíz de tipo TipoElemento, hizq de tipo
árbol y hder de tipo árbol.
● Los punteros hizq e hder serían índices del array.
● Un valor -1 en el hijo derecho podría corresponder a un elemento que no contiene un nodo
válido.

const
MaxArbol = …
tipos
… = TipoElemento
entero = árbol
registro = nodo
TipoElemento = raíz
árbol = hizq, hder
fin_registro
array[1..MaxArbol] de nodo = almacenamiento
var
almacenamiento : alm

EQUIPO:

Rosa Arianna Paredes Gonzalez.
Edgar Lozano Velazquez.
Jose Luis Cocoletzi Lopez.
Ricardo Daniel Juarez Hernandez.
Michel Alain Nophal Hernandez.


ÁrbolesFiled under General
Un árbol es una estructura de datos dinámica ( las estructuras del árbol pueden cambiar durante la ejecución del programa ) no lineal ( puesto que a cada elemento del árbol puede seguirle varios elementos ) y homogénea en el que cada elemento puede tener varios elementos posteriores y solamente un elemento anterior. Es una estructura jerárquica aplicada sobre una colección de elementos u objetos llamados nodos, de los cuales uno es conocido como raíz , además se crea una relación de parentesco entre los nodos dando lugar a términos como padre, hijo, hermano, antecesor, sucesor, ancestro, etc.
Un árbol es una estructura que está compuesta por un dato y varios árboles. 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 una árbol completo.
external image pic.php?u=19319TEqXa&i=1115858
En relación con otros nodos:
  • Nodo Padre: Nodo que contiene un puntero al nodo actual. En un árbol un nodo solo puede tener un nodo padre.. X es padre de Y sí y solo sí el nodo X apunta a Y, tambien se dice que X es antecesor de Y. En la figura B es padre de E y F.
  • Nodo Hijo: Cualquiera de los nodos apuntados por uno de los nodos del aŕbol. Un nodo puede tener varios hijos.. X es hijo de Y, sí y solo sí el nodo X es apuntado por Y. Tambien se dice que X es descenciente directo de Y. En la figura : E es hijo de B.
  • Hermano: Dos nodos serán hermanos si son descencientes directos de un mismo nodo. En la figura Ey F son hermanos.
En cuanto a la posición dentro del árbol:
  • Nodo Raíz: Es el único nodo del árbol que no tiene padre. Este es el nodo que usaremos para referirnos al árbol. En la figura A es el nodo raíz.
  • Nodo Hoja: Nodo que no tiene hijos. Se llama hoja o terminal a aquellos nodos que no tienen ramificaciones ( hijos ). En la figura .. N es un nodo hoja.
  • Nodo Interior: Es un nodo que no es raíz ni hoja. En la figura .. D es un nodo interior.
  • 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. Podríamos decir que nuestro árbol de ejemplo es de orden tres.
  • 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, el de sus hijos uno y asi sucesivamente. En el ejemplo, el nodo D tiene nivel 1, el nodo G tiene nivel 2 y el nodo N nivel 3.
  • Rama: Es el camino desde el nodo raíz a una hoja. En el ejemplo A-B-E-K y A-B-F son ramas.
  • 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, tambien podemos hablar de altura de ramas, el máximo número de nodos que hay que recorrer para llegar de la raíz a una de las hojas. El árbol de la Figura tiene altura 3, la rama B tiene altura 2, la rama G tiene altura 1 y la N cero.
  • Peso: Es el número de nodos del árbol sin contar la raíz.
  • Camino: Es una consecuencia de nodos, en el que dos nodos consecutivos cualesquiera son padre e hijo. En el ejemplo A-D-H y A-C-G-M son caminos.
  • Longitud de camino: Es el número de arcos que deben ser recorridos para llegar desde la raíz al nodo X. Por definición la raíz tiene longitud de camino 1, y sus descendientes directos longitud de camino 2 y así sucesivamente. En nuestro árbol de ejemplo G tiene longitud de camino 3 y N tiene longitud de camino 4.

Grafo

En matemáticas y ciencias de la computación, un grafo (del griego grafos: dibujo, imagen) ográfica es el principal objeto de estudio de la teoría de grafos.
Informalmente, un grafo es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto.
Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas).
Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre unidades que interactúan unas con otras. Por ejemplo, una red de computadoras puede representarse y estudiarse mediante un grafo, en el cual los vértices representan terminalesy las aristas representan conexiones (las cuales, a su vez, pueden ser cables o conexiones inalámbricas).

Tipos de grafos
Existen dos tipos de grafos los no dirigidos y los dirigidos.
• No dirigidos: son aquellos en los cuales los lados no están orientados (No son flechas). Cada lado se representa entre paréntesis, separando sus vértices por comas, y teniendo en cuenta (Vi,Vj)=(Vj,Vi).

external image Image156.gif
• Dirigidos: son aquellos en los cuales los lados están orientados (flechas). Cada lado se representa entre ángulos, separando sus vértices por comas y teniendo en cuenta <Vi ,Vj>!=<Vj ,Vi>. En grafos dirigidos, para cada lado <A,B>, A, el cual es el vértice origen, se conoce como la cola del lado y B, el cual es el vértice destino, se conoce como cabeza del lado.

external image img7.png
Se dice que el grafo G = (V, E) es
a) Un grafo regular de grado n si todos sus vértices tienen grado n.
b) Un grafo completo si cada par de vértices está unido por una arista. Se denota por Kn al grafo completo de n vértices
c) Un ciclo si V = {v1, v2, . . . vn}, n³> 3, y E = (v1, v2), (v2, v3), . . . , (vn, v1). Se denota por Cn al ciclo de n vértices
d)Una rueda si V = {v0, v1, v2, . . . vn}, n n> 3, y E = {(v1, v2), (v2, v3), . . . , (vn, v1), {(v1, v0), (v2, v0), . . . , (vn, v0) }. Se denota por Wn a la rueda de n+1 vértices
e)Un cubo si sus vértices y aristas están relacionados como los de un cubo n-dimensional. Se denota por Qn al cubo asociado al cubo n-dimensional.
f)Un grafo bipartido si V=V 1 UV 2 y cada arista de E une un vértice de V1 y otro de V2
g)Un grafo bipartido completo si V=V 1 UV 2 y dos vértices de V están unidos por una arista de E si y solo si un vértice está en V1 y el otro en V2. Se denota por Kr,s al grafo bipartido completo donde V1 tiene r vértices y V2 tiene s vértices


Yves Geraud MendozaCarlos Omar Pérez Cortes






" ESTRUCTURAS NO LINEALES"




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

Árbol
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.
El nodo típico de un árbol difiere de los nodos que hemos visto hasta ahora para listas, aunque sólo en el número de nodos. Veamos un ejemplo de nodo para crear árboles de orden tres:
struct nodo \{
   int dato;
   struct nodo *rama1;
   struct nodo *rama2;
   struct nodo *rama3;
};
O generalizando más:
#define ORDEN 5
 
struct nodo \{
   int dato;
   struct nodo *rama[ORDEN];
};
 
[[#6_2]]
 

6.2 Declaraciones de tipos para manejar árboles en C

^
Para C, y basándonos en la declaración de nodo que hemos visto más arriba, trabajaremos con los siguientes tipos:
typedef struct _nodo \{
   int dato;
   struct _nodo *rama[ORDEN];
} tipoNodo;
 
typedef tipoNodo *pNodo;
typedef tipoNodo *Arbol;
Al igual que hicimos con las listas que hemos visto hasta ahora, declaramos un tipo tipoNodo para declarar nodos, y un tipo pNodo para es el tipo para declarar punteros a un nodo.
Arbol es el tipo para declarar árboles de orden ORDEN.
Árbol
Árbol

Árbol
El movimiento a través de árboles, salvo que implementemos punteros al nodo padre, será siempre partiendo del nodo raíz hacia un nodo hoja. Cada vez que lleguemos a un nuevo nodo podremos optar por cualquiera de los nodos a los que apunta para avanzar al siguiente nodo.
En general, intentaremos que exista algún significado asociado a cada uno de los punteros dentro de cada nodo, los árboles que estamos viendo son abstractos, pero las aplicaciones no tienen por qué serlo. Un ejemplo de estructura en árbol es el sistema de directorios y ficheros de un sistema operativo. Aunque en este caso se trata de árboles con nodos de dos tipos, nodos directotio y nodos fichero, podríamos considerar que los nodos hoja son ficheros y los nodos rama son directorios.
Otro ejemplo podría ser la tabla de contenido de un libro, por ejemplo de este mismo curso, dividido en capítulos, y cada uno de ellos en subcapítulos. Aunque el libro sea algo lineal, como una lista, en el que cada capítulo sigue al anterior, también es posible acceder a cualquier punto de él a través de la tabla de contenido.
También se suelen organizar en forma de árbol los organigramas de mando en empresas o en el ejército, y los árboles genealógicos.

" GRAFOS "

external image 200px-6n-graf.svg.pngexternal image magnify-clip.png
Un grafo de 6 vértices y 7 aristas.
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.

Formas de representación

Existen diferentes implementaciones del tipo grafo: con una matriz de adyacencias (forma acotada) y con listas y multilistas de adyacencia (no acotadas).
  • Matriz de adyacencias: se asocia cada fila y cada columna a cada nodo del grafo, siendo los elementos de la matriz la relación entre los mismos, tomando los valores de 1 si existe la arista y 0 en caso contrario.
Matriz de adyacencia.jpg
Matriz de adyacencia.jpg

  • Lista de adyacencias: se asocia a cada nodo del grafo una lista que contenga todos aquellos nodos que sean adyacentes a él.
Listas de adyacencia.jpg
Listas de adyacencia.jpg

Especificación de los tipos abstractos de datos de un grafo no dirigido

Generadores

Crear un grafo vacío: Devuelve un grafo vacío.

Grafo

  • op crearGrafo : -> Grafo [ctor] .
Añadir una arista: Dado un grafo, añade una relación entre dos nodos de dicho grafo.
  • op añadirArista : Grafo Nodo Nodo -> [Grafo] [ctor] .
Añadir un nodo: Dado un grafo, incluye un nodo en el en caso en el que no exista previamente.
  • op añadirNodo : Grafo Nodo -> Grafo [ctor] .

Constructores

Borrar nodo: Devuelve un grafo sin un nodo y las aristas relacionadas con él. Si dicho nodo no existe se devuelve el grafo inicial.
  • op borrarNodo : Grafo Nodo -> Grafo .
Borrar arista: Devuelve un grafo sin la arista indicada. En caso de que la arista no exista devuelve el grafo inicial.
  • op borrarArista : Grafo Nodo Nodo -> Grafo .

Selectores

Grafo Vacio: Comprueba si un grafo no tiene ningún nodo.
  • op esVacio : Grafo -> Bool .
Contener Nodo: Comprueba si un nodo pertenece a un grafo.
  • op contiene : Grafo Nodo -> Bool .
Adyacentes: Comprueba si dos nodos tienen una arista que los relacione.
  • op adyacentes : Grafo Nodo Nodo -> Bool .
Para la especificación de un grafo dirigido tenemos que modificar algunas de las ecuaciones de las operaciones borrarArista y añadirArista para que no se considere el caso de aristas bidireccionales.
Y sustituir la operación adyacentes por:
  • op predecesor : Grafo Nodo Nodo -> Bool .
  • op sucesor : Grafo Nodo Nodo -> Bool .


MIRIAM ARROYO GUTIERREZ
ABIGAIL HUERTA MACIAS
JESUS ANTONIO MONTIEL RAMIREZ

ARBOLES
_
ARBOLES

Árbol :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.

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'.

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'.
Un árbol en el que en cada nodo o bien todos o ninguno de los hijos existe, se llama árbol completo .

RAIZ DEL ÁRBOL:Todos los árboles que no están vacíos tienen un único nodo raíz. Todos los demás elementos o nodos se derivan o descienden de él. El nodo raíz no tiene padre, es decir, no es el hijo de ningún elemento.

NODO: Son los vértices o elementos del árbol.

NODO TERMINAL U HOJA: Es aquel que no contiene ningún subárbol.

A cada nodo que no es hoja se asocia uno o varios subárboles llamados descendientes o hijos. De igual forma, cada nodo tiene asociado un antecesor o ascendiente llamado padre.

Los nodos de un mismo padre se llaman Hermanos.

Los nodos con uno o dos subárboles no son hojas ni raíz, se llaman Nodos Interiores o Internos.

Una colección de dos o más árboles se llama bosque.

Todos los nodos tienen un solo padre (excepto la raíz) que no tiene padre.

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.
Árboles generales Intuitivamente el concepto de árbol implica una estructura en la que los datos se organizan de modo que los elementos de información están relacionados entre si a través de ramas. El árbol genealógico es el ejemplo típico más representativo del concepto de árbol general.

Árboles binarios Es un árbol en el que ningún nodo puede tener mas de dos subárboles. En un árbol binario, cada nodo puede tener cero, uno o dos hijos (subárboles). Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho.

Operaciones en árboles binarios Determinar su altura Determinar su número de elementos Hacer una copia Visualizar el árbol binario en pantalla o en impresora Determinar si dos árboles binarios son idénticos Borrar (eliminar el árbol) Si es un árbol de expresión, evaluar la expresión Si es un árbol de expresión, obtener la forma de paréntesis de la expresión.

Recorridos de un árbol binario Recorrido. Requiere que cada nodo del árbol sea procesado (visitado) una vez y sólo en una secuencia predeterminada. Existen dos enfoques generales para la secuencia de recorrido, profundidad y anchura.

Recorrido en profundidad El proceso exige un camino desde la raíz a través de un hijo, al descendiente más lejano del primer hijo antes de proseguir a un segundo hijo. En otras palabras, en el recorrido en profundidad, todos los descendientes de un hijo se procesan antes del siguiente hijo.

Recorrido en anchura El proceso se realiza horizontalmente desde el raíz a todos sus hijos, a continuación a los hijos de sus hijos y así sucesivamente hasta que todos los nodos han sido procesados. En otras palabras, en el recorrido en anchura cada nivel se procesa totalmente antes que comience el siguiente nivel.

Preorden (NID) Este recorrido conlleva los siguientes pasos: Recorrer la raíz (N) Recorrer el subárbol izquierdo (I) Recorrer el subárbol derecho (D) REGLA . La raíz se procesa antes que los subárboles izquierdo y derecho.

Inorden (IND) Recorrer el subárbol izquierdo (I) Visitar el nodo raíz (N) Recorrer el subárbol derecho (D) El significado in es que la raíz se procesa entre los subárboles.

Postorden (IDN) Recorrer el subárbol izquierdo (I) Recorrer el subárbol derecho (D) Recorrer la raíz (N) Se comienza situándose en la hoja mas izquierda
Operaciones comunes en arboles son:
•Enumerar todos los elementos
•Buscar un elemento
•Añadir un nuevo ítem en una cierta posición del árbol
•Borrar un elemento
•Remover una sección completa de un árbol.
•Añadir una sección completa a un árbol.
•Encontrar la raíz de cualquier nodo



Arbol07.GIF

GRAFOS
Un grafo dirigido es una estructura compuesta por un conjunto de elementos, denominados los vértices, y por un conjunto de relaciones entre dichos elementos, denominados los arcos. El formalismo escogido para representar un grafo es una pareja ordenada de conjuntos:
G = ( V, A )
donde V es el conjunto de vértices y A el conjunto de arcos. Para efectos prácticos se dice que v1, ..., vn son los elementos de V.
V = { v1, ..., vn }
Un arco, por su parte, es una tripleta de la forma ( vi, vk, cik ), la cual establece una relación entre los vértices vi y vk de V, un sentido de la relación ( vi vk ), y un valor o peso asociado ( cik ). Gráficamente, una tripleta se suele representar de la siguiente forma:



De esta forma, se puede definir el conjunto de arcos como:
A = { ( x, y, c ) x, y V, x y,, x e y están relacionados con un valor c }
Se dice que vk es sucesor de vi, si ( vi, vk, c ) A para algún c. En este mismo caso se dice que vi es predecesor de vk. Una representación gráfica de estos conceptos se da en la figura 6.4.


Fig. 6.4 - Sucesores y predecesores del vértice v
Cada vértice vi del grafo tiene asociados dos valores: uno, corresponde a un identificador que lo distingue como elemento único de V, y, el otro, es alguna información asociada con el elemento. Como parte de la notación se utiliza vi para hablar indistintamente del vértice y de su identificador, e info( vi ) para referirse a la información asociada con el vértice vi.
En un grafo dirigido existe la restricción de que no puede haber más de un arco entre cualquier par de vértices, en cada uno de los sentidos. En la figura 6.5 se ilustra un caso válido y otro inválido.


( a ) Situación válida ( b ) Situación inválida
Fig. 6.5 - Dos arcos entre dos vértices
El orden de un grafo corresponde al número de sus elementos, es decir, a la cardinalidad del conjunto de vértices. Cuando un grafo es de orden cero, el grafo es vacío y se representa mediante la pareja ( , ). Un vértice de un grafo es una fuente si no tiene ningún predecesor. En ese caso, no existe en el conjunto de arcos ninguna tripleta cuyo segundo elemento sea dicho vértice. Un vértice de un grafo es un sumidero, si no tiene ningún sucesor en el grafo. Formalmente se tiene que:
fuente( v ) ssi (w, v, c) A, w, c
sumidero( v ) ssi (v, w, c) A, w, c
‘Un conjunto de pares de vértices que se llaman aristas o arcos y que indican qué nodos están relacionados. De una manera más informal podemos decir que un grafo es un conjunto de nodos con enlaces entre ellos, denominados aristas o arcos.
Arbol07.GIF
Existen dos tipos de grafos los no dirigidos y los dirigidos.
• No dirigidos: son aquellos en los cuales los lados no están orientados (No son flechas). Cada lado se representa entre paréntesis, separando sus vértices por comas, y teniendo en cuenta (Vi,Vj)=(Vj,Vi).
grafo_4_colores.JPG
• Dirigidos: son aquellos en los cuales los lados están orientados (flechas). Cada lado se representa entre ángulos, separando sus vértices por comas y teniendo en cuenta <Vi ,Vj>!=<Vj ,Vi>. En grafos dirigidos, para cada lado <A,B>, A, el cual es el vértice origen, se conoce como la cola del lado y B, el cual es el vértice destino, se conoce como cabeza del lado.

Se dice que el grafo G = (V, E) es
a) Un grafo regular de grado n si todos sus vértices tienen grado n.
b) Un grafo completo si cada par de vértices está unido por una arista. Se denota por Kn al grafo completo de n vértices
c) Un ciclo si V = {v1, v2, . . . vn}, n³> 3, y E = (v1, v2), (v2, v3), . . . , (vn, v1). Se denota por Cn al ciclo de n vértices
d)Una rueda si V = {v0, v1, v2, . . . vn}, n n> 3, y E = {(v1, v2), (v2, v3), . . . , (vn, v1), {(v1, v0), (v2, v0), . . . , (vn, v0) }. Se denota por Wn a la rueda de n+1 vértices
e)Un cubo si sus vértices y aristas están relacionados como los de un cubo n-dimensional. Se denota por Qn al cubo asociado al cubo n-dimensional.
f)Un grafo bipartido si V=V 1 UV 2? y cada arista de E une un vértice de V1 y otro de V2
g)Un grafo bipartido completo si V=V 1 UV 2 y dos vértices de V están unidos por una arista de E si y solo si un vértice está en V1 y el otro en V2. Se denota por Kr,s al grafo bipartido completo donde V1 tiene r vértices y V2 tiene s vértices
¿Cómo se implementan en java?

Árboles Binarios: Implementación de forma Recursiva


En esta forma de implementación, un árbol puede definirse como un dato (al que llamamos raíz) seguido de un subárbol izquierdo y otro subárbol derecho.

public class ArbolB<E>{

private E raiz;

private ArbolB<E> izq;

private ArbolB<E> der;


[...]

}

Grafo: Implementación

tgrafo Crear(void){

tnodo aux;


aux = (tnodo)malloc(sizeof(struct nodo));

if (aux == NULL) {

error(\"Error en Crear.\");

} else {

aux->nodo = 0;

aux->etiq = NULL;

aux->ady = NULL;

aux->inc = NULL;

aux->sig = NULL;

return aux;

Equipo:

Rubí Beltrán Rugerio

Gabriela Montiel Degante