6.4.3 Clasificación (altura, número de nodos)

Los árboles se pueden definir como un tipo restringido de grafo.

Un grafo se define de la siguente manera: Un grafoconsiste de un número de nodos (puntos o vértices) y un grupode arcos que unen parejas de nodos. A todos los pares de nodos unidos porun arco se les llama nodos adyacentes. Los arcos pueden t ener una direccióndeterminada, generando así un grafo dirigido, el cual de lo contrariosería no-dirigido. (También existen los grafos mixtos).

Por convención a los nodos de un grafo sele representa con círculos y los arcos que los conectan como líneas(no-dirigido) o flechas (dirigido).

Los árboles son entonces un subconjunto importantede los grafos, y son una herramienta útil para describir estructurasque representan algún tipo de jerarquía.

Un árbol dirigido tiene un nodo al que sele llama "raíz" y de este nodo parten todas las conexiones a losdemás nodos. A los nodos terminales se les llama "hojas" y a todoslos demás se les llama nodos intermedios.

De acuerdo al número de arcos que partende cada nodo en un árbol, este se puede clasificar en diferentescategorías. Así se tienen árboles binarios, árboles2-3-4, árboles rojo-negro, árboles B, etc.

A los nodos que dependen de otro nodo tambiénse les conoce como nodos "hijos" o descendientes y al otro se le llamanodo "padre".

De esto de puede concluir que cada nodo padre esuna raíz de un sub-árbol.

El número de sub-árboles que tieneun nodo determinan el grado del nodo. Naturalmente el grado de lashojas es de cero. Por convención al nodo raíz de arbol sele considera el nivel cero del árbol.

Cuando se tienen varios árboles en un conjunto,al conjunto se le llama bosque.

• Altura de un nodo: Es la longitud del caminomás largo desde el nodo hasta una hoja que sea decendiente de estenodo.
• Altura de un árbol = altura del nodo raíz.

Para poder realizar búsquedas eficientes en árbolesse manejan dos características: Los árboles pueden estarbalanceados por altura o por peso.

 

• Arbol balanceado por altura: en dóndetodos los hijos o nodos hoja se intentan mantener a la misma distanciade la raíz.
• Arbol balanceado por peso: en dónde losnodos más visitados o utilizados se mantienen a poca distancia dela raíz.

6.4.4 Arboles con peso

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. 

6.4.5 Recorrido de un árbol: pre orden, inorden, postorden

Árbol binario 

• Pre orden: (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: 

1. Visite la raíz 

2. Atraviese el sub-árbol izquierdo 

3. 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: 

1. Atraviese el sub-árbol izquierdo 

2. Visite la raíz 

3. 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: 

1. Atraviese el sub-árbol izquierdo 

2. Atraviese el sub-árbol derecho 

3. Visite la raíz 

En general, la diferencia entre pre orden, 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 pre orden, 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 

6.5 Redes (Teorema de flujo, máximo, teorema de flujo mínimo, pareos, redes de petri)

Una Red de Transporte es una gráfica dirigida, simple, con pesos y que debe cumplir las siguientes: Poseer una fuente o vértice fijo que no tiene aristas de entrada. Poseer un sumidero o vértice fijo que no tiene arista de salida El peso Cij de la arista dirigida de i a j llamado capacidad de “ij” es un número no negativo. 

Teorema de flujo máximo. Siendo G una red de trasporte, un flujo máximo es un flujo con valor máximo. En general, habrá varios flujos con el mismo valor máximo. La idea es sencilla: comenzar con cierto flujo inicial e incrementar de forma iterativa hasta que no pueda mejorarse más. El flujo resultante será el máximo. Para aumentar el valor de un flujo dado, debemos determinar un camino de la fuente al sumidero e incrementar el flujo a lo largo de ese camino. 

Teorema del flujo mínimo. En lo que respecta a las redes, un corte es un conjunto de corte en el cual quedando partes disjuntas del conjunto de vértices, V1 y V2 que, situados en la red, dejan la fuente en una de ellas y al sumidero en la otra. Se llama capacidad de un corte a la suma: Capacidad (v,w) ; vV1, w?V2 V1es la parte que contiene a la fuente V2 es la parte que contiene al sumidero Sea F un flujo en G y sea (P, P) un corte en G. Entonces la capacidad de (p, p) es mayor o igual que el valor de F.

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.

6.6 Aplicaciones de grafos y arboles

¿Qué es un grafo? Recordemos que un grafo G es el par (V, A) que representa una relación entre un conjunto de Vértices y otro de Aristas. Un vértice puede tener 0 o más aristas, pero toda arista debe unir exactamente 2 vértices. 

Las aplicaciones más importantes de los grafos son las siguientes:

• Rutas entre ciudades.

• Determinar tiempos máximos y mínimos en un proceso.

• Flujo y control en un programa.

Los grafos son artefactos matemáticos que permiten expresar de una forma visualmente muy sencilla y efectiva las relaciones que se dan entre elementos de muy diversa índole.

Un grafo simple está formado por dos conjuntos:

• Un conjunto V de puntos llamados vértices o nodos.

• 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. En un grafo simple entre dos nodos sólo hay un arco. Si hay más de un arco hablamos de un multígrafo.