Árboles

Unidad VI
Árboles
Árboles generadores
Un árbol T es un árbol generador de un grafo G si T es un subgrafo de G que contiene todos los vértices G.
Árboles generadores minimales.
Un árbol generadormínimo es el que resulta de la construcción en primer lugar de un árbol generador, pero con la característica de ser el de menor peso del grafo al cual genera.
Tipos de algoritmos para determinarárboles generadores.
1. Algoritmo de Prim.
Construye un árbol en forma iteraría, agregando lados hasta obtener un árbol generador mínimo. En cada iteración se coloca un lado de peso mínimo que noforme un circuito con el árbol que se ha construido con iteraciones anteriores.
2. Algoritmo de Kruskal.
Este algoritmo parte con un grafo T que contiene inicialmente todos los vértices y ningúnlado en cada iteración, se agrega un lado a T de peso mínimo tal que no complete un circulo en T. cuando T tenga n-1 lados se termina.
Árboles etiquetados.
+
+
(3-(2*x))+((x-2)-(3+x)
2
2
x
x
33
x
x
+
+
-
-
x
x
2
2
*
*
3
3
-
-
--
--

Recorridos
Recorrer significa visitar los nodos de forma simétrica, de tal manera que todos los nodos del mismo sean visitados una solavez.
Existen tres formas diferentes de efectuar el recorrido y todas ellas de naturaleza recursiva.
1. Recorrido Preorden.
A
A
En el que se procesa el nodo y después su proceso recursivamentesus hijos.
Preorden (Polaca).
C
C
B
B
-Visitar la raíz.
F
F
E
E
D
D
-Visitar el hijo izquierdo.
G
G
-Visitar el hijo derecho.ABDECFG
2. Recorrido Postorden.
Donde el nodo se procesa recursivamente el hijo izquierdo, luego se procesa el nodo actual y finalmente se procesa recursivamente el hijo derecho.
A
A
Postorden(Polaca Inversa).
C
C
-Visitar hijo izquierdo.
B
B
-Visitar hijo derecho
F
F
G
G
E
E
D
D
-Raíz

DBEAFCG
3. Recorrido Inorden.
En este se procesa recursivamente el hijo...