Un ejemplo de un mapa del mundo que no es de 4-colourable?

Question

Los cuatro colores de asignación teorema establece que todos los mapas pueden ser de cuatro colores (regiones adyacentes reciben distintos colores, y cuatro colores diferentes se utilizan en total). Sin embargo, la definición técnica de "mapa" implica que las regiones deben ser continuos, y, de hecho, es fácil construir contra-ejemplos para una propuesta de "cuatro-color no necesariamente contiguos de asignación de conjetura". Por ejemplo:

donde las dos zonas verdes constituyen una sola no contiguos de la región. Claramente, este no es de cuatro colourable desde cada una de las cinco regiones internas es adyacente a todos los demás (formando un $K_5$ en la teoría de grafos sentido).

Algunos en el mundo real los mapas tienen distintos componentes (por ejemplo, Estados Unidos, incluyendo Alaska, Hawai), lo que me lleva a:

Pregunta: ¿Qué es un ejemplo de un mapa del mundo (que necesariamente debe tener al menos un no-contiguos región) que no es de cuatro colourable?

Answer 1

Wikipedia tiene una lista de conjuntos de cuatro países que bordean el uno al otro; incluye un par de división entre los países (Rusia, Bielorrusia, Lituania-Rusia-Polonia, con Kaliningrado separado del resto de Rusia y Azerbaiyán en Azerbaiyán-Irán-Armenia-Turquía). No parece ser cualquier conjunto de 5 o más en la actualidad.

Agregó: sin Embargo, se podría argumentar que la existencia de desconectado países, de hecho, las fuerzas de ciertos mapas a utilizar más colores, aunque no implican desconectado países. Por ejemplo, un mapa de Europa que necesariamente requieren de diferentes colores para Francia, Bélgica, los países Bajos, Alemania, Dinamarca, Noruega y el Reino Unido (posiblemente también de Irlanda), para que no parezca que uno de esos países es desconectado en dos regiones adyacentes. Esto también muestra algunas de las dificultades que las islas producir (en oposición a la visión idealizada de los mapas del teorema).

Hubo un tiempo, cuando gran Bretaña, España, Francia, Portugal y la República holandesa rodeada de unos a otros (principios del 18vo siglo, contando fronteras que se extiende entre las colonias); y a partir de finales del siglo 19 hasta antes de la I Guerra Mundial, lo hizo Bélgica, Portugal, Alemania, Francia, el Reino Unido y los países Bajos (lo que exige seis colores; de nuevo, esto incluye a las colonias que pueden estar en la frontera de la otra).

Es posible que algunas de las divisiones menores (estados, provincias, etc.) podría incluir tales conjuntos.

Como he señalado en el comentario, no es una suposición incorrecta en su pregunta que un contraejemplo debe tener desconectado regiones: en los cuatro colores del mapa teorema se supone que las regiones vecinas tienen un borde de medida positiva. Países/estados reunión en un punto (como el Colorado, Utah, Nuevo México y Arizona reunión a las Cuatro de Estado de la Esquina) se requiere el uso de diferentes colores en los mapas, pero en el contexto de la 4-mapa de color teorema de las regiones que sólo se reúnen en el punto podría ser de color utilizando el mismo color.

Answer 2

Aquí está un mapa del sacro Imperio Romano después de la Paz de Westfalia en 1648.

En el esquema de color del mapa de políticas han elegido, las piezas del mapa con la etiqueta "Baviera" (verde), "Austriaca de los Habsburgo" (luz verde), "Eclesiástico" (luz violeta), "Hohenzollern de Franconia" (de color marrón claro, incluyendo Ansbach y Bayreuth), y "Ciudades Imperiales" (rojo) todos en contacto. Así que cinco son requeridos colores para diferenciarlos.

Answer 3

Google "África colonial". El Belga, francés, alemán, Británico y Portugués colonial áreas adyacentes. La única difíciles de distinguir de adyacencia aquí es el portugués-francés, que está al cuidado de Cabinda y África Ecuatorial francesa. (Este mapa, en realidad sólo requiere de cinco colores, ya que el italiano, Belga, y de las colonias españolas, no son contiguos, y Etiopía no es contigua a una colonia alemana).