viernes, 18 de diciembre de 2009

Teorema de cuatro colores

El teorema de cuatro colores es un teorema sobre el coloreo de grafos (mapas), y establece lo siguiente:

Dado cualquier mapa geográfico, éste puede ser coloreado con cuatro colores diferentes, de forma que no queden regiones (países) adyacentes con el mismo color.

Dos regiones (países) se dicen adyacentes si comparten un segmento de borde (frontera) en común, no solamente un punto.

Es fácil ver que no es posible colorear cualquier mapa en estas condiciones con sólo tres colores, y es laborioso pero no complejo demostrar la propiedad con cinco colores.

El problema de los cuatro colores fue planteado por primera vez por Francis Guthrie en 1852 y resuelto en 1976 por Kenneth Appel y Wolfgang Haken con la ayuda de una computadora.

El teorema de cuatro colores ha sido demostrado con la ayuda de un ordenador. La prueba sin embargo, no es aceptada por todos los matemáticos dado que sería impracticable por su gran cantidad de detalles que una persona se vería imposibilitada de verificar manualmente. Sólo queda aceptar la exactitud del programa, del compilador y del computador en el cual se ejecutó la prueba.

Otro aspecto de la prueba, que puede ser considerado negativo, es su falta de elegancia.

En la actualidad ya se realizó otra demostración, pero también haciendo uso de cálculos en la computadora, lo cual verifica la prueba original, pero queda la interrogante de una prueba que se pueda efectuar con lápiz y papel.

No hay comentarios: