Unidad 2

Def.

2.1.- Un árbol es un
grafo sencillo no dirigido
que es a la vez conexo y
acíclico.



Def. 2.2.-En un árbol, a los nodos o
vértices de grado uno se les conoce
como nodos hojas onodos terminales y
a los nodos de grados mayor a uno se
les conoce como nodos ramas o nodos
internos.

Podemos definir tres propiedades que
caracterizan a un árbol:
1. Existe una únicatrayectoria entre cada
par de vértices de un árbol.
2. El número de vértices es siempre igual
al número de aristas más uno.
3. Un árbol con dos o más vértices tiene al
menos dos hojas.



Def.2.3.- Un árbol de expansión de un
grafo conexo no dirigido G=(N,A) es un
árbol libre con el conjunto de nodos N
que es un subgrafo de G; esto es, un
árbol de expansión es conexo, acíclico y
tiene atodo N como nodos y a parte de
A como conjunto de aristas.

 Def.

2.4.- Un árbol de expansión
de un grafo ponderado (con
pesos) conexo y no dirigido en el
cual la suma de los costos de susaristas sea mínima se denominará
árbol de expansión mínimo.

INICIO
%Se selecciona una arista de costo mínimo, digamos {s,w}
dentro de A

Nodos = [s,w];



Resto=N-Nodos;Aristas={[s,w]};










Mientras Resto { } hacer
Inicio
%Se selecciona una arista de costo mínimo [k,w] en A tal
que (k este en Nodos) y (w en resto);
Aristas=Aristas + {[k,w]};Nodos = Nodos + {[w]};
Resto= Nodos - {[w]};
Fin
FIN

Def.

2.5.- Un árbol binario
es un árbol con raíz en el
cual cada nodo puede
tener como máximo dos
hijos.

 Def

2.6.-Se llamarecorrido de
un árbol al proceso que
permite acceder una sola vez
a cada uno de los nodos del
árbol para examinar el
conjunto completo de nodos.



INORDEN

› Recorrer el subarbol izquierdoen inorden.
› Examinar la raíz.
› Recorrer el subarbol derecho en inorden.



PREORDEN

› Examinar la raíz.
› Recorrer el subarbol izquierdo en preorden.
› recorrer el subarbol derecho en...