En este video veremos las definiciones de "árbol", "árbol enraizado" y "árbol dirigido". Además, estudiaremos cómo se puede almacenar un árbol dirigido y una aplicación de los árboles de particular relevancia para los problemas de asignación y equilibrio, el árbol de rutas mínimas. En el contexto de la teoría de grafos, se define un "árbol" como un grafo conexo que no posee ciclos. Para comprender mejor lo que es un árbol, comencemos por un par de ejemplos de grafos que no serían un árbol, por ejemplo, ¿es este grafo un árbol? La respuesta es, claramente, no, ya que este grafo no es conexo. Ahora, ¿es este grafo un árbol? A pesar de que este grafo es conexo, tampoco es un árbol, porque presenta un ciclo. Este grafo no presenta ciclos y es un grafo conexo, por lo tanto, podemos decir que este grafo es un árbol. Cabe notar que el sentido de los arcos es irrelevante para determinar si un grafo es o no un árbol. Estudiemos algunas de las propiedades de los árboles. En primer lugar, podemos preguntarnos: ¿cuántos arcos conforman un árbol de "n" nodos? Para responder a esta pregunta, podemos construir un árbol desde cero. Partimos por un arco cualquiera que conecta dos nodos, estos dos nodos forman un árbol si lo miramos como un sistema aparte. Llevemos registro de los arcos y los nodos de este árbol parcial. Ahora, pensemos qué opciones tenemos para agregar un nuevo arco al árbol que ya estamos construyendo. Es fácil ver que el próximo arco a agregar tiene que conectar alguno de los nodos de dentro del árbol parcial con alguno de los nodos de afuera, sino, obtendríamos un grafo no conexo o formaríamos un ciclo. Agreguemos un nuevo arco a nuestro árbol parcial. El nuevo árbol parcial posee tres nodos y dos arcos. ¿Qué pasa con el número de nodos y arcos del árbol parcial cuando agregamos un nuevo arco? Por cada arco que agregamos, agregamos también un nodo al árbol parcial, esto quiere decir que siempre vamos a tener un nodo más que el número de arcos de nuestro árbol. Podemos verificar este hecho en el árbol del ejemplo que está formado por seis nodos y cinco arcos. Ahora, ¿cuántas rutas podemos encontrar para cada par de nodos? Es fácil verificar, sobre este ejemplo, que la respuesta es: una sola ruta. De hecho, ¿qué sucedería si algún par de nodos estuviera conectado por más de una ruta? Supongamos que para los nodos "uno" y "seis", además de la ruta que los conecta, existiera una segunda ruta. La unión de estas dos rutas formaría un ciclo y el grafo no podría ser un árbol. De hecho, una definición alternativa de árbol es un grafo en el que cualquier par de nodos está conectado por exactamente una ruta. Esto sucede porque si algún par de nodos poseyera cero rutas, el grafo sería no conexo, mientras que si algún par de nodos tuviera dos o más rutas, se formaría un ciclo. Definamos ahora un tipo especial de árbol, el "árbol enraizado". Un árbol enraizado es, simplemente, un árbol cualquiera para el cual se ha seleccionado un nodo arbitrario como raíz. Por convención, llamaremos a este nodo raíz: "s". En nuestro ejemplo, podemos decir que el árbol está enraizado en el nodo "uno", si escogemos como raíz al nodo "uno". Diremos, además, que un árbol dirigido hacia afuera es un árbol enraizado donde la ruta, desde la raíz hacia cualquier otro nodo, es dirigida. En este ejemplo, si escogemos el nodo "uno" como raíz, podemos notar que la ruta hacia cualquiera de los otros nodos es dirigida. Por ejemplo, para ir del nodo raíz, es decir, el nodo "uno" al nodo "seis", la ruta dada por los arcos "uno-tres" y "tres-seis" es dirigida. Observemos ahora, con detención, las cabezas de los arcos en este árbol. ¿Qué podemos observar? Podemos notar que cada nodo, excepto el nodo raíz, es cabeza de un único arco. Esto es una propiedad que resultará útil para almacenar este tipo de árbol. Para esto, tenemos que definir como el predecesor del nodo "i" a aquel nodo que precede a "i" en el árbol dirigido. Es decir, "pi" es un nodo tal que "pi, i" es un arco del conjunto de arcos del grafo. El nodo raíz "s" no posee predecesor, por convención, diremos que el predecesor de "s" es "s". De esta forma, un árbol enraizado puede ser reconstruido a partir de la información de sus predecesores. Veamos cómo, a partir de un vector de predecesores, podemos reconstruir un árbol dirigido. Notemos que el predecesor del nodo "uno" es el mismo nodo "uno", es decir, uno es el nodo raíz. Luego, dado que el predecesor del nodo "dos" es el nodo "cuatro", podemos agregar el arco "cuatro-dos". Continuamos este proceso, revisando cada predecesor para agregar el arco asociado a cada nodo, hasta completar el árbol. Una aplicación de los árboles dirigidos es registrar las rutas mínimas desde un nodo dado "s" hacia el resto de los nodos de un grafo. Supongamos, por ejemplo, que queremos identificar las rutas mínimas desde el nodo "s" al resto de los nodos, en este grafo. Estas rutas mínimas, que se pueden obtener aplicando diversos algoritmos, como veremos más adelante, para este caso, corresponderán al siguiente árbol. Este es un árbol dirigido hacia afuera desde el nodo raíz "s", por lo tanto, para cualquier otro nodo que miremos, este árbol registra una única ruta dirigida desde "s". Esta ruta corresponderá a la ruta óptima desde "s". En síntesis, hoy aprendimos que un "árbol" se puede definir como un grafo conexo que no posee ciclos. Esta definición es equivalente a decir que cada par de nodos se encuentra conectado por una única caminata. Un árbol es dirigido hacia afuera si existe un nodo, que denominamos "raíz", desde el cual existe una ruta dirigida hacia todos los demás nodos del árbol. También, vimos hoy que un árbol dirigido puede ser almacenado, registrando, para cada nodo, cuál es el nodo que lo precede. Finalmente, vimos hoy que los árboles dirigidos pueden ser utilizados para representar el conjunto de rutas mínimas que salen desde un nodo hacia los nodos restantes de un grafo, lo que resultará muy útil cuando estudiemos diferentes algoritmos de asignación de viaje, más adelante. Esto es todo por ahora, hasta la próxima.
