Algunos teoremas básicos sobre árboles

Árbol: – Un gráfico conexo sin ningún circuito se llama árbol. En otras palabras, un árbol es un grafo no dirigido G que satisface cualquiera de las siguientes condiciones equivalentes:

Dos vértices cualesquiera de G pueden estar conectados por un único camino simple.
G es acíclico y se forma un ciclo simple si se agrega cualquier borde a G.
G es conexo y no tiene ciclos.
G está conectado pero se desconectaría si se quitara un solo borde de G.
G es conexo y el grafo completo de 3 vértices K3 no es menor de G.

Por ejemplo :

Este gráfico es un árbol:

Este gráfico no es un árbol:

Algunos teoremas relacionados con los árboles son:

Teorema 1 : Demostrar que para un árbol (T), existe un único camino entre cada par de vértices de un árbol.
Prueba: Dado que el árbol (T) es un grafo conexo, existe al menos un camino entre cada par de vértices en un árbol (T). Ahora, supongamos que entre dos vértices ayb del árbol (T) existen dos caminos. La unión de estos dos caminos contendrá un circuito y el árbol (T) no puede ser un árbol. Por lo tanto, se prueba la afirmación anterior.

Figura 3: Árbol (T)

Teorema 2: Si en un grafo G hay un único camino entre cada par de vértices entonces el grafo G es un árbol.
Prueba: Existe la existencia de un camino entre cada par de vértices por lo que suponemos que el grafo G es conexo. Un circuito en un gráfico implica que hay al menos un par de vértices a y b, de modo que hay dos caminos distintos entre a y b. Ya que G tiene un único camino entre cada par de vértices. G no puede tener ningún circuito. Por lo tanto, el gráfico G es un árbol.

Figura 4: Gráfica dada G

Teorema 3: Demuestra que un árbol con n vértices tiene (n-1) aristas.
Demostración: Sea n el número de vértices de un árbol (T).
Si n=1, entonces el número de aristas=0.
Si n=2 entonces el número de aristas=1.
Si n=3 entonces el número de aristas=2.

Por lo tanto, el enunciado (o resultado) es verdadero para n=1, 2, 3.

Sea verdadera la afirmación para n=m. Ahora queremos demostrar que es cierto para n=m+1.

Sea $e$ el borde que conecta los vértices, digamos Vi y Vj. Como G es un árbol, entonces existe un solo camino entre los vértices Vi y Vj. Por lo tanto, si eliminamos el borde e, se desconectará el gráfico en dos componentes G1 y G2, digamos. Estos componentes tienen menos de m+1 vértices y no hay circuito y, por lo tanto, cada componente G1 y G2 tiene m1 y m2 vértices.

Now, the total no. of edges = (m1-1) + (m2-1) +1
                            = (m1+m2)-1
                            = m+1-1
                            = m.

Por tanto, para n=m+1 vértices hay m aristas en un árbol (T). Por inducción matemática, el gráfico tiene exactamente n-1 aristas.

Figura 5: Dado un árbol T

Teorema 4: Demostrar que cualquier grafo conexo G con n vértices y (n-1) aristas es un árbol.
Prueba: Sabemos que el número mínimo de aristas requeridas para hacer un gráfico de n vértices conectados es (n-1) aristas. Podemos observar que la eliminación de un borde del gráfico G lo hará desconectado. Por tanto, un grafo conexo de n vértices y (n-1) aristas no puede tener un circuito. Por tanto, un grafo G es un árbol.

Figura 6: Gráfico G

Teorema 5: Demuestra que un grafo con n vértices, (n-1) aristas y sin circuito es un grafo conexo.
Prueba: Deje que el gráfico G esté desconectado, entonces existen al menos dos componentes G1 y G2, digamos. Cada uno de los componentes no tiene circuitos, ya que G no tiene circuitos. Ahora, para hacer un grafo G conectado, necesitamos agregar una arista e entre los vértices Vi y Vj, donde Vi es el vértice de G1 y Vj es el vértice de la componente G2.
Ahora el número de aristas en G = (n – 1)+1 =n.

Figura 7: Gráfico desconectado

Ahora, G es un grafo conectado y sin circuitos con n vértices y n aristas, lo cual es imposible porque el grafo conectado sin circuitos es un árbol y el árbol con n vértices tiene (n-1) aristas. Entonces el grafo G con n vértices, (n-1) aristas y sin circuito es conexo. Por lo tanto, el enunciado dado queda probado.

Figura 8:Gráfico conectado G

Teorema 6: Un grafo G es un árbol si y sólo si es mínimamente conexo.
Prueba: Sea el grafo G mínimamente conexo, es decir; la eliminación de un borde hace que se desconecte. Por lo tanto, no hay circuito. Por lo tanto, el gráfico G es un árbol.
Por el contrario, dejemos que el gráfico G sea un árbol, es decir; existe un único camino entre cada par de vértices y sabemos que la eliminación de un borde del camino hace que el gráfico sea desconectado. Por lo tanto, el gráfico G es mínimamente conexo.

Figura 9: Gráfico mínimamente conectado

Teorema 7: Todo árbol con al menos dos vértices tiene al menos dos vértices colgantes.
Prueba: Sea n el número de vértices en un árbol dado T y n>=2. Por lo tanto, el número de aristas en un árbol T=n-1 usando los teoremas anteriores.

summation of (deg(Vi)) = 2*e
                       = 2*(n-1)
                       =2n-2

La suma de grados se dividirá entre n vértices. Como un árbol T es un grafo conexo, no puede tener un vértice de grado cero. Cada vértice contribuye al menos uno a la suma anterior. Por lo tanto, debe haber al menos dos vértices de grado 1. Por lo tanto, cada árbol con al menos dos vértices tiene al menos dos vértices colgantes.

Figura 10: Aquí a, b y d son vértices colgantes del gráfico dado

Teorema 8: Demuestra que todo árbol tiene uno o dos centros.
Demostración: Usaremos una observación de que la distancia máxima max d(v, w) desde un vértice dado v a cualquier otro vértice w ocurre solo cuando w es un vértice colgante.

Ahora, sea T un árbol con n vértices (n>=2)

T debe tener al menos dos vértices colgantes. Elimine todos los vértices colgantes de T, luego el gráfico resultante T ‘sigue siendo un árbol. Una vez más, elimine los vértices colgantes de T’ para que la T resultante siga siendo un árbol con los mismos centros.

Tenga en cuenta que todos los vértices que T tenía como centros seguirán siendo centros en T’–>T”–>T”’–>….

continúa este proceso hasta que el árbol restante tenga un vértice o un borde. Entonces, al final, si hay un vértice, esto implica que el árbol T tiene un centro. Si hay un borde, entonces el árbol T tiene dos centros.
Teorema 9: Demuestra que el número máximo de vértices en el nivel ‘L’ en un árbol binario es $2^L$ , donde L>=0.
Prueba: El teorema dado se demuestra con la ayuda de la inducción matemática. En el nivel 0 (L=0), solo hay un vértice en el nivel (L=1), solo hay $<strong>2^1 </strong>$ vértices.

Ahora asumimos que esa afirmación es verdadera para el nivel (L-1).

Por lo tanto, el número máximo de vértices en el nivel (L-1) es $<strong>2^L-1 </strong>$ . Como sabemos que cada vértice en un árbol binario tiene un máximo de 2 vértices en el siguiente nivel, el número de vértices en el nivel L es el doble que el del nivel L-1.

Por lo tanto, en el nivel L, el número de vértices es: