Arboles

ÁRBOLES
BREVE HISTORIA: Continuaremos nuestro estudio de la teoría de grafos y nos centraremos en un tipo especial de grafo llamado árbol, los arboles fueron utilizados por primera vez en 1847 en la obra de Gustav Kirchhoff (1824-1887) en su trabajo de redes eléctricas. El concepto también apareció en Geometría de Lage, de Karl von Staudt (1798-1867) aunque posteriormente fueron descubiertospor Arthur Cayley (1821-1895) quien No conocía tales desarrollos anteriores y fue el primero en llamar “Árbol” a esta estructura. Cayley los utilizo estos grafos en las aplicaciones relacionadas con los isómeros químicos como Hidrocarburos Saturados eso en 1857.
Definición: Sea G= (V, E) un grafo no dirigido sin lazos. El grafo G es un árbol si G es conexo y no contiene ciclos. En la figura 12.1,el grafo G1 es un árbol, pero G2 no lo es, pues contiene el ciclo (a, b), (b, c), (c, a). El grafo G3 no es conexo, por lo que no puede ser un árbol. Sin embargo, cada componente de G3 es un árbol; en este caso G3 es un Bosque.
Si un grafo es un árbol, escribimos T en vez de G, para enfatizar esta estructura. 
En la figura 12.1 veremos que G1 es un subgrafo de G2, que G1 contiene todos losvértices de G2 y que G1 es un árbol. En este caso G1 es un árbol recubridor de G2. Por lo tanto, un árbol recubridor de un grafo conexo es un subgrafo recubridor que también es un árbol.

TEOREMA 12.1: Si a, b son vértices distintos en un árbol T= (V, E), entonces hay un único camino que conecta estos vértices.
DEMOSTRACIÓN: Como T es conexo, existe al menos un camino en T que conecta a y b. Sihubiera más caminos de este tipo, por medio de dos de ellos, algunas aristas podrían formar un ciclo, pero T no tiene ciclos.
TEOREMA 12.2: De nuevo, si G3 no contiene ciclos, entonces tenemos un árbol recubridor de G. En caso contrario, continuamos este procedimiento un número finito de veces, hasta obtener un subgrafo recubridor de G, que sea conexo, sin lazos ni ciclos y que, por lo tanto, sea unárbol recubridor de G.
 La figura 12.2 muestra tres árboles no isomorfos para cinco vértices. Aunque no so isomorfos, tienen el mismo número de aristas (cuatro). Estos nos llevan al siguiente resultado general.

TEOREMA 12.3: Si, por ejemplo, eliminamos de T la arista con extremos y, z obtendremos dos subárboles, T1= (V1, E1) y T2=(V2,E2), tales que |V|=|V1|+|V2| y |E1|+|E2|+1=|E|. (Uno de estossubárboles podrían estar formado por un solo vértice si, por ejemplo, eliminamos la arista con extremos w, x.) Como 0|E1|k y 0<=|E2|<=k, de la hipótesis de inducción se sigue que |E1|+1=|V1|, para y=1,2. En consecuencia, |V|=|V1|+|V2= (|E1|+1)+ (|E2+1)=( |E1|+|E2|)+1)+1=|E|+1 y el teorema se sigue de la forma alternativa de la inducción matemática.
En cualquier árbol T= (V, E),|V|= |E|+1 .Demostración: La demostración se obtiene al aplicar la forma alternativa de la inducción matemática a |E|. Si |E|=0, entonces el árbol está formado por un solo vértice aislado, como en la figura 12.3(a). En este caso, |V|= 1= |E|+1. Las partes (b) y (c) de la figura verifican los resultados para estos casos en que |E|=1 o 2 .
Supongamos que el teorema es cierto para cualquier árbol que cuentecon un máximo de k aristas, donde k0. Ahora consideremos un árbol T=(V,E), como en la figura 12.4, tal que |E|=k+1 . [La(s) arista(s) punteada(s) indica(n) que una parte del árbol no aparece en la figura.]

TEOREMA 12.4

TEOREMA 12.5: Las siguientes proposiciones son equivalentes para un grafo no dirigido G=(V,E) sin lazos:
* G es un árbol.
* G es conexo, pero si se elimina cualquierade sus artistas, G quedara desconectado en dos subgrafos que son arboles.
* G no contiene ciclos y |V|=|E|+1.
* G es conexo y |V|=|E|+1.
* G no contiene ciclos y si a, b€V con {a, b}€E, entonces el grafo que se obtiene de añadir la arista {a, b} a G tiene precisamente un ciclo.
EJEMPLO 12.1: En la figura 12.5 tenemos dos árboles, cada uno con 14 vértices (con nombres C y H) y 13...