12.4: Árboles

Una clase especial de gráficas que surgen a menudo en la teoría de grafos, es la clase de árboles. Si un matemático sospecha que algo es cierto para todas las gráficas, una de las primeras familias de gráficas para las que probablemente intentará demostrarlo, es la familia de árboles porque su fuerte estructura los hace mucho más fáciles de trabajar que muchas otras familias de gráficas.

Definición: Árbol, Bosque y Hoja

• Un árbol es una gráfica conectada que no tiene ciclos.
• Un bosque es una unión disjunta de árboles. Entonces un bosque es una gráfica que no tiene ciclos (pero que no necesita estar conectada).
• Una hoja es un vértice de valencia\(1\) (en cualquier gráfica, no solo en un árbol o bosque).

Observe que la gráfica\(P_n\) es un árbol, para cada\(n ≥ 1\). Demostramos algunos resultados importantes sobre la estructura de los árboles.

Proposición\(\PageIndex{1}\)

Dejar\(T\) ser una gráfica conectada sin ciclos. Después, eliminar cualquier borde de\(T\) desconecta la gráfica.

Prueba

Si no\(T\) tiene aristas, la afirmación es vacuamente cierta. Por lo tanto, podemos suponer que\(T\) tiene al menos un borde. Dejar\(\{u, v\}\) ser un borde arbitrario de\(T\). (Ya que un bucle es un ciclo, debemos tener\(u \neq v\) aunque no estuviéramos asumiendo que nuestras gráficas son simples).

Hacia una contradicción, supongamos que borrar\(\{u, v\}\) de\(T\) no se desconecta\(T\). Entonces por la definición de una gráfica conectada, hay un\(u − v\) paseo adentro\(T \setminus \{u, v\}\). Por la Proposición 12.3.1, la\(u − v\) caminata más corta\(T \setminus \{u, v\}\) debe ser una\(u − v\) senda. Si tomamos este mismo paseo\(T\) y agregamos u al final, esto seguirá siendo un paseo\(T\) ya que\(T\) contiene el borde uv. Como el caminar en\(T \setminus \{u, v\}\) era un camino, no se repitieron vértices. Sumando\(u\) al final de esta caminata se realiza una caminata (ciertamente de longitud al menos\(2\)) en la que no se repite ningún vértice excepto que el primer y último vértices son los mismos: por definición, un ciclo. Así,\(T\) tiene un ciclo, contradiciendo nuestra hipótesis. Esta contradicción sirve para probar que eliminar cualquier borde de\(T\) desconecta la gráfica.

Dado que un árbol es una gráfica conectada sin ciclos, esto muestra que eliminar cualquier borde de un árbol desconectará la gráfica.

Proposición\(\PageIndex{2}\)

Cada árbol que tenga al menos un borde, tiene al menos dos hojas.

Prueba

Esto lo demostramos por una fuerte inducción en el número de vértices. Observe que debe ser una gráfica (simple) en un vértice\(K_1\), la cual no tiene aristas, por lo que la proposición no aplica. Por lo tanto nuestro caso base será cuando haya\(2\) vértices.

Caso base:\(n = 2\). De las dos gráficas (sin etiquetar) sobre\(2\) vértices, solo una está conectada:\(K_2\) (o\(P_1\); estas son isomórficas). Ambos vértices tienen valencia\(1\), por lo que hay dos hojas. Esto completa la prueba del caso base.

Paso de inducción: Comenzamos con la fuerte hipótesis inductiva. Que\(k ≥ 2\) sea arbitrario. Supongamos que para cada uno\(2 ≤ i ≤ k\), cada árbol con\(i\) vértices tiene al menos dos hojas. (Dado que\(i ≥ 2\) y un árbol es una gráfica conectada, cada árbol en\(i\) vértices tiene al menos un borde, por lo que podemos omitir esta parte de la hipótesis).

Dejar\(T\) ser un árbol con\(k + 1\) vértices. Ya que\(k + 1 > 1\),\(T\) tiene al menos un borde. Elija cualquier borde\(\{u, v\}\) de\(T\), y elimírelo. Por la Proposición 12.4.1, se desconecta la gráfica resultante. Por la Proposición 12.3.2, no puede tener más de dos componentes conectados, por lo que debe tener exactamente dos componentes conectados. Además, por la prueba de esa proposición, los componentes son\(T_u\) (el componente conectado que contiene el vértice\(u\)) y\(T_v\) (el componente conectado que contiene el vértice\(v\)).

Ya que no\(T\) tiene ciclos, ni hacer\(T_u\) ni\(T_v\). Dado que son componentes conectados, ciertamente están conectados. Por lo tanto, ambos\(T_u\) y\(T_v\) son árboles. Dado que no\(u\) es un vértice de\(T_v\) y no\(v\) es un vértice de\(T_u\), cada uno de estos árboles tiene como máximo\(k\) vértices.

Si ambos\(T_u\) y\(T_v\) tienen al menos dos vértices, entonces podemos aplicar nuestra hipótesis de inducción a ambos. Esto nos dice que\(T_u\) y\(T_v\) cada uno tiene al menos dos hojas. En particular,\(T_u\) debe tener alguna hoja\(x\) que no sea\(u\), y\(T_v\) debe tener alguna hoja\(y\) que no lo sea\(v\). Eliminando\(u_v\) de\(T\) no cambió la valencia de ninguno\(x\) o\(y\), así\(x\) y también\(y\) debe tener valencia\(1\) en\(T\). Por lo tanto,\(T\) tiene al menos dos hojas. Esto completa el paso de inducción y por lo tanto la prueba, en el caso donde\(T_u\) y\(T_v\) cada uno tenga al menos dos vértices. Aún debemos considerar la posibilidad de que al menos uno de\(T_u\) y\(T_v\) tenga un solo vértice.

Ya que\(k + 1 ≥ 3\), al menos uno de\(T_u\) y\(T_v\) debe tener dos vértices, por lo que sólo uno de ellos puede tener un solo vértice. Sin pérdida de generalidad (ya que nada en nuestro argumento hasta ahora hizo ninguna distinción entre\(u\) y\(v\), podemos cambiar\(u\) y\(v\) si es necesario), podemos suponer que\(T_v\) tiene solo un vértice, y\(T_u\) tiene al menos dos vértices. Aplicando nuestra hipótesis de inducción a\(T_u\), concluimos que\(T_u\) tiene alguna hoja\(x\) que no es\(u\), y que también es una hoja de\(T\). Además, dado que solo\(T_v\) tiene un vértice, esto significa que eliminar el borde\(uv\) izquierdo\(v\) como un vértice aislado, así\(u_v\) fue el único borde incidente con\(v\) in\(T\). Por lo tanto,\(v\) es una hoja de\(T\). Así,\(T\) tiene al menos dos hojas:\(x\) y\(v\). Esto completa el paso de inducción y por lo tanto la prueba, en el caso de que al menos uno de\(T_u\) y solo\(T_v\) tenga un vértice. Ya que hemos tratado con todas las posibilidades, esto completa nuestro paso de inducción.

Por el Principio de Inducción Matemática, cada árbol que tenga al menos un borde, tiene al menos dos hojas.

El siguiente resultado se te dejará a ti para que lo prueben.

Proposición\(\PageIndex{3}\)

Si se elimina una hoja de un árbol, la gráfica resultante es un árbol.

Teorema\(\PageIndex{1}\)

Los siguientes son equivalentes para una gráfica\(T\) con\(n\) vértices:

1. \(T\)es un árbol;
2. \(T\)está conectado y tiene\(n − 1\) bordes;
3. \(T\)no tiene ciclos, y tiene\(n − 1\) bordes;
4. \(T\)está conectado, pero al eliminar cualquier borde se deja un gráfico desconectado.

Prueba

Demostraremos que las declaraciones son equivalentes demostrando eso\(1 ⇒ 2 ⇒ 3 ⇒ 4 ⇒ 1\). Así, al utilizar una secuencia de implicaciones, vemos que cualquiera de los enunciados implica cualquier otro.

\((1 ⇒ 2)\)Suponemos que\(T\) es un árbol, y nos gustaría deducir que\(T\) está conectado y tiene\(n−1\) aristas. Por la definición de un árbol,\(T\) está conectado. Usaremos la inducción\(n\) para mostrar que\(T\) tiene\(n − 1\) bordes.

Caso base:\(n = 1\). Solo hay una gráfica (sin etiquetar) en un vértice, es\(K_1\), entonces\(T \cong K_1\), que no tiene bordes. Ya que\(0 = n − 1\), esto completa la prueba del caso base.

Paso inductivo: Comenzamos con la hipótesis inductiva. \(k ≥ 1\)Sea arbitrario, y supongamos que cada árbol en\(k\) vértices tiene\(k − 1\) aristas.

Dejar\(T\) ser un árbol arbitrario con\(k + 1\) vértices. Ya que\(k + 1 ≥ 2\) y\(T\) está conectado,\(T\) debe tener al menos un borde, así que por la Proposición 12.4.2,\(T\) tiene al menos dos hojas. Deja\(v\) ser una hoja de\(T\). Por la Proposición 12.4.3,\(T \setminus \{v\}\) es un árbol. También,\(T \setminus \{v\}\) tiene\(k\) vértices, por lo que podemos aplicar nuestra hipótesis de inducción para concluir que\(T \setminus \{v\}\) tiene\(k − 1\) aristas. Ya que\(v\) era una hoja,\(T\) tiene precisamente un borde más que\(T \setminus \{v\}\), por lo que\(T\) debe tener\(k = (k + 1) − 1\) bordes. Esto completa nuestro paso inductivo.

Por el Principio de Inducción Matemática, cada árbol en\(n\) vértices tiene\(n − 1\) aristas.

