Arboles

En teoría de grafos, se usa la siguiente definición: «Un árbol binario es un grafo conexo, acíclico y no dirigido tal que el grado de cada vértice no es mayor a 3». De esta forma solo existe un camino entre un par de nodos.

Un árbol binario con enraizado es como un grafo que tiene uno de sus vértices, llamado raíz, de grado no mayor a 2. Con la raíz escogida, cada vértice tendrá un único padre, y nunca más de dos hijos. Si rehusamos el requerimiento de la conectividad, permitiendo múltiples componentes conectados en el grafo, llamaremos a esta última estructura un bosque'.

- Elementos de un árbol

*Raíz: Vértice del que sale uno o más áreas pero no entran.

*Brote: Vértice en el que termina uno o más arcos, pero del que no sale ninguno.

*Nodo raíz: Es cuando salen mas arcos de los que entran.

*Nodo eslabón: Nodo del que salen y entran de igual cantidad de áreas.

*Nodo eslabón simple: Es el que entra en un arco y sale en otro.

Arboles binarios.

Propiedades:

a) El grafo es conexo.

b) El grafo no tiene ciclos

c)Si V es el número de vértices; V-1 sera el número de aristas.

d) Si se agrega una arista entre 2 vértices no adyacentes se forman un ciclo.

e) Si suprimimos una arista cualquiera, el grafo deja de ser conexo.

f) Para cada par de vértices hay una sola cadena que los conecta.

Con frecuencia se usa un árbol con raíz para especificar relaciones jerárquicas. Cuando se usa un árbol de esta manera, si un vértice A esta en un nivel uno menos que el nivel del vértice By A y B son adyacentes, entonces A están "justo arriba" de B y existe una relación lógica entre Ay B: A domina a B ó B es subordinado de A en alguna forma.