Grafos y Arboles

Un árbol es un grafo simple no dirigido G que satisface:

1. G es conexo y no tiene ciclos .
2. G no tiene ciclos y, si se añade alguna arista se forma un ciclo.
3. G es conexo y si se le quita alguna arista deja de ser conexo.
4. G es conexo y el grafo completo de 3 vértices ${\displaystyle K_{3}}$ no es un menor de G.
5. Dos vértices cualquiera de G están conectados por un único camino simple.

Las condiciones anteriores son todas equivalentes, es decir, si se cumple una de ellas otras también se cumplen. Para árboles finitos además se cumple que: Si un árbol G tiene un número finito de vértices, n, entonces tiene n − 1 aristas.
Algunas definiciones relacionadas con los árboles son:

• Un grafo unidireccional simple G es un bosque si no tiene ciclos simples.
• Un árbol dirigido es un grafo dirigido que sería un árbol si no se consideraran las direcciones de las aristas. Algunos autores restringen la frase al caso en el que todos las aristas se dirigen a un vértice particular, o todas sus direcciones parten de un vértice particular.
• Un árbol recibe el nombre de árbol con raíz si un vértice ha sido designado raíz. En este caso las aristas tienen una orientación natural hacia o desde la raíz. Los árboles con raíz, a menudo con estructuras adicionales como orden de los vecinos de cada vértice, son una estructura clave en informática; véase árbol (programación).
• Un árbol etiquetado es un árbol en el que cada vértice tiene una única etiqueta. Los vértices de un árbol etiquetado de n vértices reciben normalmente las etiquetas {1,2, ..., n}.
• Un árbol regular u homogéneo es un árbol en el que cada vértice tiene el mismo grado.
• Todo árbol posee una altura. Recorriendo el mismo en forma de grafo dirigido y considerando que las aristas parten desde los vértices hacia algún otro vértice o hacia alguna hoja, de forma tal que todo camino inicia en la raíz y termina en una hoja, puede afirmarse que el árbol posee una altura h. Dicha altura será igual a la longitud del camino con más aristas.
•