English
عربى
中文
Deutsch
Español
Français
हिन्दी
Hrvatski
Italiano
日本語
Português
Română
Русский
Svenska
Türkçe
Tiếng ViệtGraphes et réseauxColoration de la carte
Nous avons déjà utilisé la théorie des graphes avec certaines cartes. En faisant un zoom arrière, des routes et des ponts disparaissent et nous voyons les contours de pays entiers.
Lors de la coloration d'une carte - ou de tout autre dessin constitué de régions distinctes - les pays adjacents ne peuvent pas avoir la même couleur. Nous pourrions aussi vouloir utiliser le moins possible de couleurs différentes.
Certaines «cartes» simples, comme un échiquier, n'ont besoin que de deux couleurs (noir et blanc), mais la plupart des cartes complexes nécessitent davantage.
Lorsque vous colorez la carte des États américains, 50 couleurs suffisent évidemment, mais il en faut beaucoup moins. Essayez de colorier les cartes ci-dessous avec le moins de couleurs possible:
États Unis
Amérique du sud
Allemagne
Angleterre
Toutes ces cartes peuvent être colorées avec seulement quatre couleurs différentes, mais il n’est pas difficile d’imaginer que d’autres cartes très complexes pourraient nécessiter beaucoup plus de couleurs. En fait, certaines cartes nécessitent au moins couleurs, lorsqu'elles contiennent quatre pays connectés entre eux.
Comme auparavant, nous pouvons convertir une carte avec des pays et des frontières en un graphique planaire: chaque pays devient
Nous souhaitons maintenant colorer les sommets d'un graphique. Deux sommets doivent avoir une couleur différente s'ils sont connectés par une arête.
En 1852, l’étudiant en botanique
Au cours des 100 années suivantes, de nombreux mathématiciens ont publié des «preuves» du théorème des quatre couleurs, uniquement pour que des erreurs soient trouvées ultérieurement. Certaines de ces preuves non valides étaient si convaincantes qu'il a fallu plus de 10 ans pour découvrir des erreurs.
Pendant longtemps, les mathématiciens ont été incapables de prouver que quatre couleurs suffisaient ou de trouver une carte nécessitant plus de quatre couleurs.
Le problème des quatre couleurs n’a guère progressé jusqu’en 1976, lorsque
Le théorème des quatre couleurs est le premier théorème mathématique bien connu à avoir été prouvé à l'aide d'un ordinateur, ce qui est devenu beaucoup plus courant et moins controversé depuis. Des ordinateurs plus rapides et un algorithme plus efficace signifient qu'aujourd'hui, vous pouvez résoudre le théorème des quatre couleurs sur un ordinateur portable en seulement quelques heures.
Cachet postal du département de mathématiques de l'Université
de l'Illinois Urbana-Champaign, où travaillaient Haken et Appel.
Le théorème des quatre couleurs ne fonctionne que pour les cartes sur un plan plat ou une sphère et où tous les pays se composent d'une seule zone.
Cependant, les mathématiciens ont également examiné des cartes de empires, où les pays peuvent être constitués de plusieurs composants déconnectés, ainsi que des cartes de planètes de formes différentes, telles qu'un tore (forme de beignet). Dans ces cas, vous aurez peut-être besoin de plus de quatre couleurs et les épreuves deviennent encore plus difficiles.
Cette carte sur tore nécessite sept couleurs.