Algoritmo de coloreo

Orígenes del Algoritmo de Coloreo
El problema del coloreo de mapas planos tiene sus orígenes en la década de 1850 planteado por Francis Guthrie. Muchos matemáticos han dedicado parte de sus vidas en demostrar cuál es la menor cantidad de colores que se deben utilizar para pintar un mapa plano sin que dos regiones limítrofes estén pintadas con el mismo color. Pero fue recién en 1976, y gracias ala ayuda de las computadoras, se pudo demostrar que la menor cantidad de colores que podían utilizarse era 4.
El 17 de Julio de 1879, Alfred Bray Kempe anunció que tenía una demostración de la Conjetura de los Cuatro Colores. El Teorema y su demostración fueron publicados en el Periódico Americano de Matemáticas en 1879. Pero en 1890 Percy John Heawood demostró que era errónea.
Fue en 1976cuando, finalmente, se resolvió la Conjetura de los Cuatro Colores. La prueba fue obtenida por Appel y Haken, quienes trabajaron sobre los métodos que había utilizado Kempe y otros métodos creados en los últimos años. Appel y Haken utilizaron 1200 horas de computadora para trabajar en la prueba final. Los algoritmos originales fueron programados en PHP y una versión interactiva del último algoritmooptimizado fue realizada en Macromedia Flash. Este puede ser considerado como el nacimiento de la teoría de grafos. Al tratar de resolverlo, los matemáticos definieron términos y conceptos teóricos fundamentales de los grafos.
¿Porqué no bastan 3 colores para realizar el coloreo?


Ejemplo de coloreo de un mapa por medio del algoritmo de coloreo
El mapa anterior muestra que tres colores nobastan: Si se empieza por el país central a y se esfuerza uno en utilizar el menor número de colores, entonces en la corona alrededor de a alternan dos colores. Llegando al país h se tiene que introducir un cuarto color. Lo mismo sucede en i si se emplea el mismo método.
La forma precisa de cada país no importa; lo único relevante es saber qué país toca a qué otro. Estos datos están incluidos en elgrafo donde los vértices son los países y las aristas conectan los que justamente son adyacentes. Entonces la cuestión equivale a atribuir a cada vértice un color distinto del de sus vecinos.
Hemos visto que tres colores no son suficientes, y demostrar que con cinco siempre se llega, es bastante fácil. Pero el teorema de los cuatro colores no es nada obvio. Prueba de ello es que se han tenido queemplear ordenadores para acabar la demostración (se ha hecho un programa que permitió verificar una multitud de casos, lo que ahorró muchísimo tiempo a los matemáticos). Fue la primera vez que la comunidad matemática aceptó una demostración asistida por ordenador, lo que ha creado una fuerte polémica dentro de la comunidad matemática, llegando en algunos casos a plantearse la cuestión de que estademostración y su aceptación es uno de los momentos que han generado una de las más terribles crisis en el mundo matemático.

Coloración de Grafos

Figura 2: Colores en los vértices.
Definición: Si G=(V, E) es un grafo no dirigido, una coloración propia de G, ocurre cuando coloreamos los vértices de G de modo que si {a, b} es una arista en G entonces a y b tienen diferentes colores. (Por lotanto, los vértices adyacentes tienen colores diferentes). El número mínimo de colores necesarios para una coloración propia de G es el número cromático de G y se escribe como C (G). Sea G un grafo no dirigido sea λ el número de colores disponibles para la coloración propia de los vértices de G. Nuestro objetivo es encontrar una función polinomial P (G,λ), en la variable λ, llamada polinomiocromático de G , que nos indique el número de coloraciones propias diferentes de los vértices de G, usando un máximo de λ colores.

A continuación se mostrará por medio de un ejemplo la implementación del algoritmo de coloreo. El ejemplo explica paso a paso como es que se utiliza este algoritmo.

COLOREO DE MAPAS ALGORITMO DE ELIMINACIÓN DE POSIBILIDADES
Planteamiento del problema:
El problema...