Le théorème des 4 couleurs a été prouvé par informatique

Proposé par
le
dans

Le théorème des 4 couleurs veut que tout découpage d'une carte permet de colorier les différentes régions avec seulement 4 couleurs, en évitant que deux couleurs ne se touchent. Il est célèbre car il est le premier théorème à avoir nécessité un ordinateur pour être prouvé, en 1976. Bien que conjecturé depuis 1852, aucune démonstration analytique n'a été trouvée à ce jour.

Le théorème marche pour tout découpage de pays/région, tant qu'on considère les pays partageant une frontière et non juste un point (on considère qu'un découpage en camembert, par exemple, ne pose pas de problème car les différentes régions ne sont en contact que sur un point), et qu'on ne prend pas en compte les "trous" dans des pays (comme des iles qui ne formeraient qu'un pays, par exemple).
En 1976, après avoir isolé un nombre fini (1478) de cas limites (c'est-à-dire des cas qui auraient pu contredire le théorème), Kenneth Appel et Wolfgang Haken les vérifient sur ordinateur, trouvant un coloriage pour chaque cas, et prouvant ainsi le théorème.


Tous les commentaires (29)

a écrit : Cette source est très bien expliquée www.youtube.com/watch?v=g_nTfZ9OgJs
petite vidéo youtube d'une chaine intéressante.
En revoyant la vidéo, je me rend compte qu’il dit une bêtise concernant les ambassades.
Le territoire d’une ambassade n’appartient pas du tout au pays représenté par l’ambassade mais bien au pays où est implantée l’ambassade.

a écrit : Je suis un novice également mais pour prendre du concert, regarde pour la France Metropolitaine. Elle a 7 frontieres terrestres. Imagine que la France est en bleu, Andorre, la Belgique et la Suisse pourrait très bien être en rouge puisque ces 3 pays ne se touchent pas. La France peut avoir plusieurs "voisins" de la même couleur à condition qu'ils ne se touchent pas si j'ai bien compris. Afficher tout Exactement. Le but est simplement que 2 zones qui se touchent soient différentes pour que l'on puisse voir précisément les délimitations de chacune.
Du moment que la couleur doit porter plus d'information que cette seule délimitation (appartenance à un pays, type de climat, nature du produit dans un conduit, etc.) cela peut nécessiter plus de 4 couleurs. Au pire, autant de couleur que de versions possibles de l'information.

a écrit : Oui, mais n'oublie pas que si deux droites se croisent, le point d'intersection n'est pas considéré comme un contact entre les surfaces, car en mathématique, un point n'a aucune dimension. Sur un damier, ca veut dire que deux carrés l'un à coté de l'autre en diagonale peuvent avoir la même couleur.

A part ça, je viens de regarder mon globe terrestre, deux pays (territoires devrait on dire^^) qui se touchent n'ont jamais la même couleur, mais il y en a six (de couleurs) donc, les fabricants de cartes pourraient faire quelques économies avec ce système, en achetant moins de couleurs différentes, donc des couleurs en plus gros volumes.

Ben quoi, autant qu'il serve à quelquechose ce théorème, non? ;)
Afficher tout
Le problème est que l'ensemble des territoires d'un même pays doivent porter la même couleur. Or ce théorème ne fonctionne que pour les territoires unifiés. Du moment qu'il y a morcellement, un nombre plus important de couleur peut être nécessaire.
Autant dire qu'en qualité de français, on a intérêt à se faire discret sur ce point parce que ce sont nos DOM-TOM qui participent grandement à ce problème sur les cartes du Monde.

NB: en cas de morcellement, la règle reste valable si tous les fragments peuvent entre regroupé au sein d'une bulle constituant un territoire unique. Par exemple, en Méditerranée, on peut englober les îles Baléares dans le territoire espagnol, la corse dans le français, la Sardaigne et la Sicile dans l'italien

a écrit : Le problème est que l'ensemble des territoires d'un même pays doivent porter la même couleur. Or ce théorème ne fonctionne que pour les territoires unifiés. Du moment qu'il y a morcellement, un nombre plus important de couleur peut être nécessaire.
Autant dire qu'en qualité de français, on a i
ntérêt à se faire discret sur ce point parce que ce sont nos DOM-TOM qui participent grandement à ce problème sur les cartes du Monde.

NB: en cas de morcellement, la règle reste valable si tous les fragments peuvent entre regroupé au sein d'une bulle constituant un territoire unique. Par exemple, en Méditerranée, on peut englober les îles Baléares dans le territoire espagnol, la corse dans le français, la Sardaigne et la Sicile dans l'italien
Afficher tout
Les DOM TOM n’existent plus depuis 2003. On parle maintenant de DROM, de POM, de COM.

a écrit : En voici un très bon exemple.... Pour démontrer que quatre couleurs sont suffisantes.
Au nord de la Suisse, se trouve l'Allemagne. À l' est, l'Autriche, au sud, l'Italie, et à l'ouest, la France.
Tels et comme des points cardinaux opposés, le couple de pays du nord et du sud
(Allemagne et Italie) ou celui de l'est et de l'ouest (Autriche et France) pourra avoir la même couleur, vu qu'ils ne possèdent pas de frontières communes.
Donc, voici la configuration possible des pays coloriés. Par exemple, la France et l'Autriche seraient de la même couleur. Ceci ne pose aucun problème, vu que les deux pays ne possèdent pas de frontière commune. Une seconde couleur sera attribuée à la Suisse, une troisième à l' Allemagne, et la dernière à l'Italie.

Note que je n'ai pas parlé du Liechtenstein, situé entre la Suisse et l'Autriche, afin de ne pas rendre l'explication plus compliquée. Néanmoins si l'on veut le colorier, il pourrait encore se faire usage de la couleur déjà employée pour représenter l' Allemagne ou l'Italie, vu qu'aucun de ces deux pays ne possède de frontière commune avec ce micro-etat.
Afficher tout
Ah oui effectivement ça paraît évident maintenant. Merci pour l’explication.

a écrit : Le problème est que l'ensemble des territoires d'un même pays doivent porter la même couleur. Or ce théorème ne fonctionne que pour les territoires unifiés. Du moment qu'il y a morcellement, un nombre plus important de couleur peut être nécessaire.
Autant dire qu'en qualité de français, on a i
ntérêt à se faire discret sur ce point parce que ce sont nos DOM-TOM qui participent grandement à ce problème sur les cartes du Monde.

NB: en cas de morcellement, la règle reste valable si tous les fragments peuvent entre regroupé au sein d'une bulle constituant un territoire unique. Par exemple, en Méditerranée, on peut englober les îles Baléares dans le territoire espagnol, la corse dans le français, la Sardaigne et la Sicile dans l'italien
Afficher tout
En toute logique, même si tous les territoires d'un pays doivent avoir la même couleur, vu que, par exemple, la Guyane et St Pierre-et-Miquelon sont séparés par un "trou" (un non-territoire, l'océan Atlantique dans notre cas) entre eux et entre la métropole cela doit quand même fonctionner avec 4.

