Decimos que una gráfica $T(V,E)$ sin lazos es un árbol cuando se presenta alguna de la siguientes situaciones:

• $T$ es conexo y no contiene ciclos.
• $T$ es conexo, pero al eliminar cualquier arista quedará desconectado en dos subgráficas.
• $T$ no contiene ciclos y el número de vértices excede en uno al número de aristas, es decir, $|V|=|E|+1$.
• $T$ es conexo y además $|V|=|E|+1$.
• $T$ no contiene ciclos pero si se añade una nueva arista entonces $T$ contendrá un ciclo y solo uno.

Hemos cambiado la $G$ usual de gráfica por una $T$ (del inglés tree, árbol).

Independientemente de si son o no dirigidas, podemos ver que las condiciones anteriores se cumplen para la gráfica derecha de la escena del Inicio pero no así para la izquierda.

Notemos que si tenemos un conjunto $V$ de puntos y queremos formar una gráfica conexa, vamos a necesitar al menos $|V|-1$ aristas. No tenemos forma de conectar $n$ nodos si no empleamos al menos $n-1$ aristas.

Similarmente, si tenemos una gráfica conexa sin lazos, de la cual queremos eliminar el mayor número de aristas posible, pero manteniéndola conectada, necesariamente obtendremos un árbol.

Los dos párrafos anteriores nos dicen algo muy importante:

Podríamos considerar a los árboles como el esqueleto de las gráficas conexas, lo que las mantiene unidas con el menor número de aristas.

A continuación ilustramos un algoritmo de búsqueda binario que encontrará una posición desconocida en una lista ordenada de 1,023 elementos en a lo más $\hbox{log}_2(1024)=10$ iteraciones. Te pedimos que pienses un número al azar en el rango de valores mencionado y observes cómo el algoritmo lo va aproximando. Sólo tendrás que responder si la propuesta es mayor, menor o igual. El algoritmo concluye cuando indiques que es igual.

El árbol que utilizamos en este algoritmo de búsqueda es un árbol con 1,023 nodos y, por tanto, con 1,022 aristas, además 512 nodos son de grado 1 (conocidos como hojas o vértices colgantes).

Sin embargo, dos características importantes de este árbol son que está dirigido y que siempre lo recorremos comenzando por el mismo nodo. Iniciamos la búsqueda con 512 como propuesta, y avanzamos hasta llegar a los vértices colgantes, si es que ocupamos las 10 iteraciones de la búsqueda, o nos detenemos en un número par, cuando terminamos la búsqueda antes de completar las 10 iteraciones. Los vértices colgantes corresponden a todos los números impares desde el 1 hasta el 1,023.

La gráfica de la escena muestra el camino entre el vértice correspondiente a la primera propuesta y el del número buscado. Si buscásemos todos los números impares del 1 al 1,023 y no borrásemos estos caminos, entonces tendríamos la gráfica completa del árbol de búsqueda.