martes, 12 de abril de 2011

Problema de los 4 colores

El problema de los cuatro colores fue planteado por primera vez por Francis Guthrie en 1852 y resuelto positivamente en 1976 por Kenneth Appel y Wolfgang Haken.
En  teoria de grafos, el teorema de cuatro colores es un teorema sobre la coloración de grafos que establece lo siguiente.
Dado cualquier mapa geográfico con regiones continuas, éste puede ser coloreado con cuatro colores diferentes con el mismo color.
 
No es posible colorear cualquier mapa en estas condiciones utilizando sólo tres colores. En cambio, sí es posible hacerlo considerando cinco colores

 




Finalmente en 1976 (¡124 años después de que se había propuesto el problema!) dos matemáticos de la Universidad de Illinois en Estados Unidos, Kenneth Appel y Wolfgang Haken, usando una computadora Cray de segunda generación, analizaron 1900 posibles arreglos de regiones en el plano, o sea, analizaron 1900 tipos distintos de mapas. La computadora tardó 1,200 horas en correr un programa que tenía miles de líneas de largo, y para todos los mapas encontró una coloración en la que a lo más se usaban cuatro colores. ¡El problema había sido resuelto!

No hay comentarios:

Publicar un comentario