Tmp_25567 Capítulo 4 1166872268

Capítulo 4
ÁRBOLES

4.1 Definiciones.- Un árbol es un grafo en el que cualesquiera dos vértices están conectados por exactamente un camino. Un árbol es un grafo conexo simple y sin circuitos(acíclico). Como un árbol no tiene circuitos, tampoco puede tener arcos múltiples ni bucles.

Raíz.- Algunas veces, un vértice o nodo del árbol es distinguido llamándolo raíz.
Nodo Hijo / Nodo Padre.- Sedice que un nodo es padre de un nodo si existe un enlace desde hasta (en ese caso, también decimos que es hijo de ). Sólo puede haber un único nodo sin padres, que es el nodo raíz.
Hojas.- Dado unárbol con raíz se denominan hojas a los nodos de distintos de que tienen grado 1. En otras palabras, son los nodos que no tienen hijos.
Rama.- A los nodos distintos de la raíz y que no son hojas delárbol se les denomina rama o vértices internos. Son los nodos que a la vez son hijos de un nodo y padres de uno o más nodos.
Nivel o Profundidad.- Se denomina nivel o profundidad de un nodo en unárbol con raíz, a la longitud del camino que une a la raíz con dicho nodo.
Altura.- La altura de un árbol con raíz es el mayor de los niveles de sus nodos (el camino más largo entre la raíz y el nodo másprofundo del árbol).
Subárbol.- Un subárbol de un grafo G es un subgrafo que es además un árbol. Es decir, si es un nodo de un árbol con raíz , el subárbol de que contiene a como raíz es elsubgrafo del árbol formado por el nodo , todos sus hijos y todas las aristas incidentes en sus hijos.

Bosque.- Un bosque es un conjunto de uno o más árboles, dicho de otra forma es la unión disjunta deárboles. De forma equivalente, un bosque es un grafo acíclico.


4.2 Clasificación.-
Árbol k-ario.- Un árbol es llamado k-ario, si cada nodo tiene como máximo hijos. El siguiente ejemplo es un árbol3-ario.

Árbol Binario.- Un caso particularmente importante es el de un árbol 2-ario, al cual se denomina árbol binario.

Árbol Completo.- Si todos los nodos del árbol exceptuando las hojas, poseen...