Árboles y bosques#
Introducción#
Imagina que sabemos que tenemos una gráfica en \(10\) vértices, los cuales puedes pensar como las ciudades de un cierto país. Piensa que una aerolínea quiere establecer algunos vuelos redondos entre parejas de ciudades (es decir, si hay un vuelo de \(A\) a \(B\), entonces también hay vuelo de \(B\) a \(A\)). A la aerolínea le gustaría que se pudiera ir de cualquiera de las diez ciudades a cualquier otra (en términos de lo que hemos visto antes, que la gráfica sea conexa). Pero para simplificar sus operaciones, a la aerolínea le interesa establecer la menor cantidad de vuelos redondos (es decir, minimizar la cantidad de aristas usadas) ¿Cuál es el mínimo número de vuelos que la aerolínea debe establecer?
Una posible forma de conectar a todas las ciudades es la siguiente:
Sin embargo, observa que este acomodo no es óptimo. Si bien la gráfica es conexa, la aerolína todavía podría quitar el vuelo redondo de Calayea a Montalio y la gráfica seguiría siendo conexa:
La aeorolínea aún podría quitar un vuelo más, por ejemplo el de Salsaro a Orizanta y la gráfica seguiría siendo conexa:
Pero en este punto la aerolínea no puede quitar ningún otro vuelo, pues como puedes verificar, esto desconectaría la gráfica. ¿Será entonces que la mínima cantidad de vuelos redondos (aristas) que la aerolínea debe establecer es \(9\)? ¿O será que hay alguna forma de tener \(8\) vuelos?
En esta sección daremos algunas definiciones clave y desarrollaremos teoría para entender este problema con más detalle.
Definiciones#
Nuestras dos definiciones clave son las siguientes.
Definición. Un bosque es una gráfica sin ciclos.
Definición. Un árbol es un bosque conexo. En otras palabras, es una gráfica conexa sin ciclos.
Ejemplo. La siguiente gráfica es un bosque, pues no tiene ciclos:
Sin embargo, no es un árbol, pues no es conexa. La siguiente gráfica sí es un árbol:
\(\square\)
Observación. Las compontentes conexas de un bosque son árboles.
Propiedades básicas#
A continuación estableceremos algunas propiedades importantes de los árboles.
Definición. Una hoja de una gráfica es un vértice de grado 1.
Proposición. Todo árbol \(G\) con al menos dos vértices tiene por lo menos dos hojas.
Demostración. Comencemos con un vértice arbitrario \(u\) del árbol y hagamos una trayectoria tan larga como se pueda que comience en \(u\). Es imposible que esta trayectoria sólo tenga a \(u\), pues esto querría decir que de \(u\) no salen aristas, por lo que sería un vértice aislado y entonces estaría en una componente conexa distinta de algún otro vértice distinto de \(u\) (recordemos que \(G\) tiene al menos dos vértices). Así, la trayectoria termina en un vértice \(v\) distinto de \(u\).
La razón por la cual la trayectoria terminó es por que no podía alargarse más allá de \(v\). Esto pudo haber sucedido por una de dos razones:
O bien \(v\) es de grado mayor o igual a \(2\), y no pudo salir una arista pues cualquier arista lleva a un vértice por el que ya pasó la trayectoria.
O bien \(v\) es de grado \(1\).
Lo primero no puede pasar, pues en ese caso se formaría un ciclo (En la siguiente figura, la trayectoria máxima es la que está indicada con negro. En rojo se muestran las aristas que no pueden estar pues se formaría un ciclo.). Así, \(v\) es de grado \(1\) y por lo tanto es una hoja.
Para encontrar una segunda hoja, repetimos el argumento pero ahora con una trayectoria de longitud máxima que comience en \(v\). El vértice \(w\) en el que termina es una hoja por un argumento análogo al anterior. \(\square\)
La hipótesis de que la gráfica sea un árbol es importante. ¿Puedes encontrar una gráfica sin hojas?
Las hojas de un árbol nos permiten hacer demostraciones inductivas como la siguiente.
Proposición. Un árbol \(G\) con \(n\) vértices tiene exactamente \(n-1\) aristas.
Demostración. Procedemos por inducción en el número de vértices de \(G\). Si hay \(1\) vértice, tenemos \(0\) aristas, como queremos.
Supongamos el resultado válido para árboles con \(n-1\) vértices y tomemos un árbol \(G\) con \(n\) vértices. Tomemos una hoja \(u\) de \(G\). Al quitar a \(u\) y su única arista incidente, obtenemos un árbol \(G^\ast\) con \(n-1\) vértices. Por hipótesis inductiva, \(G^\ast\) tiene \(n-2\) aristas. Al regresar a \(u\) y su arista, tenemos entonces que \(G\) tiene \(n-1\) aristas, como queríamos. \(\square\)
Como consecuencia inmediata, tenemos el siguiente resultado.
Corolario. Si \(G\) es un bosque con \(n\) vértices y \(k\) componentes conexas, entonces \(G\) tiene \(n-k\) aristas.
Demostración. Supongamos que las componentes conexas de \(G\) son \(C_1,\ldots,C_k\) y que tienen, respectivamente, \(a_1,\ldots,a_k\) vértices. Entonces
Los árboles son óptimos para conexidad y aciclicidad#
Con las propiedades anteriores podemos demostrar el siguiente teorema, que nos acerca todavía más a mostrar que los árboles son las gráficas conexas con la mínima cantidad de aristas posibles.
Teorema. Sea \(G\) una gráfica con \(n\) vértices, entonces, cualesquiera dos de las siguientes afirmaciones implican la tercera:
\(G\) es conexa.
\(G\) es acíclica.
\(G\) tiene \(n-1\) aristas.
Demostración. Hagamos cada demostración por separado. Si \(G\) es conexa y acíclica, entonces es un árbol. Por la proposición de la sección anterior, \(G\) tiene \(n-1\) aristas.
Supongamos ahora que \(G\) es acíclica y tiene \(n-1\) aristas. Por el corolario de la sección anterior, \(G\) tiene \(n-k\) aristas, en donde \(k\) es el número de componentes conexas de \(G\). Como \(n-k=n-1\), entonces \(k=1\), es decir, \(G\) es conexa.
Finalmente, supongamos que \(G\) es conexa y tiene \(n-1\) aristas. Si \(G\) tuviera un ciclo, entonces al quitar una arista de ese ciclo, \(G\) seguiría siendo conexa (ver ejercicios). Podemos seguir quitando aristas de ciclos de esta manera hasta llegar a una gráfica conexa y acíclica \(G^\ast\), es decir, un árbol. Digamos que para llegar a eso se quitaron \(k\) aristas. Entonces \(G^\ast\) tiene \(n\) vértices y \(n-1-k\) aristas. Pero por la proposición de la sección anterior, \(G^\ast\) tiene \(n-1\) aristas. De aquí que \(n-1-k=n-1\) y por lo tanto que \(k=0\). En otras palabras, sin haber quitado ninguna arista \(G\) ya era acíclica. \(\square\)
Con el teorema anterior, obtenemos los siguientes dos corolarios.
Corolario. Si \(G\) es una gráfica conexa con \(n\) vértices, entonces tiene al menos \(n-1\) aristas.
Demostración. Si \(G\) no es acíclica, como en la demostración del teorema anterior podemos ir quitando aristas una por una sin desconectarla, hasta llegar a una gráfica acíclica. La gráfica a la que se llega es un árbol, que tiene \(n-1\) aristas. Así, \(G\), que tiene una cantidad mayor o igual de aristas, tiene entonces por lo menos \(n-1\) aristas. \(\square\)
Corolario. Si \(G\) es una gráfica acíclica con \(n\) vértices, entonces tiene a lo más \(n-1\) aristas.
Demostración. La hipótesis es que \(G\) es bosque. Si \(G\) tiene \(k\) componentes conexas, por un resultado anterior tiene \(n-k\) aristas. Como \(k\geq 1\), entonces \(n-k\leq n-1\). \(\square\)
Árboles con raíz y árboles binarios#
Aprovechemos que estamos hablando de árboles para definir un tipo de árboles especiales que necesitaremos más adelante cuando hablemos de algoritmos de búsqueda.
Definición. Un árbol con raíz es un árbol en el que se elige a un vértice especial al que llamaremos raíz.
Definición. En un árbol con raíz, la profundidad de un vértice será su distancia a la raíz. Al conjunto de vértices a cierta profunidad \(k\) le llamaremos el nivel \(k\). A la máxima profundidad de un vértice le llamaremos la altura del árbol.
A los árboles con raíz los podemos dibujar de una manera especial, colocanco a la raíz en la parte superior del dibujo. Luego, en un siguiente nivel horizontal, colocamos a los vecinos de la raíz (los vértices de profundidad \(1\)). Luego, en un siguiente nivel horizontal, colocamos a los vecinos de los vecinos de la raíz que no hayamos puesto aún (los vértices de profundidad \(2\)), y así sucesivamente.
Ejemplo. El siguiente es un árbol con raíz:
La raíz que hemos elegido es el vértice \(F\). Esta forma de dibujarlo no es muy ilustrativa, y por lo tanto a continuación mostramos un mejor dibujo, por niveles.
Aquí es muy claro que tenemos los siguientes vértices en los niveles dados:
Nivel 0: \(F\).
Nivel 1: \(A\), \(C\), \(B\).
Nivel 2: \(D\), \(E\), \(J\)
Nivel 3: \(H\), \(I\).
Nivel 4: \(G\).
La altura del árbol es \(4\). Puedes también pensar a la altura como la longitud máxima de una trayectoria que comience en la raíz.
\(\square\)
Definición. Dado un vértice que no sea la raíz, llamaremos padre a su vecino que está en el nivel anterior. Dado cualquier vértice, llamaremos hijos a sus vecinos que están en el nivel siguiente.
Definición. Los ancestros de un vértice son sus padres, los padres de sus padres, y así sucesivamente. Los descendientes de un vértice son sus hijos, los hijos de sus hijos, y así sucesivamente.
Ejemplo. Consideremos nuevamente el árbol con raiz de arriba. Pasan las siguientes cosas:
Los ancestros de \(E\) son \(C\) y \(F\).
Los descendientes de \(C\) son \(E\), \(J\) e \(I\).
\(F\) no tiene padre pues es la raíz, pero es padre de \(A\), \(B\) y \(C\), que son sus hijos.
\(I\) no tiene hijos, pero es hijo de \(J\).
\(\square\)
De entre los árboles con raíz hay unos particularmente importantes, que se usan frecuentemente en ciencias de la computación. Estos árboles cumplen que de un nivel a otro sólo se pueden tener «pocos hijos».
Definición. Un árbol binario es un árbol en el que cada vértice tiene a lo más dos hijos.
El árbol con el que hemos trabajado de ejemplo es binario. Verifica que cualquier vértice tiene máximo dos hijos.
Tarea moral#
Los siguientes problemas te ayudarán a practicar lo visto en esta entrada. Para resolverlos, necesitarás usar herramientas matemáticas, computacionales o ambas.
Demuestra que si \(u\) y \(v\) son vértices de un árbol, entonces existe un único camino de \(u\) a \(v\).
Se sabe que un árbol \(G\) tiene un vértice de grado \(k\). Demuestra que \(G\) tiene al menos \(k\) hojas.
Prueba las siguientes dos afirmaciones:
Si \(G\) es una gráfica conexa y \(C\) es un ciclo de \(G\), entonces al quitar una arista de \(C\) a la gráfica \(G\), la gráfica que se obtiene sigue siendo conexa.
Si \(G\) es un bosque y \(u\) y \(v\) son vértices en componentes conexas distintas de \(G\), entonces la gráfica que se obtiene al agregar la arista \(uv\) sigue siendo un bosque.
Demuestra que si un árbol con raíz es binario y tiene altura \(h\), entonces tiene a lo más \(2^{h+1}-1\) vértices.
Dos jugadores juegan el siguiente juego. Comienzan con una gráfica que consiste de \(n\) vértices aislados. Alternadamente, cada jugador agrega una arista a la gráfica, siempre y cuando esto no haga un ciclo. Si uno de ellos crea un ciclo, entonces pierde. ¿Quién tiene una estrategia ganadora? Para responder esta pregunta, deberás explicar cómo algún jugador debe jugar para garantizar la victoria, es decir, los pasos que debe seguir para garantizar que sin importar qué haga el otro jugador, él gane.
Sean \(u\) y \(v\) vértices de un árbol con raíz. ¿Es cierto que siempre la distancia de \(u\) a \(v\) es la misma que la suma de la distancia de \(u\) a la raíz más la distancia de la raíz a \(v\)? En caso de que sí, demuéstralo. En caso de que no, da un contraejemplo e intenta modificar la afirmación para que sea cierta.