Árboles

Unidad II:
Arboles
Por: Alfredo Leal Pérez
Juan Pablo López Morales

Definición
• Un grafo G se dice que es un árbol si es un
grafo conexo y además no existe ningún
circuito en él.

Figura2.1

Terminología
• Sea T un árbol:
– Un árbol enraizado es un árbol donde existe un
vértice distinguido o especial llamado raíz.
– A cada vértice de grado uno se le llamara vértice
hoja, ovértice termina
– A cada vértice de grado 2 o mayor se le llamara
vértice rama, o vértice intermedio.

Terminología
• El nivel de un vértice v es la longitud del camino del
nodo raíz a vértice v.• La altura del árbol enraizado es el mayor nivel que
tienen los nodos.
• Los hijos de un nodo son los vértices adyacentes al
nodo y que están en un nivel mayor que el nodo.

Terminología
•Si v es un hijo de w, w se dice padre de v.
• Si v y w son hijos de un mismo padre se llaman
hermanos.
• Si v está en el camino de la raíz a w se dice que v es
un ancestro de w o que w es undescendiente de v.

Terminología

Ejemplo

Arboles de expansión mínima
• Dado un grafo conexo, no dirigido y con pesos en las
aristas, un árbol de expansión mínima es un árbol
compuesto portodos los vértices y cuya suma de sus
aristas es la de menor peso.

Árbol de expansión mínima

Árbol de expansión mínima
• De la imagen anterior el árbol de expansión mínima
seria el primer árbolde expansión cuyo peso total es
6.
• El problema de hallar el Árbol de Expansión Mínima
(MST) puede ser resuelto con varios algoritmos, los
mas conocidos con Prim y Kruskal.

Arboles binarios• Un árbol binario es un árbol enraizado donde cada
nodo tiene a lo más dos hijos.
– Cada hijo se designa por el calificativo hijo
derecho o hijo izquierdo.
– El árbol binario se dice árbolbinario completo si
todo padre tiene exactamente dos hijos.

• Un árbol binario es completo, si todo elemento no
terminal tiene asociados exactamente dos
subárboles no vacíos. Eso equivale a decir...