a écrit : En toute logique, même si tous les territoires d'un pays doivent avoir la même couleur, vu que, par exemple, la Guyane et St Pierre-et-Miquelon sont séparés par un "trou" (un non-territoire, l'océan Atlantique dans notre cas) entre eux et entre la métropole cela doit quand même fonctionner avec 4. Effectivement, si c'est complétement séparé, ça va (parce qu'on considère alors qu'on a deux cartes indépendantes). Par contre si la fragmentation est belle et bien sur la même carte et ne peut pas être "rassemblé" (comme expliqué dans un des commentaires), alors ça ne marche plus (c'aurait été le cas des ambassades si leur territoire n’appartenait pas au pays accueillant). Il est assez facile de s'en convaincre en voyant qu'on rajoute une contrainte et qu'il peut exister des contres-exemples. On en trouve assez vite en gribouillant quelques schéma (moi j'ai trouvé à partir de 7 territoires/6 pays), et ça donne aussi une bonne intuition de pourquoi ça marche sans ladite contrainte !

a écrit : En revoyant la vidéo, je me rend compte qu’il dit une bêtise concernant les ambassades.
Le territoire d’une ambassade n’appartient pas du tout au pays représenté par l’ambassade mais bien au pays où est implantée l’ambassade.
Encore une de ces légendes urbaines qui ont la vie dure.... Probablement motivée par la confusion entre le statut diplomatique de son personnel, et le bâtiment en soi.

a écrit : Il me semble que l'anecdote est mal formulée dans sa première phrase.
Ce que l'auteur a voulu expliquer, c'est qu'il ne sera jamais indispensable de faire usage d'une seule et même couleur, pour représenter deux entités territoriales limitrophes, même dans une situation de quintipoint
(cinq territoires se réunissant en un point où lieu précis).

A l'échelle des Pays/Nations du Monde, il n'existe pas de situation réelle de quadripoint. Ce qui se rapproche le plus, est la convergence des territoires de la Namibie, la Zambie, le Botswana et du Zimbabwe.
Dans le cas de quintipoint, il existe plusieurs cas communaux en France, ainsi que deux sextipoints. Il y a même un sextipoints comunal en Finlande et un octipoint aux Philippines.
Afficher tout
Et aux pôles?