Grafos

APLICACIONES DE LA TEORÍA DE GRAFOS.. APLICACIONES DE LA TEORÍA DE GRAFOS

Los grafos de tipo de árbol son utilizados en métodos de optimización en
aplicaciones de un grupo de objetos unidos mediante alguna relación. También se suele emplear en Estadística para caracterización de espacios muestrales y cálculo de probabilidades # Ejemplo: Supongamos que tres caballos {a,b,c} corren juntos enuna carrera, y que sus probabilidades de ganar son ½ , 1/3 y 1/6 respectivamente. Si se efectúan dos carreras consecutivas, el espacio muestral de los resultados vendrá caracterizado por: a a ½ b c a b c a b c

b 1/3 1/6 c

Para hallar las respectivas probabilidades de los resultados de la competición bastará multiplicar los pesos de las correspondientes ramas. Por ejemplo la probabilidad de queel resultado sea (c,a) será: P( (c,a) ) = (1/6).(1/3) = 1/18. Una aplicación importante en la representación plana de mapas aplicada a los poliedros, sin recurrir a la topología algebraica es la Formula de Euler:

El número de caras - número de aristas + número de vértices es igual a 2.
Mediante la identificación de las caras del poliedro con las regiones del mapa asociado al conjunto de susvértices.. Otra aplicación 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, planteándole la cuestión : ¿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 resuelvemediante la construcción del pseudomultigrafo dual GM del mapa M correspondiente a un grafo plano G. Donde los vértices GM son las regiones de M y las aristas entre dos vértices (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 región, entonces es un lazo. Y aplicando una función denominada coloración c al mapa MGMdel grafo GM , en un conjunto de k colores de modo que para cada par de vértices adyacentes u y v de MGM tienen colores distintos. Denotando la función de coloración de k colores como:

c : V(MGM) → {1,2, ... ,k }. Tal que si uv ∈ E(MGM) : c(u) ≠ c (v).
Al número k se le denomina NÚMERO CROMÁTICO. Según el teorema de Kuratowski un mapa plano no puede contener ningún subgrafo isomorfo a un grafocompleto de cinco vértices K 5 , ni a ningún subgrafo 3-regular de seis vértices "K3,3" , entonces se puede demostrar que todo grafo plano admite una coloración con cuatro colores. Teorema de Kuratowski.- Un grafo G es plano ⇔ no contiene ningún subgrafo isomorfo a una subdivisión de K5 o K3 3. La Suma de regiones de un mapa es igual a 2 veces el número de aristas, del grafo que representa. Luegotodo grafo tiene un número par o cero de vértices de grado impar. # Ejemplo: Si consideramos el mapa correspondiente a la siguiente figura:

A

B

C

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 otrasdos, se necesitan tres colores para distinguirlas.

Si definimos la aplicación c del las regiones en el conjunto de los colores, por medio de: c(A) = 1, c(B) = 2 y c(C) = 3. Además poniendo para cada región W del exterior C(W) = C(X) siendo X la región no adyacente a W del conjunto {A,B,C}. Tenemos una coloración 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 coloración γ: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 coloración viene dada por el carácter blanco y negro de cada vértice de la figura. El siguiente Teorema da una caracterización de los grafos...