16.3: Identificación de árboles

Teorema\(\PageIndex{1}\): Characterizations of trees.

Los siguientes son equivalentes para una gráfica\(G = (V,E)\) con\(\vert V \vert = n\) vértices.

1. Graph\(G\) es un árbol.
2. La gráfica\(G\) es acíclica pero la adición de cualquier borde nuevo crearía un ciclo.
3. Graph no\(G\) contiene bucles y contiene exactamente una ruta entre cada par de vértices distintos.
4. Graph\(G\) está conectado pero cada borde de\(G\) es un puente.
5. Graph\(G\) está conectado y tiene exactamente\(\vert E \vert = n-1\) bordes.
6. La gráfica\(G\) es acíclica y tiene exactamente\(\vert E \vert = n-1\) bordes.

Comprobante de la equivalencia de los estados 1 a 4.

Declaración 1 implica Declaración 2.

Supongamos que\(G\) es un árbol. Por definición, es acíclico. Además, supongamos que agregamos un borde entre vértices\(v,v'\text{.}\) Dado que los árboles están conectados, ya había un camino de\(v\) a\(v'\) en\(G\text{.}\) Atravesar el nuevo borde de\(v'\) atrás a\(v\) cierra ese camino a un ciclo.

Declaración 2 implica Declaración 3.

Considerando lo contrapositivo, asumiremos que la Declaración 3 es falsa, y probaremos que ello implica que la Declaración 2 también debe ser falsa.

Para que la Declaración 3 sea falsa, una de las siguientes debe ser cierta.

1. Los bucles existen en\(G\text{.}\)
2. Algún par de vértices distintos en no\(G\) está conectado.
3. Algún par de vértices distintos en\(G\) está conectado por más de una ruta.

En el primer caso, no\(G\) sería acíclico, ya que un bucle es la forma más básica de ciclo. En el segundo caso, agregar un borde entre estos dos vértices que previamente estaban desconectados por una ruta no crearía un ciclo, ya que el resto de ese ciclo distinto del nuevo borde habría sido un camino entre los dos vértices. Y en el tercer caso, si un par de vértices está conectado por más de un camino entonces las partes de dos de tales caminos que son diferentes podrían ser concatenadas (uno hacia adelante, otro invertido) para crear un ciclo, de manera que eso no\(G\) debe ser acíclico.

Así, en todos los casos que hagan falsa la Declaración 3, la Declaración 2 también es falsa.

Declaración 3 implica Declaración 4.

Nuevamente, consideraremos lo contrapositivo, asumiendo que el Estado 4 es falso y demostrando que el Estado 3 también es falso.

Para que la Declaración 4 sea falsa, una de las siguientes es cierta.

1. La gráfica no\(G\) está conectada.
2. Algún borde adentro no\(G\) es un puente.

En el primer caso,\(G\) debe contener al menos un par de vértices que no esté conectado por ningún camino. Para el segundo caso, supongamos que edge\(e\) in\(G\) es un bucle. Si\(e\) es un bucle, entonces\(G\) contiene bucles. Si no\(e\) es un bucle, entonces es un borde entre un par de vértices distintos, digamos\(v\) y\(v'\text{.}\) Pero luego quitando\(e\) de\(G\) dejaría un subgrafo\(G'\) que todavía contiene ambos\(v\) y\(v'\text{,}\) y que todavía está conectado. Entonces este subgrafo (y por lo tanto\(G\)) debe contener un camino entre\(v\) y\(v'\) que no\(e\text{.}\) implique Por otro lado, también\(v, e, v'\) es un camino entre\(v\) y\(v'\text{.}\) Así\(v,v'\) es un par de vértices distintos en\(G\) para los que hay más de un camino entre ellos.

Así, en todos los casos que hagan falsa la Declaración 4, la Declaración 3 también es falsa.

Declaración 4 implica Declaración 1.

Nuevamente, consideramos lo contrapositivo de esta implicación lógica, asumiendo que la Declaración 1 es falsa y demostrando que la Declaración 4 también es falsa. No obstante, dado que ambas declaraciones contienen la subdeclaración que\(G\) está conectada, no vamos a negar esa parte.

Entonces supongamos que\(G\) está conectado pero contiene un ciclo adecuado. Nuestro objetivo es demostrar que al menos un borde en no\(G\) es un puente. En la Actividad 16.7.4, se le pide que demuestre que ninguno de los bordes en el ciclo adecuado que\(G\) contiene es un puente, que completará la prueba.

Constancia de la equivalencia de los estados financieros 1, 5 y 6.

Declaración 1 implica Declaración 5.
Supongamos que\(G\) es un árbol. Entonces se conecta. Para demostrar que el número de aristas es\(\vert E \vert = n - 1\text{,}\) procedemos por inducción (fuerte) sobre\(n\text{,}\) el número de vértices en\(G\text{.}\)

Para el caso base de\(n = 1\text{,}\)\(\vert E \vert = 0\) es la única posibilidad, ya que no se permiten bucles en un árbol.

Ahora el paso de inducción. Supongamos que cada árbol con\(k \lt n\) vértices tiene\(k - 1\) aristas. Elija algún borde en\(G\text{.}\) By Statement 4, quitando ese borde crea dos componentes conectados,\(G_1\) y\(G_2\text{.}\) As\(G\) es acíclico, estos componentes conectados son ambos árboles (Sentencia 2 de la Proposición 16.2.1). Vamos a\(k_1, k_2\) representar el número de vértices en\(G_1,G_2\text{,}\) respectivamente, de manera que\(k_1 + k_2 = n\text{.}\) Dado que cada uno de\(k_1\) y\(k_2\) debe ser estrictamente menor de\(n\text{,}\) lo que podamos aplicar nuestra hipótesis de indución a cada uno de\(G_1\) y para\(G_2\text{,}\) que\(G_1\) tenga exactamente\(k_1 - 1\) bordes y\(G_2\) tiene exactamente\(k_2 - 1\) bordes.

Figura\(\PageIndex{1}\): El árbol\(G\) se divide en subárboles\(G_1,G_2\) después de la eliminación de un borde.

Sumando el número de aristas en\(G_1\) y\(G_2\text{,}\) junto con el borde único en el\(G\) que se eliminó para crear estos dos componentes conectados, obtenemos\(\vert E \vert = (k_1 - 1) + (k_2 - 1) + 1 = (k_1 + k_2) - 1 = n - 1, \) como se desee.

Declaración 5 implica Declaración 6.
Consideremos lo contrapositivo de esta implicación lógica, asumiendo que la Declaración 6 es falsa y demostrando que la Declaración 5 también es falsa. No obstante, ya que ambas declaraciones contienen el subenunciado que no\(\vert E \vert = n - 1\text{,}\) vamos a negar esa parte.

Entonces supongamos que\(G\) tiene\(n - 1\) bordes, pero contiene un ciclo adecuado. Debemos probar que\(G\) no se puede conectar en este caso. Elija una arista\(e\) en el ciclo adecuado y cree una subgráfica\(G'\) eliminando\(e\text{.}\) Subgraph\(G'\) ahora tiene\(n\) vértices pero\(n - 2\) aristas, y así por el contrapositivo del Teorema 15.3.1\(G'\) no se puede conectar. Eso quiere decir que\(G'\) contiene un par de vértices\(v_1,v_2\) entre los cuales no existe ninguna caminata. Si hay un paseo entre\(v_1,v_2\) adentro\(G\) pero no en\(G'\text{,}\) entonces ese paseo debe involucrar al elegido\(e\text{.}\) Pero entonces habría otro paseo entre\(v_1,v_2\) en\(G\) evitar\(e\) vía el resto del ciclo adecuado que contiene\(e\text{.}\) Y esta otra caminata sería en\(G'\) ya que no implica\(e\text{.}\) Excepto que asumimos que no había paseo entre\(v,v'\) adentro de\(G'\text{,}\) ahí tampoco puede haber caminata entre ellos en\(G\text{.}\) Así, no\(G\) está conectado.

Declaración 6 implica Declaración 1.
De nuevo, consideremos lo contrapositivo de esta implicación lógica, asumiendo que la Declaración 1 es falsa y demostrando que la Declaración 6 también es falsa. No obstante, dado que ambas declaraciones contienen la subdeclaración que\(G\) es acíclica (parte de la definición de árbol), no vamos a negar esa parte.

Entonces supongamos que\(G\) es acíclico pero no un árbol, es decir, que no\(G\) está conectado. Debemos probar que el número de aristas en\(G\) es diferente de\(n - 1\text{,}\) donde\(n\) está el número de vértices en\(G\text{.}\) Let\(G_1,G_2,\ldots,G_\ell\) be the connected components of\(G\text{.}\) Now, ya que\(G\) se asume acíclico, cada uno de estos componentes conectados es un árbol (Declaración 2 de Proposición 16.2.1). Ya hemos probado arriba que la Declaración 1 implica la Declaración 5, así que si escribimos\(k_i\) para el número de vértices en componente\(G_i\text{,}\) entonces podemos concluir que el número de aristas en componente\(G_i\) es\(k_i - 1\text{.}\) Como los componentes componen toda la gráfica\(G\text{,}\) podemos sumar la vértices y aristas en cada componente para obtener los totales en la gráfica completa:

\ begin {ecuación*} n = k_1 + k_2 +\ cdots + k_\ ell,\ end {ecuación*}
\ begin {align*}\ vert E\ vert & = (k_1 - 1) + (k_2 - 1) +\ cdots + (k_\ ell - 1)\\ & = (k_1 + k_2 +\ cdots + k_\ ell) -\ ell\\ & = n -\ ell\ texto {.} \ end {align*}
Ya que suponemos que no\(G\) está conectado, tenemos\(\ell \ge 2\text{,}\) y así\(\vert E \vert \neq n - 1\) como se desee.