Francisco Jesús Ramos AgudoLicenciado en Ciencias Matemáticas

Tema 2 : 666.441.488

Teorema fundamental de árboles

TEOREMA.- Sea G(V, E) un grafo. Son equivalentes:

a) G es un árbol

b) Cada par de vértices distintos de V esta conectado por un único camino.

c) G es conexo y toda arista de G es de separación

d) G no tiene ciclos y |V| = |E| + 1

e) G es conexo y |V| = |E| + 1

f) G no tiene ciclos pero al añadirle una arista a G se crea un único circuito

Dem.

a) ⇒ b) Por definición de árbol, G es conexo y entre cada par de vértices debe haber, al menos, un camino. Si hubiese dos caminos distintos uniendo dos vértices, su unión formaría un ciclo, pero los árboles no tienen ciclos.

b) ⇒ c) Es conexo porque cada par de vértices está conectado por un camino. Una arista es un camino entre dos vértices, por tanto es el único. Si quito esa arista, ya no hay caminos entre los vértices que unía y el grafo deja de ser conexo. Por tanto toda arista es de separación.

c) ⇒ d) G no puede tener ciclos porque las aristas de los ciclos no son de separación. Veamos que |V| = |E| + 1 por inducción en |V|.

Para |V| = 1 hay un único vértice v ⇒ |A| = 0 y |V| = |A| + 1.

Supongamos que el teorema es cierto para grafos con menos de n aristas y vamos a verlo si n = |A|.

Quito una arista e, que será de separación, y el grafo se parte en dos componentes conexas G1 = (V1, E1) con |V1| < n y G2 = (V2, E2) con |V2| < n.

Por la hipótesis de inducción |V1| = |E1| + 1, |V2| = |E2| + 1, luego |V| = |V1| + |V2| = (|E1| + |E2| + 1) + 1 = |E| + 1.

d) ⇒ e) Veamos que G es conexo. Si no lo fuera, lo parto en componentes conexas, G1,..., Gm. Cada una de ellas es conexa y sin ciclos, por lo que |V1| = |E1| + 1, ..., |Vm| = |Em| + 1. Pero entonces |V| = |V1| +...+ |Vm| = |E1| + 1 +.....+ |Em| + 1 = |E| + m en vez de ser |E|+1.

e) ⇒ f) Suponemos que existe un ciclo (con k aristas y k vértices) y vamos a llegar a una contradicción. Pueden suceder 2 casos:

1) k = n, |E| ≥ k = n, n = |V|, pero por la hipótesis |V| = |E| + 1 luego |V| > |E|.

2) los n – k vértices restantes necesitan al menos otras n – k aristas que les unan con los demás para que G sea conexo, pero entonces |E| ≥ k + (n – k) = n = |V|, pero por hipótesis |V| = |E| + 1.

f) ⇒ a) Si G no fuese conexo, habría dos vértices entre los que no habría ningún camino. Entonces al añadir una arista entre ellos no formaríamos ningún ciclo.

TEOREMA de CAYLEY: Existen nn – 2 árboles etiquetados diferentes de n vértices.

Francisco Jesús Ramos AgudoLicenciado en Ciencias Matemáticas

Tema 2 : 666.441.488

Dem.- Existen varios métodos de demostración para este teorema. Uno de ellos debido a Prufer y Clarke, y

es: se establece una correspondencia biunívoca entre el conjunto de árboles etiquetados de orden n y el

conjunto de todos los símbolos ordenados (a1, a2,..., an-2) donde ai está definido como entero entre 1 y n.

Dado que existen n·n·n···n (n – 2 veces) de tales símbolos, la demostración se tiene casi inmediata.

APLICACIONES DE LA TEORÍA DE GRAFOS.

Son varias las aplicaciones y usos que las distintas ciencias o áreas hacen de la teoría de grafos.

La aplicación más importante dentro de la matemática moderna se encuentra en el campo de la

combinatoria.

Veamos algunos de los ejemplos más importantes:

• El Teorema Matrimonial de Hall.- Sea un conjunto finito de muchachos, cada uno de los cuales

conoce a varias chicas. ¿En qué condiciones se pueden formar los matrimonios de tal forma que

cada uno de los muchachos se case con la chica que conoce?

TEOREMA de Hall: Una condición necesaria y suficiente para la solución del problema matrimonial

es que cada conjunto de k jóvenes conozca colectivamente k chicas al menos (1 ≤ k ≤ m).

• El teorema de Menger.- Determinación del número de trayectorias que unen dos vértices dados u,

v de un grafo G.

TEOREMA de Menger.: El número máximo de trayectorias de vértices disjuntos que conectan dos

vértices diferentes no adyacentes v y w de G es igual al número mínimo de vértices de un

subconjunto separador v w.

TEOREMA: El teorema de Menger implica el teorema de Hall.