3 ÁRBOLES UN GRAFO QUE NO TIENE CICLOS Y

ÁRBOLES

Á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:

3 ÁRBOLES UN GRAFO QUE NO TIENE CICLOS Y

Árbol enraizado

Un árbol enraizado es un árbol libre con un vértice (o nodo) distinguido denominado raíz.

3 ÁRBOLES UN GRAFO QUE NO TIENE CICLOS Y

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.

3 ÁRBOLES UN GRAFO QUE NO TIENE CICLOS Y

Á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).

3 ÁRBOLES UN GRAFO QUE NO TIENE CICLOS Y

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.

3 ÁRBOLES UN GRAFO QUE NO TIENE CICLOS Y

INORDEN: La clave de la raíz se imprime entre los valores de su subárbol izquierdo y derecho.

3 ÁRBOLES UN GRAFO QUE NO TIENE CICLOS Y

POSTORDEN: La clave de la raíz se imprime después de los valores de sus subárboles.

3 ÁRBOLES UN GRAFO QUE NO TIENE CICLOS Y

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:

3 ÁRBOLES UN GRAFO QUE NO TIENE CICLOS Y

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.

3 ÁRBOLES UN GRAFO QUE NO TIENE CICLOS Y

Ejercicios:

Encontrar los caminos mas corto entre P y Q:

3 ÁRBOLES UN GRAFO QUE NO TIENE CICLOS Y

Tags: ciclos y, grafo, tiene, ciclos, árboles