6. ARBOLES Y REDES

6. ARBOLES Y REDES

1. 6.2. ÀRBOLES CON PESO 6.2.1 RECORRIDO DE UN ÀRBOL

   • Dado un grafo conexo, un árbol recubierto mínimo de ese grafo es un subgrafo que tiene que ser un árbol y contener todos los vértices del grafo inicial. Cada arista tiene asignado un peso proporcional entre ellos, que es un número representativo de algún objeto, distancia, etc... , y se usa para asignar un peso total al árbol recubierto mínimo computando la suma de todos los pesos de las aristas del árbol en cuestión. Un árbol recubridor mínimo o un árbol expandido mínimo es un árbol recubridor que pesa menos o igual que otros árboles recubridores. Todo grafo tiene un bosque recubridor mínimo. En el caso de un empate, porque podría haber más de un árbol recubridor mínimo; en particular, si todos los pesos son iguales, todo árbol recubridor será mínimo. De todas formas, si cada arista tiene un peso distinto existirá sólo un árbol recubridor mínimo. Árbol abarcador de menor peso. Vamos a considerar de nuevo el problema de la red de conducción, pero ahora añadiremos un ingrediente nuevo
     • Preorden: (raíz, izquierdo, derecho). Para recorrer un árbol binario no vacío en preorden, hay que realizar las siguientes operaciones recursivamente en cada nodo, comenzando con el nodo de raíz:
       • *Visite la raíz *Atraviese el sub-árbol izquierdo *Atraviese el sub-árbol derecho
     • Inorden: (izquierdo, raíz, derecho). Para recorrer un árbol binario no vacío en inorden (simétrico), hay que realizar las siguientes operaciones recursivamente en cada nodo:Inorden: (izquierdo, raíz, derecho). Para recorrer un árbol binario no vacío en inorden (simétrico), hay que realizar las siguientes operaciones recursivamente en cada nodo:
       • *Atraviese el sub-árbol izquierdo *Visite la raíz *Atraviese el sub-árbol derecho1. *Atraviese el sub-árbol izquierdo *Visite la raíz *Atraviese el sub-árbol derecho
     • Postorden: (izquierdo, derecho, raíz). Para recorrer un árbol binario no vacío en postorden, hay que realizar las siguientes operaciones recursivamente en cada nodo:Postorden: (izquierdo, derecho, raíz). Para recorrer un árbol binario no vacío en postorden, hay que realizar las siguientes operaciones recursivamente en cada nodo:
       • *Atraviese el sub-árbol izquierdo *Atraviese el sub-árbol derecho *Visite la raíz *Atraviese el sub-árbol izquierdo *Atraviese el sub-árbol derecho *Visite la raíz
       • En general, la diferencia entre preorden, inorden y postorden es cuándo se recorre la raíz. En los tres, se recorre primero el sub-árbol izquierdo y luego el derecho
         • En preorden, la raíz se recorre antes que los recorridos de los subárboles izquierdo y derecho En inorden, la raíz se recorre entre los recorridos de los árboles izquierdo y derecho, y En postorden, la raíz se recorre después de los recorridos por el subárbol izquierdo y el derecho. Preorden (antes), inorden (en medio), postorden (después).

2. 6.3 REDES

   • Teorema de flujo máximo y mínimo. Definición: Existe un flujo que viaja desde un único lugar de origen hacia un único lugar de destino a través de arcos que conectan nodos intermediarios. Los arcos tienen una capacidad máxima de flujo, y se trata de enviar desde la fuente al destino la mayor cantidad posible de flujo
     • Usos del Algoritmo de flujo máximo y mínimo: Este algoritmo se utiliza para reducir los embotellamientos entre ciertos puntos de partida y destino en una red. Por ejemplo: 1. Sistema de Vías Públicas. 2. Transporte de petróleo desde la refinería hasta diversos centros de almacenamiento. 3. Distribución de energía eléctrica a través de una red de alumbrado público
       • REDES DE PETRI
         • Una red de Petri es un grafo orientado con dos tipos de nodos: lugares (representados mediante circunferencias) y transiciones (representadas por segmentos rectos verticales). Los lugares y las transiciones se unen mediante arcos o flechas. Su mecanismo básico, si bien, la representación de grandes sistemas es costosa.
           • Para facilitar su uso en diferentes campos de aplicación, el modelo original se ha extendido en dos aspectos: 1. Introducción de modificaciones estructurales para incrementar la potencia o la comodidad de modelado o para facilitar la solución de los problemas de análisis. 2. Definición de redes de Petri temporizadas que se pueden utilizar para analizar cuantitativa mente las prestaciones del sistema modelado.
             • Definiciones básicas: · Una plaza p es entrada de una transición t si existe un arco desde p a t. · Una plaza p es salida de una transición t si existe un arco desde t a p.
       • REDES DE PAREO
         • Dado un grafo, un pareo es un subconjunto de aristas los cuales no tiene vértices en común.

3. 6.1 ÀRBOLES

   • Definición: Un árbol es un grafo no dirigido conexo que no contiene circuitos.
     • Una colección de árboles disjuntos se llama bosque. Un vértice de grado 1 en un árbol se le llama hoja o nodo terminal, y un vértice de grado mayor que 1 recibe el nombre de nodo rama o nodo interno. Ejemplo: En el árbol i) b, c, d, f, g, i, son nodos hoja a, e, h, son nodos rama
     • Existen algunas propiedades que señalaremos con relación a los árboles. 1) Existen un único paseo entre dos vértices cualesquiera en un árbol. 2) El número de vértices es mayor que el número de aristas en un árbol. 3) Un árbol con dos o más vértices tiene al menos una hoja.
       • 6.1.1 Componentes y propiedades
         • Aristas :
           • Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos. Si la arista carece de dirección se denota indistintamente {a, b} o {b, a}, siendo a y b los vértices que une. Si {a ,b} es una arista, a los vértices a y b se les llama sus extremos. • Aristas Adyacentes: Se dice que dos aristas son adyacentes si convergen en el mismo vértice. • Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial y el final son el mismo. • Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo. • Cruce: Son dos aristas que cruzan en un punto.
         • Vértices :
           • Son los puntos o nodos con los que esta conformado un grafo. Llamaremos grado de un vértice al número de aristas de las que es extremo. Se dice que un vértice es `par' o `impar' según lo sea su grado. • Vértices Adyacentes: si tenemos un par de vértices de un grafo (U, V) y si tenemos un arista que los une, entonces U y V son vértices adyacentes y se dice que U es el vértice inicial y V el vértice adyacente. • Vértice Aislado: Es un vértice de grado cero. • Vértice Terminal: Es un vértice de grado 1.
         • Valencia de un vértice Es el numero de lados que salen o entran a un vértice.
           • 6.1.2 Clasificación por altura y número de nodos
             • Altura
               • La altura (o profundidad) de un árbol es el largo del mayor camino de la raíz a una hoja. Dado un camino < v0, v1, v2,..., vk > el largo de este camino es k. Por lo cual el largo de un camino es igual al número de arcos del camino.
             • Número de Nodos
               • Nodo: Es el término usado para referirse a un vértice de un árbol con raíz. 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.
                 • 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 yd.
                   • 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.
     • Existen además otros resultados sobre la caracterización de árboles. 1) Un grafo en el cual existe un único paseo entre cada par de vértices es un árbol. 2) Un grafo conexo con e = v - 1 es un árbol. 3) Un grafo con e = v - 1 que no tiene circuitos es un árbol.

Images and files in the map