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.


Commentaires préférés (3)

a écrit : Quand ça parle de "découpage d'une carte", ça mentionne une carte du monde ou bien des formes aléatoires (comme l'image d'illustration de la source Wikipedia) ?
J'avoue ne pas du tout comprendre l'anecdote...
De mon point de vue il suffit qu'une zone soit en contact a
vec 4 autres pour que tout ce théorème tombe à l'eau.
Je suis, bien entendu, certain de passer à côté de quelque chose dans cette anecdote pour bien la comprendre. Si quelqu'un pouvait m'aiguiller ce serait sympa.
Afficher tout
Non, ça fonctionne. Si une couleur est en contact avec quatre autres, comme vous le dites, celle-ci aura une couleur (1), et les quatre autres pourront avoir (2), (3), (2) et (3 ou 4) comme couleurs. L’interdit n’est pas qu’une couleur touche deux fois une autre couleur, mais qu’elle touche LA SIENNE.

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.

a écrit : Pas trop compris, cela marche avec des cartes imaginaires ? N'importe quel découpage géographique ça veut dire que si je trace des droites sur la carte de France (do'c que je redecoupe le territoire comme je le souhaite) est ce que ça marche ? Oui ! En gros, si tu prends une feuille de papier sur laquelle tu traces plusieurs formes qui se touchent les unes les autres, seulement 4 crayons de couleur différentes sont nécessaires pour pouvoir colorier toutes ces formes sans que deux formes qui se touchent aient la même couleur.

Par exemple, avec du bleu, du vert, du rouge, et du jaune, on peut colorier l’ensemble des pays situés sur un planisphère sans que deux pays frontaliers aient la même couleur. Ainsi cela fonctionne sur un planisphère terrestre mais aussi sur un planisphère imaginé.

Cependant, comme l’anecdote le précise, il faut en réalité penser sous forme de territoires et non de pays. De cette façon, pour être sûr que cela fonctionne dans le cas d’une carte du monde, il faudrait distinguer la Guyane et la France métropolitaine en ne les obligeant pas à avoir la même couleur ;)


Tous les commentaires (29)

Quand ça parle de "découpage d'une carte", ça mentionne une carte du monde ou bien des formes aléatoires (comme l'image d'illustration de la source Wikipedia) ?
J'avoue ne pas du tout comprendre l'anecdote...
De mon point de vue il suffit qu'une zone soit en contact avec 4 autres pour que tout ce théorème tombe à l'eau.
Je suis, bien entendu, certain de passer à côté de quelque chose dans cette anecdote pour bien la comprendre. Si quelqu'un pouvait m'aiguiller ce serait sympa.

Posté le

android

(6)

Répondre

a écrit : Quand ça parle de "découpage d'une carte", ça mentionne une carte du monde ou bien des formes aléatoires (comme l'image d'illustration de la source Wikipedia) ?
J'avoue ne pas du tout comprendre l'anecdote...
De mon point de vue il suffit qu'une zone soit en contact a
vec 4 autres pour que tout ce théorème tombe à l'eau.
Je suis, bien entendu, certain de passer à côté de quelque chose dans cette anecdote pour bien la comprendre. Si quelqu'un pouvait m'aiguiller ce serait sympa.
Afficher tout
Non, ça fonctionne. Si une couleur est en contact avec quatre autres, comme vous le dites, celle-ci aura une couleur (1), et les quatre autres pourront avoir (2), (3), (2) et (3 ou 4) comme couleurs. L’interdit n’est pas qu’une couleur touche deux fois une autre couleur, mais qu’elle touche LA SIENNE.

en effet, anecdote mal formulée. le théorème stipule qu une même couleur ne peut se toucher.

Posté le

android

(5)

Répondre

JLSD ! Grâce à la vidéo de ScienceEtonnante sur YouTube. Je vous conseille d’aller la voir elle explique très bien ce théorème !

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.

Je suis content de voir cette anecdote ;) je l’avais soumise ici sans succès après avoir vu la vidéo de science étonnante il y a quelques temps déjà.
Allez voir la vidéo pour comprendre le théorème qui n’est pas si simple que ça.

Pas trop compris, cela marche avec des cartes imaginaires ? N'importe quel découpage géographique ça veut dire que si je trace des droites sur la carte de France (do'c que je redecoupe le territoire comme je le souhaite) est ce que ça marche ?

Posté le

android

(2)

Répondre

a écrit : Pas trop compris, cela marche avec des cartes imaginaires ? N'importe quel découpage géographique ça veut dire que si je trace des droites sur la carte de France (do'c que je redecoupe le territoire comme je le souhaite) est ce que ça marche ? Oui ! En gros, si tu prends une feuille de papier sur laquelle tu traces plusieurs formes qui se touchent les unes les autres, seulement 4 crayons de couleur différentes sont nécessaires pour pouvoir colorier toutes ces formes sans que deux formes qui se touchent aient la même couleur.

