ARBOLES

Un árbol binario es un conjunto finito de elementos que está vacio o dividido en tres subconjuntos separados. El primer subconjunto contiene un único elemento llamado raíz del árbol. Los otros 2 subconjuntos son por si mismos árboles binarios y se les conoce como subárboles izquierdo y derecho del árbol original. Cada elemento de un árbol binario se denomina nodo. La ausencia de una ramificación indica un subárbol vacio. 

Si A es la raíz de un árbol binario y B es la raíz de su subárbol izquierdo o derecho, se dice que A es el padre de B y se dice que B es el hijo izquierdo o derecho de A. Un nodo que no tiene hijos se denomina hoja. El nodo n1 es un ancestro del nodo n2 ( y n2 es un descendiente de n1) si n1 es el padre de n2 o el padre de algún ancestro de n2. 2 nodos son hermanos si son los hijos izquierdo y derecho del mismo padre. 

Si cada nodo que no es hoja es un árbol binario tiene subárboles izquierdo y derecho que no están vacíos, el elemento se clasifica como árbol estrictamente binario. Un árbol estrictamente binario con n hojas siempre contiene 2n – 1 nodos. El nivel de un nodo en árbol binario se define del modo siguiente: la raíz del árbol tiene el nivel 0, el nivel de cualquier otro nodo en el árbol es uno más que el nivel de su padre. 

La profundidad de un árbol binario es el máximo nivel de cualquier hoja en el árbol. Esto es igual a la longitud de la trayectoria más larga de la raíz a cualquier hoja. Un árbol binario completo de profundidad d es un árbol estrictamente binario que tiene todas su hojas en el nivel d.  

Si un árbol binario contiene m nodos en el nivel I, contiene cuando mucho 2m nodos en el nivel I + 1. Dado que un árbol binario solo contiene un nodo en el nivel 0 (raíz), puede contener un máximo de 2I nodos en el nivel I. Un árbol binario completo de profundidad d es el árbol que contiene 2I nodos en el nivel I entre 0 y d. La cantidad total de nodos en un árbol binario completo de profundidad d, tn es igual a la suma de la cantidad de nodos en cada nivel entre 0 y d. 

Un árbol binario de profundidad d es un árbol binario casi completo si: 

  • Cualquier nodo nd a un nivel menor que d – 1tiene 2 hijos.
  • Para cualquier nodo nd en el árbol con un descendiente derecho en el nivel d, nd debe tener 1 hijo izquierdo y cada descendiente izquierdo de nd es una hoja en el nivel d o tiene 2 hijos .

Los nodos de un árbol binario casi completo se enumeran para que se asigne a la raíz el No.1, se asigne a un hijo izquierdo 2 veces el número asignado a su padre y se asigne a un hijo derecho 1 más el doble del No. asignado a su padre. Un árbol estrictamente binario casi completo con n hojas tiene 2n – 1nodos, como cualquier otro árbol estrictamente binario con n hojas. Un árbol binario casi completo con n hojas que no es estrictamente binario tiene 2n nodos. 

Solo hay un árbol binario casi completo con n nodos. Este árbol es estrictamente binario si y solo si n es impar. 

Se aplican varias operaciones primitivas a un árbol binario. Si p es un apuntador a un nodo nd de un árbol binario, la función info(p) retorna el contenido de nd. Las funciones left(p), right(p), father(p) y brother(p) retornan apuntadores al hijo izquierdo de nd, al hijo derecho de nd, al padre de nd y al hermano de nd, respectivamente. Estas funciones retornan el apuntador null si nd no tiene hijo izquierdo, hijo derecho, padre o hermano. 

Por último, las funciones lógicas isleft(p) e isright(p) retornan el valor true si nd es un hijo izquierdo o derecho, respectivamente, de algún otro nodo en el árbol , y false en caso contrario. Un árbol binario es una estructura de datos útil cuando deben tomarse decisiones en dos sentidos en cada punto de un proceso. 

Otra operación común es recorrer un árbol binario, es decir, pasar por todo el árbol numerando cada uno de sus nodos una vez. Hablamos de visitar cada nodo mientras se enumera. Un árbol binario no vacio puede ser recorrido de 3 maneras distintas: Orden previo, orden y orden posterior. 

El recorrido en orden previo (Orden de primero profundidad) sigue 3 operaciones: 

  • Visitar la raíz.
  • Recorrer el subárbol izquierdo en orden previo.
  • Recorrer el subárbol derecho en orden previo.

El recorrido en orden (Orden simétrico) es así: 

  • Recorrer el subárbol izquierdo en orden
  • Visitar la raíz.
  • Recorrer el subárbol derecho en orden.

El recorrido en orden posterior se presenta de la siguiente manera. 

  • Recorrer el subárbol izquierdo en orden posterior.
  • Recorrer el subárbol derecho en orden posterior.
  • Visitar la raíz.

Existe un árbol binario que presenta la propiedad de que todos los elementos en el subárbol izquierdo de un nodo n son menores que el contenido de n, y que todos los elementos en el subárbol derecho de n son mayores o iguales que el contenido de n. Una árbol binario que tiene esta propiedad se denomina árbol de búsqueda binaria. 

Igual que en el caso de los nodos de lista, los nodos de árboles se implementan como elementos de un arreglo o como asignaciones de una variable dinámica. Cada nodo contiene campos info, left, right y father. Los campos left, right y father de un modo apuntan al hijo izquierdo, al hijo derecho y al padre del nodo, respectivamente. 

Bajo esta representación, las operaciones info(p), left(p), right(p) y father(p) se implementan mediante referencia a node[p].info, node[p].left, node[p].right, y node[p].father, respectivamente. Las operaciones isleft(p), isright(p) y brother(p) se implementan en términos de las operaciones left(p), right(p) y father(p), según se describió en la sección anterior. 

Para implementar isleft e isright en forma más eficiente, también incluimos dentro de cada nodo una bandera isleft adicional. El valor de esta bandera es TRUE si el nodo es un hijo izquierdo y FALSE en caso contrario. La raíz se identifica inequívocamente mediante un valor NULL(-1) en su campo father. El apuntador externo al árbol por lo general apunta a su raíz. 

O bien, el signo del campo father puede ser negativo si el nodo es un hijo izquierdo, o positivo si es un hijo derecho. Entonces, el valor absoluto del campo father proporcionaría el apuntador a un padre de nodo. Por tanto, las operaciones isleft o isright sólo necesitarán examinar el signo del campo father. Para implementar brother(p) con más eficiencia, también incluimos un campo brother adicional en cada nodo. 

Una vez codificado lo anterior se observa que la lista disponible no es un árbol binario, sino una lista lineal cuyos nodos están vinculados mediante el campo left. Cada nodo es un árbol se toma del grupo disponible cuando ya nos e usa. Esta representación se denomina representación de arreglo vinculado de un árbol binario. 

Las operaciones info(p), left(p), right(p) y father(p) se implementarían mediante referencias a p-> info(p), p-> left(p), p-> right(p) y p-> father(p), respectivamente. Bajo esta implementación, no se necesita una lista disponible explicita. Las rutinas getnode y freenode simplemente asignan y liberan nodos usando las rutinas mallos y free. Esta se denomina la representación dinámica de nodos de un árbol binario. 

Tanto las representaciones de arreglo vinculado como la representación dinámica de nodos son implementaciones de una representación vinculada abstracta(también denominada representación de nodos) en la cual apuntadores explícitos vinculan los nodos de un árbol binario. 

Por definición, los nodos de hoja no tienen hijos. En ocasiones, se usan 2 conjuntos de nodos separados para hojas y los que no son hojas. Los nodos que no son hojas contienen campos info, left y right. . se asignan como registros dinámicos o como un arreglo de registros controlados usando una lista disponible. Los nodos hojas no contienen un campo left o right y se conservan como una arreglo info único que se asigna secuencialmente conforme se necesita. 

Cuando se establece la diferencia entre los nodos de hojas y los no hojas, los no hojas se llaman nodos internos y los hojas se llaman nodos externos. La representación de arreglo implícito también se denomina representación secuencial, en contraste con la representación vinculada que se presento antes, porque permite que un árbol implemente en un bloque contiguo de memoria (arreglo) y no mediante apuntadores que conectan nodos ampliamente separados. 

Cuando se va a representar un árbol la representación secuencial es más sencilla, aunque es necesario asegurar que todos los apuntadores se encuentren dentro de los límites del arreglo, ahorra espacio de almacenamiento para los árboles de los que se tiene la seguridad que son casi completos, también emplea con eficiencia el espacio en árboles a los que solo les faltan unos nodos para ser casi completos o cuando se eliminan sucesivamente nodos de un árbol que se origina como casi completo. La representación secuencial únicamente puede usarse en un contexto en el cual solo se requiere un árbol único o en donde se fija con anticipación la cantidad de árboles necesarios y cada uno de sus tamaños máximos. 

La representación vinculada permite un uso más flexible del conjunto de nodos. En la representación vinculada, un nodo particular se coloca en cualquier posición en cualquier árbol, en tanto que la representación secuencial, un nodo solo puede inicializarse si se necesita en una posición específica de un árbol específico. La representación dinámica de nodos, la cantidad total de árboles y nodos solo está limitada por la cantidad de memoria disponible. 

Las rutinas en c pretrav, intrav y postrav imprimen el contenido de un árbol binario en orden previo, en orden y orden posterior, respectivamente. 

Es posible ejecutar varias operaciones en una lista de elementos. Entre estas operaciones están agregar un elemento nuevo a la parte delantera o posterior de la lista, , suprimir el primer o último elemento existente de la lista, recuperar el késimo o el último elemento de la lista, insertar un elemento después o antes de un elemento determinado. Desarrollar una lista con elementos determinados es una operación adicional que se requiere con frecuencia. 

Un árbol es un conjunto finito de elementos no vacio en el cual un elemento s denomina la raíz y los restantes se dividen en m >= 0 subconjuntos separados, cada uno de los cuales es por sí mismo un árbol. Cada elemento de un árbol se denomina nodo del árbol. 

Cada nodo puede ser la raíz de un árbol con 0 o más subárboles. Un nodo sin subárboles es una hoja. Usamos los términos padre, hijo, hermano, ancestro, descendiente, nivel y profundidad en el mismo sentido que los empleamos para árboles binarios. También definimos el grado de un nodo en un árbol como el número de sus hijos. 

Un árbol ordenado se define como un árbol en el que los subárboles de cada nodo forman un conjunto ordenado. El primer hijo de un nodo en un árbol ordenado se denomina con frecuencia el hijo más viejo de este nodo y el último hijos e denomina el más joven. Un bosque es un ordenado conjunto de árboles ordenados. 

Surge la cuestión de sí un árbol binario es un árbol. Todo árbol binario, excepto el árbol binario vacio, es en realidad un árbol. Sin embargo, no todos los árboles son binarios. Un nodo de árbol puede tener más de 2 hijos, en tanto que un árbol binario no puede. Un árbol binario que no es vacio es aquel cuyos nodos tienen un máximo de 2 subárboles, los cuales tienen agregada la definición de “izquierdo” o “derecho”. 

Para declarar un árbol en C de inmediato pensamos en 2 alternativas: se declara un arreglo de nodos de árbol o se asigna una variable dinámica para cada nodo creado. Sin embargo ¿Cuál será la estructura de cada nodo individual? En la representación de árbol binario, cada nodo contiene un campo de información y 2 apuntadores hacia sus 2 hijos. Pero ¿Cuántos apuntadores debe contener un nodo de árbol?. La cantidad de hijos de un nodo es variable y puede ser tan grande o pequeña como sea necesario.

 

______________________________________________________________________

 

Algoritmo de Dijkstra para Rutas más Cortas

 

El problema de la ruta más corta y el problema de flujo máximo son los dos tipos de problemas de flujos en redes.
Ambos se pueden resolver utilizando progamación lineal o programación lineal entera, tal como se discutió en clases pasadas. Sin embargo, debido a que el método simplex es de complejidad exponencial, se prefiere utilizar algoritmos que aprovechen la estrutura en red que se tiene para estos problemas.

El problema de la ruta más corta, aparece en una gran cantidad de aplicaciones. Por ejempo, entre las discutidas por [Bertzekas98] se encuentra la de ruteo en redes de datos que se describe en la sección que sigue.
 

Ruteo en Redes de Datos

Una red de comunicaciones involucra un conjunto de computadoras (nodos) conectadas mediante enlaces de comunicacion (arcos), que transfiere paquetes (grupos de bits) desde determinados nodos origen a otros nodos
destino. La forma más común para seleccionar la trayectoria (o ruta) de dichos paquetes, se basa en la formulación
de la ruta más corta. En particular a cada enlace de comunicación se le asigna un escalar positivo el cual se puede ver como su longitud.

Un algoritmo de ruteo de trayectoria más corta, rutea cada paquete a lo largo de la trayectoria de longitud mínima
(ruta más corta) entre los nodos origen y destino del paquete.

Hay varias formas posibles de seleccionar la longitud de los enlaces. Aquíi describimos solamente dos:

La forma más simple es que cada enlace tenga una longitud unitaria, en cuyo caso, la trayectoria más corta es simplemente una trayectoria con el menor número de enlaces.
De una manera más general, la longitud de un enlace puede depender de su capacidad de transmision y su carga de tráfico.
La situación es encontrar la trayectoria más corta. Esperamos que dicha trayectoria contenga pocos enlaces no
congestionados; de esta forma los enlaces menos congestionados son candidatos a pertenecer a la ruta. Hay algoritmos de ruteo especializados que también pueden permitir que la longitud de cada enlace cambie en el tiempo, dependiendo del nivel de tráfico de cada enlace. De esta forma un algoritmo de ruteo se debe adaptar a sobrecargas temporales y rutear paquetes alrededor de nodos congestionados.
Dentro de este contexto, el algoritmo de ruta más corta para ruteo opera contínuamente, determinando la
trayectoria más corta con longitudes que varían en el tiempo.

Una característica peculiar de los algoritmos de ruteo de trayecoria más corta es que con frecuencia utilizan
comunicación y computación asíncrona y distribuida. En particular, cada nodo de la red de comunicación:

monitorea las condiciones de trafico de sus enlaces adyacentes,
calcula estimados de sus distancias más cortas a varios destinos y pasa estos estimados a otros nodos, quienes ajustan sus propios estimados, y así sucesivamente.
Este proceso es basado sobre algoritmos de ruta más corta estándar, los cuales pueden ser ejecutados en forma
síncrona, como los descritos en [BERTZEKAS 91] o asíncronamente, como los que se describen en [BERTZEKAS 98].
La comunicación y computación asíncrona y distribuida, acarrea problemas de sincronización por lo que se requiere del uso de técnicas de descripción (o especificación) formal, de las cuales las más utilizadas son las redes de Petri,
(o PN por sus siglas en inglés: Petri Nets) las cuales se abordan más ampliamente en otros cursos de sistemas distribuidos. Permítasenos sólo decir, que las PN permiten obtener modelos de concurrencia y sincronización de sistemas distribuidos a traves de automatas conformados por dos tipos de nodos (plazas y
transiciones) y un conjunto de marcas (tokens). En esta misma página se encuentra una gran cantidad de
información sobre PN.
En esta sección se abordarán los algoritmos de rutas más cortas que son empleados por los algoritmos de ruteo,
que es la parte fina de dichos algoritmos. De esta manera problemas de sincronización son dejados de lado.
 

Alternativas de Solución del Problema de Rutas Más Cortas

El modelo formal de un problema de ruta más corta ha sido presentado con anterioridad. Dicho modelo puede ser
resuelto mediante Programación Lineal. Si bien es cierto que la Programación Lineal (PL) resulta útil para ciertas
aplicaciones prácticas, no hay que olvidar que PL es de complejidad exponencial, de esta manera, no se puede tener confianza en ella para casos de redes con un gran número de nodos. Por esta razón, se requiere de algoritmos que exploten la estructura en red del problema de ruta más corta. Entre estos algoritmos se tienen dos tipos:

a) Algoritmos de Programación Dinamica y
b) Algoritmos de Etiquetado.

En esta clase introduciremos los algoritmos de equiquetado.

Existen varios algortimos de etiquetado, dentro de los cuales, los más conocidos y utilizados son los métodos de
Dijsktra, los cuales se tocarán en esta sección.
 

Algoritmos de Dijkstra Para Ruta Más Corta

Estos son algoritmos de etiquetado, los cuales, en términos generales, encuentran la ruta más corta entre dos nodos, incial a y final z, de la siguiente manera:

Los nodos de la red son etiquetados con números. Al principio, todos tienen la etiqueta 00 excepto el nodo inicial a que tiene la etiqueta 0. Los arcos tienen un peso wij que representa la distancia del enclace (i, j).
Los algoritmos de Dijkstra renumeran los nodos, de manera que cuando el nodo z tiene una etiqueta permanente, se ha obtenido la solución final.
 

Algoritmos Heurísticos
Como hemos notado anteriormente, el algoritmo para encontrar la red multipunto óptima, con restricciones, puede
algunas veces requerir tiempos de corrida de computadora muy largos, particularmente para redes grandes. Entonces es apropiado considerar los algoritmos heurísticos que proporcionan una solución sub-óptima en general,
con una reducción considerable en el esfuerzo computacional. Así que hay una negociación de por medio entre el
mejoramiento del desempeño de la red, contra el esfuerzo computacional requerido en conseguirlo.

Varios algoritmos han aparecido en la literatura que son apropiados para resolver problemas de conexión multipunto del tipo que estamos considerando. Mencionaremos tres de ellos. También introduciremos un algoritmo desarrollado por Kershenbaum y Chou que unifica estos varios enfoques.

Los algoritmos que se presentarán son el de Esau-Williams, el de Prim y el de Kruskal descrito en sesiones anteriores. Los tres producen un árbol de expansión mínima cuando se eliminan las restricciones. Estos algoritmos difieren en sus requerimientos de tiempo de corrida (su complejidad computacional). En el problema de diseño multipunto con restricciones que hemos estado viendo, también se producen diseños algo diferentes. La experiencia ha mostrado que el algoritmo de Esau-Williams generalmente proporciona diseños de red que están más cerca del óptimo, aunque el algoritmo unificado de Kershenbaum-Chou puede ser modificado para obtener aún mejores resultados.

