Glosario

Seleccione una de las palabras clave de la izquierda ...

Gráficos y RedesMapa para colorear

Tiempo de leer: ~15 min
Esta página ha sido traducida automáticamente y puede contener errores. ¡Póngase en contacto si desea ayudarnos a revisar las traducciones!

Ya hemos usado la teoría de grafos con ciertos mapas. A medida que nos alejamos, desaparecen carreteras y puentes individuales y en su lugar vemos el contorno de países enteros.

Al colorear un mapa, o cualquier otro dibujo que conste de regiones distintas, los países adyacentes no pueden tener el mismo color. También podríamos querer usar la menor cantidad posible de colores diferentes.

Algunos "mapas" simples, como un tablero de ajedrez, solo necesitan dos colores (blanco y negro), pero la mayoría de los mapas complejos necesitan más.

Al colorear el mapa de los estados de EE. UU., 50 colores son obviamente suficientes, pero se necesitan muchos menos. Intente colorear los mapas a continuación con la menor cantidad de colores posible:

United States

0 colours used

South America

0 colours used

Germany

0 colours used

England

0 colours used

Todos estos mapas se pueden colorear con solo cuatro colores diferentes, pero no es difícil imaginar que otros mapas muy complicados puedan necesitar muchos más colores. De hecho, algunos mapas necesitan al menos cuatro colores, siempre que contengan cuatro países, todos conectados entre sí.

Como antes, podemos convertir un mapa con países y fronteras en un gráfico plano: cada país se convierte en y países que conectado por un borde:

Ahora queremos colorear los vértices de un gráfico, y dos vértices deben tener un color diferente si están conectados por un borde.

En 1852, el estudiante de botánica Francis Guthrie tuvo que colorear un mapa de condados en Inglaterra. Observó que cuatro colores parecían ser suficientes para cualquier mapa que intentara, pero no pudo encontrar una prueba que funcionara para todos los mapas. Esto resultó ser un problema extremadamente difícil, y se conoció como el teorema de los cuatro colores .

Durante los siguientes 100 años, muchos matemáticos publicaron "pruebas" del teorema de los cuatro colores, solo para errores que se encontrarán más adelante. Algunas de estas pruebas inválidas fueron tan convincentes que tardó más de 10 años en descubrir errores.

Durante mucho tiempo, los matemáticos no pudieron probar que cuatro colores son suficientes o encontrar un mapa que necesitara más de cuatro colores.

Se hicieron pocos progresos en el problema de los cuatro colores hasta 1976, cuando Wolfgang Haken y Kenneth Appel usaron una computadora para finalmente resolverlo. Redujeron infinitamente muchos mapas posibles a 1936 casos especiales, que fueron verificados por una computadora que tomó más de 1000 horas en total.

El teorema de los cuatro colores es el primer teorema matemático conocido que se prueba usando una computadora, algo que se ha vuelto mucho más común y menos controvertido desde entonces. Las computadoras más rápidas y un algoritmo más eficiente significan que hoy puede probar el teorema de los cuatro colores en una computadora portátil en solo unas pocas horas.

Postmark for the Department of Mathematics at the University of
Illinois Urbana-Champaign, where Haken and Appel worked.

El teorema de cuatro colores solo funciona para mapas en un plano plano o una esfera, y donde todos los países consisten en un área única.

Sin embargo, los matemáticos también han observado mapas de imperios , donde los países pueden consistir en múltiples componentes desconectados, y mapas en planetas de formas diferentes, como un toro (forma de rosquilla). En estos casos, puede necesitar más de cuatro colores y las pruebas se vuelven aún más difíciles.

This map on a torus requires seven colours.