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 teoría 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!
Fuente
wilson. (12 de abriil de 2011). Historia de las matematicas discretas. Recuperado el 27 de junio de 2012, de blogspot.mx: http://historiamatematicasdiscretas.blogspot.mx/2011/04/problema-de-los-4-colores.html
0 Comentarios