El algoritmo Esau-Williams, esencialmente busca los nodos que están más alejados del centro (en el sentido de costo) y los conecta a nodos vecinos que proveen el mayor beneficio en costo. El algoritmo de Prim hace lo inverso:
inicialmente selecciona el nodo más cerca del centro (en el sentido de costo), después conecta los nodos que están
más cerca a aquellos que ya están en la red. El algoritmo de Kruskal simplemente conecta los enlaces de menor
costo, uno a la vez. Para aplicación al problema multipunto, las restricciones deben verificarse conforme se hace
una posible conexión.

Kershenbaum y Chou han demostrado que estos tres algoritmos heurísticos, más otros descritos en la literarura, pueden ser considerados casos especiales de un algoritmo unificado apropiado para resolver el problema de la conexión multimpunto. El algoritmo es esencialmente una forma modificada del algoritmo de Kruskal, donde en lugar de conectar sucesivamente enlaces más y más costosos, un factor de peso es usado como medida de comparación.

______________________________________________________________________

GRAFOS

Los grafos son una estructura tipo red, en la que los nodos pueden estar conectados de 0 a n elementos. Cada conexión se denomina arco. Existen varias clasificaciones para los grafos:

 
  • Grafos Conexos y No-Conexos:
    Indican si todos los nodos de un grafo están unidos por medio de arcos o no.
  • Grafos Dirigidos y No Dirigidos:
    Indican si los arcos de un nodo a otro tiene o no dirección. Las direcciones se representan mediante flechas. Si un arco no tiene dirección preestablecida, se asume que es bidireccional.
  • Grafos Ponderados y No Ponderados:
    Indican si los arcos tienen un peso asociado. Típicamente estos pesos se relacionan con costos, tiempos o distancias.


    Otra terminología utilizada es la de camino (arcos necesarios para llegar de un nodo a otro) y ciclo (camino cuyos nodos inicial y terminal son el mismo).

    Matriz de Adyacencias

    Es una forma muy ineficiente de representar al grafo. Consiste en una tabla en donde las abcisas y ordenadas son los nodos, y mediante valores booleanos se indica si hay una conexión de un nodo al siguiente. En grafos no-dirigidos la matriz es simétrica. Si se trata de un grafo ponderado, los valores booleanos se reemplazan por valores enteros o reales.

    Lista de Adyacencias

    Es la manera más común de representar un grafo. Se utiliza una lista encadenada para representar a los nodos del grafo. Cada nodo tiene asociada una lista que representa los arcos que salen de él. El la lista pueden incluirse los pesos si el grafo es ponderado.

    Lista de Arcos

    Esta representación se utiliza principalmente para grafos dirigidos. Maneja una lsita encadenada para representar a todos los nodos del grafo. Cada nodo tiene asociadas una lista de arcos que salen de él y otra lista de arcos que llegan a él. Es más eficiente, aunque más difícil de implementar.

     

    Recorridos de Grafos

  • Depth First (Búsqueda en altura)
    El algoritmo visita a un nodo y posteriormente a todos los nodos adyacentes que no haya visitado. Guarda dónde se quedó mediante una pila auxiliar.
    Cada nodo debe tener un status de "no-visitado", y "visitado" para evitar que el algoritmo se cicle.
    1. Comenzando por el primer nodo del grafo, se inserta en la pila
    2. Sacar el nodo del top de la pila y procesarlo
    3. Cambiar su status a "visitado"
    4. Meter a la pila a todos los nodos adyacentes que tengan status de "no-visitado"
    5. Regresar al paso 2 si la pila no está vacía


     

  • Breadth First (Búsqueda en anchura)
    El algoritmo visita a un nodo y posteriormente a todos sus nodos adyacentes. Guarda dónde se quedó mediante una lista auxiliar.
    Cada nodo debe tener un status de "no-visitado", y "visitado" para evitar que el algoritmo se cicle.
    1. Todos los nodos se incializan con "no-vistado"
    2. Iniciando en el primer nodo del grafo, se inserta en la lista
    3. Sacar el primer nodo de la lista
    4. Modificar su estado a "visitado" y procesarlo
    5. Meter a la lista a todos los nodos adyacentes a él, que no tengan status de "visitado" y que no se encuentren en la lista
    6. Regresar al paso 3 si la lista no está vacía
  •  

     

    PRINCIPAL

     

     

    Google