Download Árboles por Prieto José.

1
ÁRBOLES.
Un grafo que no tiene ciclos y que conecta a todos los puntos, se llama un árbol. Por tanto un árbol es un grafo
en el que dos vértices están conectados por exactamente un camino. Un árbol recibe el nombre de árbol libre.
Ejemplo:
Un bosque es un grafo en el que dos vértices cualquiera están conectados por como máximo un camino. Una
definición equivalente es que un bosque es una unión disjunta de árboles.. Ejemplo:
Árbol enraizado
Un árbol enraizado es un árbol libre con un vértice (o nodo) distinguido denominado raíz.






Si existe un camino de un nodo x a un nodo y en un árbol T, se dice que x es antecesor de y, y que y es
sucesor de x.
Si (x; y) es el ultimo arco en el camino desde la raíz r del árbol T hasta el nodo y, entonces x es el padre de
y, e y es el hijo de x. La raíz es el único nodo en T que no tiene padre. Si dos nodos tienen el mismo padre
son hermanos.
Un nodo sin hijos lo denominaremos hoja. El resto son nodos internos.
El grado de un nodo es el número de hijos que tiene.
Se llama profundidad de un nodo a la longitud del camino desde la raíz a ese nodo.
La altura de un árbol es la profundidad del nodo más profundo.
2
ÁRBOLES BINARIOS.
Un árbol binario es un árbol en el que el máximo número de hijos de cada nodo es 2 (hijo izquierdo e hijo
derecho).


Un árbol binario se dice que es completo (o lleno) si todas las hojas tienen la misma profundidad y todos los
nodos internos tienen grado 2.
Un árbol binario es casi-completo si el árbol es completo, a excepción quizás en el nivel de las hojas, en el
cual todas las hojas están tan a la izquierda como sea posible.
RECORRIDOS DE ÁRBOLES BINARIOS.
PREORDEN: La clave de la raíz se imprime antes de los valores de sus subárboles.
INORDEN: La clave de la raíz se imprime entre los valores de su subárbol izquierdo y derecho.
POSTORDEN: La clave de la raíz se imprime después de los valores de sus subárboles.
3
GRAFOS DE EULER.
Un ciclo Euleriano es aquel camino que recorre todos los vértices (nodos) de un grafo pasando una y sólo una
vez por cada arco (arista) del grafo, siendo condición necesaria que regrese al vértice inicial de salida (ciclo =
camino en un grafo donde coinciden vértice inicial o de salida y vértice final o meta). Una definición más formal
lo define como: "aquel ciclo que contiene todas las aristas de un grafo solamente una vez".
Si un grafo admite un ciclo Euleriano, se denomina grafo Euleriano. Ejemplo:
En la imagen, C = {1,2,3,4,6,3,5,4,1}, es un ciclo euleriano, luego es un grafo
euleriano.
GRAFOS DE HAMILTON.
Un camino hamiltoniano es un camino que visita cada vértice exactamente una vez. Un grafo que contiene un
camino hamiltoniano se denomina un ciclo hamiltoniano ó circuito hamiltoniano si es un ciclo que visita cada
vértice exactamente una vez (exepto el vértice del que parte y al cual llega). Un grafo que contiene un ciclo
hamiltoniano es llamado grafo hamiltoniano.
Ejercicios:
1. Encontrar los caminos mas corto entre P y Q: