Grafos-arboles

ÁRBOLES
COMPONENTES
Un árbol es un grafo conexo que no tiene ciclos, lazos ni lados paralelos.
Un árbol tiene diferentes componentes que son:
RAÍZ: Es el nivel más alto de la jerarquía tiene un nivel 0, los vértices inmediatamente debajo de la raíz tienen un nivel 1 y así sucesivamente.
HOJA: Son todos los elementos que están en las puntas de las ramas (es decir, que no tienen hijos).PADRE: Es el nodo de mayor nivel al cual están vinculados lo demás nodos excepto la raíz.
HIJO: son todos los nodos que pueden tener uno o más elementos relacionados con un nivel más bajo.
DESCENDIENTES: Son todos los elementos colocados debajo de un nodo, independientemente de su nivel.
ANCESTROS: Son los elementos colocados en una misma línea de descendencia, antes de un nodo.
PROPIEDADES
Laspropiedades básicas de un árbol son las siguientes:
Es un grafo conexo en donde no existe un camino entre cualquier par de vértices (w, x).
Este grafo no tiene ciclos ni lados paralelos.
Todo árbol con al menos dos vértices tiene al menos una hoja (si se considera al otro vértice la raíz.)

CLASIFICACIÓN
Los árboles se pueden clasificar de acuerdo con su número de nodos y en función de sualtura.
Clasificación por número de nodos
En este caso los árboles pueden ser binarios, trinarios y cuaternarios.
BINARIOS: En este tipo de árbol cada nodo padre tiene como máximo dos hijos, esto es, el nodo puede tener dos ramas, una o ninguna pero nunca puede tener más de dos.
TRINARIOS: En este tipo de árbol cada nodo padre tiene como máximo tres hijos, esto es, el nodo puede tener tresramas, una o ninguna pero nunca puede tener más de tres.
CUATERNARIOS: En este tipo de árbol cada nodo padre tiene como máximo cuatro hijos, esto es, el nodo puede tener cuatro ramas, una o ninguna pero nunca puede tener más de cuatro.
ÁRBOL BINARIO COMPLETO: es aquel en el que cada nodo tiene dos ramas o ninguna.

Clasificación por altura
De acuerdo con este criterio los arboles pueden ser:BALANCEADOS: cuando la diferencia de altura entre sus ramas es máximo 1.
DESBALANCEADOS (cuando la diferencia de altura entre las ramas es mayor de 1.
ÁRBOLES CON PESO
El peso de un árbol es el peso de la raíz.
RECORRIDO DE UN ÁRBOL
Recorrido en orden primero (padre, izquierdo, demás hijos). En este recorrido primero se toma el padre, luego el hijo izquierdo y al final los demás hijos.Recorrido en orden segundo (izquierdo, padre, demás hijos). En este recorrido primero se toma el hijo izquierdo, segundo el padre y al final los demás hijos.
Recorrido en orden final (izquierdo, demás hijos, padres). En este recorrido se toma primero el hijo izquierdo, después los demás hijos y al final el padre.
Teorema del Flujo Máximo
Una vez que hemos modelado una situación específica conuna red de transporte, es importante poder analizar su alcance, esto es, el flujo máximo que puede soportar.
En el caso concreto de las bombas de agua nos interesa saber cuál es la cantidad máxima que es posible suministrar con este sistema de bombeo. Para esto veremos un algoritmo que nos ayudará a determinar este valor tan importante.
Definición 1. Sea R una red de transporte con fuente F,sumidero S, con pesos w(i,j) y con flujo f. Sea n0, n1, … , nk un camino de F = n0 a S = nk, donde las aristas pertenecen a R pero sin considerarlo como un grafo dirigido. Una arista (ni, ni+1) en el camino:
Si está en R decimos que está orientada en forma propia y si no está en R decimos que no está orientada en forma propia.
Dos aristas consecutivas pueden tener las siguientes orientaciones:Primera | Segunda |
Orientada en forma propia | No orientada en forma propia |
Orientada en forma propia | No orientada en forma propia |
No orientada en forma propia | Orientada en forma propia |
No orientada en forma propia | Orientada en forma propia |
Teorema: Sea C: n0, n1, … , nk un camino de F = n0 a S = nk en una red R. Sea f un flujo en R con valores f(i,j). Para las...