\((2 ⇒ 3)\)Suponemos que\(T\) está conectado y tiene\(n − 1\) bordes. Tenemos que deducir que no\(T\) tiene ciclos.

Hacia una contradicción, supongamos que\(T\) tiene un ciclo. Elimine repetidamente los bordes que estén en ciclos hasta que no queden ciclos. Por la Proposición 12.3.3 (utilizada repetidamente), la gráfica resultante está conectada, por lo que por definición es un árbol. Ya que ya lo hemos probado\(1 ⇒ 2\), este árbol debe tener\(n − 1\) bordes. Ya que empezamos con\(n − 1\) bordes y borramos al menos uno (basado en nuestra suposición de que\(T\) tiene al menos un ciclo), esto es una contradicción. Esta contradicción sirve para demostrar que no\(T\) debe tener ningún ciclo.

\((3 ⇒ 4)\)Suponemos que no\(T\) tiene ciclos, y tiene\(n − 1\) aristas. Debemos mostrar que\(T\) está conectado, y que eliminar cualquier borde deja una gráfica desconectada. Comenzamos mostrando que\(T\) está conectado; lo demostramos por inducción en\(n\).

Caso base:\(n = 1\). Entonces\(T \cong K_1\) se conecta.

Paso inductivo: Comenzamos con la hipótesis inductiva. \(k ≥ 1\)Sea arbitrario, y supongamos que cada gráfica en\(k\) vértices que tiene\(k − 1\) aristas y no ciclos, está conectada.

Let\(T\) Ser una gráfica arbitraria con\(k + 1\) vértices que tiene\(k\) aristas y sin ciclos. Por el lema de apretón de manos de Euler,

\[\sum_{v∈V} d(v) = 2k. \]

Si cada uno de\(k + 1\) los vértices tuviera valencia\(2\) o más, entonces tendríamos

\[\sum_{v∈V} d(v) ≥ 2(k + 1) \]

(esto se parece mucho al Principio Pigeonhole en concepto, pero el Principio Pigeonhole en sí no se aplica a esta situación). Ya que\(2k < 2(k + 1)\), debe haber algún vértice\(v\) que no tenga valencia\(2\) o más. Eliminar\(v\). Al hacerlo, eliminamos a lo sumo\(1\) borde, ya que\(v\) tiene como máximo borde\(1\) incidente. Así, la gráfica resultante tiene\(k\) vértices\(k\) y/o\(k − 1\) aristas, y puesto que no\(T\) tiene ciclos, tampoco lo hace\(T \setminus \{v\}\).

Si\(T \setminus \{v\}\) tiene\(k\) aristas, entonces la eliminación de cualquiera de los bordes da como resultado una gráfica en\(k\) vértices sin ciclos y\(k−1\) aristas, que por nuestra hipótesis inductiva debe estar conectada. Por lo tanto,\(T \setminus \{v\}\) es una gráfica conectada que permanece conectada después de que se elimine cualquier borde. Por la Proposición 12.4.1 (en el contrapositivo), esto significa que\(T \setminus \{v\}\) debe contener un ciclo, pero esto es una contradicción. Esta contradicción sirve para probar que\(T \setminus \{v\}\) no puede tener\(k\) aristas.

Así,\(T \setminus \{v\}\) tiene\(k − 1\) aristas y\(k\) vértices, y no tiene ciclos. Por nuestra hipótesis inductiva,\(T \setminus \{v\}\) debemos estar conectados. Además, el hecho de que\(T \setminus \{v\}\) tenga\(k − 1\) bordes significa que\(v\) es incidente a un borde, que debe tener su otro vértice final en\(T \setminus \{v\}\). Por lo tanto\(T\) está conectado. Esto completa el paso inductivo.

Por el Principio de Inducción Matemática, cada gráfica en\(n\) vértices sin ciclos y\(n − 1\) aristas está conectada.

Queda por demostrar que eliminar cualquier borde deja una gráfica desconectada, pero ahora que sabemos que\(T\) está conectada, esto se desprende de la Proposición 12.4.1.

\((4 ⇒ 1)\)Suponemos que\(T\) está conectado, pero eliminar cualquier borde deja un gráfico desconectado. Por la definición de árbol, debemos demostrar que no\(T\) tiene ciclos. Esto se desprende inmediatamente de la Proposición 12.3.3.

Ejercicio\(\PageIndex{1}\)

1. Demostrar Proposición 12.4.3.
2. Dibuja un árbol sobre\(6\) vértices.
3. Hay dos árboles no isomórficos en\(4\) vértices. Encuéntralos.
4. Hay gráficas\(11\) no isomórficas en\(4\) vértices. Dibuja todos\(11\), y debajo de cada uno indica: ¿está conectado? ¿Es un bosque? ¿Es un árbol?

[Insinuación: Uno tiene\(0\) bordes, uno tiene\(1\) borde, dos tienen\(2\) bordes, tres tienen\(3\) bordes, dos tienen\(4\) bordes, uno tiene\(5\) bordes y uno tiene\(6\) bordes.