Par exemple, avec du bleu, du vert, du rouge, et du jaune, on peut colorier l’ensemble des pays situés sur un planisphère sans que deux pays frontaliers aient la même couleur. Ainsi cela fonctionne sur un planisphère terrestre mais aussi sur un planisphère imaginé.

Cependant, comme l’anecdote le précise, il faut en réalité penser sous forme de territoires et non de pays. De cette façon, pour être sûr que cela fonctionne dans le cas d’une carte du monde, il faudrait distinguer la Guyane et la France métropolitaine en ne les obligeant pas à avoir la même couleur ;)

a écrit : Pas trop compris, cela marche avec des cartes imaginaires ? N'importe quel découpage géographique ça veut dire que si je trace des droites sur la carte de France (do'c que je redecoupe le territoire comme je le souhaite) est ce que ça marche ? 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? ;)

Pleins de gens ont parfaitement expliqué et clarifié le théorème, merci !
Il est effectivement un peu contre-intuitif, mais il marche bien. Je le trouve doublement intéressant parce qu'il n'y a pas de "preuve formelle" (une démonstration mathématique avec pleins d'implication pour arriver au résultat), il a fallu utiliser une "méthode brute" de vérification par ordinateur, depuis améliorer. J'avais indiquer la vidéo de Science étonnante comme source qui a disparu, comme ceux qui l'ont fait je vous recommande chaudement de la voir !

Est-ce que le théorème des 4 couleurs a été inventé par Bic...??

Posté le

android

(4)

Répondre

a écrit : Oui ! En gros, si tu prends une feuille de papier sur laquelle tu traces plusieurs formes qui se touchent les unes les autres, seulement 4 crayons de couleur différentes sont nécessaires pour pouvoir colorier toutes ces formes sans que deux formes qui se touchent aient la même couleur.

Par exemple, avec du
bleu, du vert, du rouge, et du jaune, on peut colorier l’ensemble des pays situés sur un planisphère sans que deux pays frontaliers aient la même couleur. Ainsi cela fonctionne sur un planisphère terrestre mais aussi sur un planisphère imaginé.

Cependant, comme l’anecdote le précise, il faut en réalité penser sous forme de territoires et non de pays. De cette façon, pour être sûr que cela fonctionne dans le cas d’une carte du monde, il faudrait distinguer la Guyane et la France métropolitaine en ne les obligeant pas à avoir la même couleur ;)
Afficher tout
Quelque chose doit m’échapper... Prenons le cas de la Suisse. Elle est entourée par la France, l’Italie, l’Allemagne et l’Autriche. Donc il faudrait plus que 4 couleurs non ? Sinon on aurait une frontière avec deux fois la même couleur.
Ou sinon j’ai rien compris.

a écrit : Quelque chose doit m’échapper... Prenons le cas de la Suisse. Elle est entourée par la France, l’Italie, l’Allemagne et l’Autriche. Donc il faudrait plus que 4 couleurs non ? Sinon on aurait une frontière avec deux fois la même couleur.
Ou sinon j’ai rien compris.
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.

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
en fait, dans ton exemple, trois couleurs suffisent.
couleur A pour la Suisse, couleur B pour la France et l'Autriche, couleur C pour l'Italie et l'Allemagne. le Liechtenstein, lui, serait aussi de couleur C.
par contre, la situation changerait si on ajoute le Luxembourg et la Belgique.

Je le savait déjà !
Je l’ai appris grâce à la chaîne El Jj sur YouTube. C’est une chaîne qui explique des problème mathématique et un tas d’autre trucs, et c’est toujours très bien imagé, et montée, je recommande !

a écrit : Quand ça parle de "découpage d'une carte", ça mentionne une carte du monde ou bien des formes aléatoires (comme l'image d'illustration de la source Wikipedia) ?
J'avoue ne pas du tout comprendre l'anecdote...
De mon point de vue il suffit qu'une zone soit en contact a
vec 4 autres pour que tout ce théorème tombe à l'eau.
Je suis, bien entendu, certain de passer à côté de quelque chose dans cette anecdote pour bien la comprendre. Si quelqu'un pouvait m'aiguiller ce serait sympa.
Afficher tout
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.

Posté le

android

(2)

Répondre

a écrit : Quelque chose doit m’échapper... Prenons le cas de la Suisse. Elle est entourée par la France, l’Italie, l’Allemagne et l’Autriche. Donc il faudrait plus que 4 couleurs non ? Sinon on aurait une frontière avec deux fois la même couleur.
Ou sinon j’ai rien compris.
Le mieux c'est encore d'essayer, dessiner autant de surfaces que l'on veut, avec autant de frontières linéaires que l'on veut, et ben... ca marche!

Je le sais, je viens d'essayer, et a chaque fois que je me disais que ca marchait pas, invariablement j'oubliais qu'une surface peut toucher plusieurs fois une même couleur tant que ce n'est pas la sienne et HOP magique! ^^