AAAPPPLLLIIICCCAAACCCIIIOOONNNEEESSS DDDEEE LLLAAA TTTEEEOOORRRAAA DDDEEE GGGRRRAAAFFFOOOSSS...

Los grafos de tipo de rbol son utilizados en mtodos de optimizacin en aplicaciones de un grupo de objetos unidos mediante alguna relacin. Tambin se

suele emplear en Estadstica para caracterizacin de espacios muestrales y clculo

de probabilidades

# Ejemplo: Supongamos que tres caballos {a,b,c} corren juntos en una carrera, y que

sus probabilidades de ganar son , 1/3 y 1/6 respectivamente. Si se efectan dos

carreras consecutivas, el espacio muestral de los resultados vendr caracterizado por:

a

a b c a b b 1/3 c 1/6 a c b c

Para hallar las respectivas probabilidades de los resultados de la competicin bastar

multiplicar los pesos de las correspondientes ramas. Por ejemplo la probabilidad de

que el resultado sea (c,a) ser:

P( (c,a) ) = (1/6).(1/3) = 1/18.

) Una aplicacin importante en la representacin plana de mapas aplicada a los poliedros, sin recurrir a la topologa algebraica es la Formula de Euler:

El nmero de caras - nmero de aristas + nmero de vrtices es igual a 2. Mediante la identificacin de las caras del poliedro con las regiones del mapa asociado

al conjunto de sus vrtices..

) Otra aplicacin importante que se resuelve mediante los grafos planos, es el problema de los cuatro colores , que apareci por primera vez en una carta enviada

por De Morgan a William en 1852, plantendole la cuestin :

Se puede colorear cualquier mapa plano con cuatro colores diferentes de modo

que no haya dos regiones adyacentes con el mismo color?.

Este problema se resuelve mediante la construccin del pseudomultigrafo dual GM del

mapa M correspondiente a un grafo plano G. Donde los vrtices GM son las regiones

de M y las aristas entre dos vrtices (regiones de M) de GM son las aristas que separan

las regiones correspondientes en el mapa M, y si dicha arista cae dentro de una misma

regin, entonces es un lazo. Y aplicando una funcin denominada coloracin c al mapa

MGM del grafo GM , en un conjunto de k colores de modo que para cada par de

vrtices adyacentes u y v de MGM tienen colores distintos.

Denotando la funcin de coloracin de k colores como:

c : V(MGM) {1,2, ... ,k }. Tal que si uv E(MGM) : c(u) c (v). Al nmero k se le denomina NMERO CROMTICO.

Segn el teorema de Kuratowski un mapa plano no puede contener ningn subgrafo

isomorfo a un grafo completo de cinco vrtices K 5 , ni a ningn subgrafo 3-regular

de seis vrtices "K3,3" , entonces se puede demostrar que todo grafo plano admite una

coloracin con cuatro colores.

) Teorema de Kuratowski.- Un grafo G es plano no contiene ningn subgrafo isomorfo a una subdivisin de K5 o K3 3.

) La Suma de regiones de un mapa es igual a 2 veces el nmero de aristas, del grafo que representa. Luego todo grafo tiene un nmero par o cero de vrtices de

grado impar.

# Ejemplo: Si consideramos el mapa correspondiente a la siguiente figura:

Para colorear las regiones de modo que dos regiones adyacentes tengan colores

diferentes, es necesario al menos tres colores. Ya que si consideramos las tres regiones

centrales A, B y C, Puesto que cada una de ellas es adyacente a las otras dos, se

necesitan tres colores para distinguirlas.

A B C

Si definimos la aplicacin c del las regiones en el conjunto de los colores, por medio

de:

c(A) = 1, c(B) = 2 y c(C) = 3.

Adems poniendo para cada regin W del exterior C(W) = C(X) siendo X la regin no

adyacente a W del conjunto {A,B,C}. Tenemos una coloracin de tres colores del Mapa

del grafo dual G M .

) Si al colorear un grafo k = 2 , decimos que el grafo es un grafo BIPARTITO. Es decir Un grafo G = (V, E) se dice que es bipartito si existe una coloracin

: V {0,1} Otras veces se consideran los colores blanco y negro en vez de 0 y 1.

# Ejemplo: El grafo de la figura es bipartito y la coloracin viene

dada por el carcter blanco y negro de cada vrtice de la figura.

El siguiente Teorema da una caracterizacin de los grafos bipartitos.

) Un grafo es bipartito si y solo si no tiene ciclos con longitud impar. # Demostracin:

Si G = (V, E) admite una coloracin : V {0, 1}, los vrtices de cada ciclo tienen que tener alternativamente los colores 0 y 1. Ahora bien como el primer vrtice y el

ltimo coinciden entonces tienen el mismo color. As el nmero de aristas en dicho

ciclo debe ser par

Sea G = (V, E) un grafo en el que todos los ciclos tienen longitud par. Para encontrar

la coloracin de G razonaremos por induccin sobre #E.

Si #E = 0 vale cualquier aplicacin y V {0, 1 }. Supongamos el teorema cierto para cualquier grafo con menos de n aristas y sea

G = (V, E) con #E = n. Sean u, v dos vrtices de G y uv una arista.

Sea G'= (V, E - { uv}).

Caso 1.- En el caso, de que u y v estn en distintas componentes conexas. Si es una coloracin tal que (u) (v), es una es evidente que es una coloracin de G', y por tanto G' es Bipartito. Y si (u) = (v), puesto, que estn en distintas conexas. Podemos definir la coloracin

(x) si x Gv (Componente conexa de v) : (x) =

' (x) = C ( (x)) si x Gv . Siendo: C ( (x)) = 0 , si (x) =1.

C ( (x)) = 1 , si (x) =0.

Caso 2.- En el caso, de que u y v estn en la misma componentes conexas.

Entonces existe un camino, que podemos tomar simple, de u a v:

(u, v1, ... , vs , v).

Como el camino es simple y uv es una arista de G,:

(u, v1 , ... , vs , v , u) es un ciclo de G, y por tanto tiene longitud par.

Con lo que: (u, v1, ... , vs , v) tiene longitud impar. Y por hiptesis de induccin

existe una coloracin:

: V {0,1}. Por tener (u, v1,..., vs , v) longitud impar y por ser coloracin, ser (u) (v) y as define tambin una coloracin de G.