Download Árboles por Prieto José.
Document related concepts
Transcript
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: