English
عربى
中文
Deutsch
Español
Français
हिन्दी
Hrvatski
Italiano
日本語
Português
Română
Русский
Svenska
Türkçe
Tiếng ViệtGráficos y RedesMapa para colorear
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
South America
Germany
England
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
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
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
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.