Théorème des quatre couleurs

[Dlzlogic]

Bonjour,
Ce sujet a été évoqué dernièrement à l'occasion d'un autre sujet.
Je rappelle ce dont il s'agit. Soit un ensemble de zones définies par leur périmètre et sans recouvrement ou trous, tels que sont par exemple les départements, il s'agit de colorier chacune des zones avec seulement 4 couleurs de façon que 2 zones ayant une limite commune aient 2 couleurs différentes.
La démonstration de ce théorème a fait l'objet de nombreuses discussions et en l'état actuel des choses, à ma connaissance, on a dressé un catalogue exhaustif des cas à traiter et on a fait tourner un ordinateur pour vérifier qu'aucun de ces cas n'entrainerait une résolution impossible.

Ceci étant dit, il me parait intéressant d'écrire un module qui étant donné la définition géométrique d'un ensemble de telles zones, attribue à chacune d'elle l'une des quatre couleurs satisfaisant aux conditions.
Les données sont supposées être les listes de points formant le périmètre de chaque zone. Ces données sont faciles à trouver pour les départements français, par exemple. Il est bien évident que la donnée de départ est sous forme géographique et non pas un pré-traitement de proximité réalisé par un humain.
Ce problème est intellectuellement intéressant.
Bonne journée.
-----

[JohnArto]

Bonjour

L'exemple des départements français est intuitif, mais assez malheureux puisque, aussi surprenant que cela puisse être, certains départements possèdent des enclaves, et d'autres ont des trous.

Au premier abord, les données étant des listes de points (segments ?) formant les périmètres de chaque zone, on peut établir les zones adjacentes (un segment commun sur les périmètres indique des zones limitrophes), puis se lancer dans la résolution proprement dite du problème des 4 couleurs (qui est un problème de théorie des graphes).

[Dlzlogic]

Bonjour,
Cette réponse m'a échappée.
Le problème des département français est réel, je sais pas où se trouve l'intuition. On peut prendre aussi les régions d'Europe (y'en a beaucoup).
Le fait qu'il y ait des enclaves, donc des trous, est un petit problème annexe, assez facile à résoudre.
Généralement les zones sont décrites par leur périmètre, compte tenu des trous et/ou enclaves, c'est à liste une liste de points. Le problème posé consiste à définir ces 4 couleurs pour les zones, la méthode est libre (indépendamment de tout logiciel existant), sachant que les éléments constituant la base de l'algorithme est une liste de périmètres de zones.

[minushabens]

Les enclaves ne posent aucune difficulté. Ce qui est a priori plus ennuyeux c'est les pays formés de plusieurs polygones disjoints (on les appelle "empires").

[A voir en vidéo sur Futura]

[leon1789]

Les enclaves ne posent aucune difficulté.

Ils sont simplement contraires aux hypothèses du théorème des quatre couleurs, dont les hypothèses portent sur des ensembles connexes. Idem, comme vous dîtes, avec les "empires" à territoires disjoints (i.e. empire non connexe).
Mais il est vrai que l'on peut quand même colorier en 4 couleurs la carte de la métropole (est-ce un coup de chance ?)

[Médiat]

Ils sont simplement contraires aux hypothèses du théorème des quatre couleurs, dont les hypothèses portent sur des ensembles connexes.

Pour être précis, au sens géographique, les enclaves sont effectivement contraires aux hypothèses, mais pas les territoires enclavés.

[minushabens]

Idem, comme vous dîtes, avec les "empires" à territoires disjoints (i.e. empire non connexe)

ce n'est pas moi qui ai inventé le terme "empire" pour désigner un pays non connexe. Il y a une extension du théorème des quatre couleurs qui dit que pour colorier une carte comportant des "m-pires" (empire ayant au plus m>1 composantes connexes) 6m couleurs sont suffisantes et parfois nécessaires. C'est intéressant de voir que le cas m=1 est à part (car 4 n'est pas 6 !)

[Dlzlogic]

Bonjour,
J'ai un peu de mal à vous suivre.
Soit les départements français. Il y a deux ou 3 cas où une petite partie d'un département est située à l'intérieur du périmètre d'un autre. Il y a un exemple tout près de chez moi : une ou deux communes du PdC sont dans le département du Nord. Si on veut représenter les départements avec 4 couleurs, ces deux communes auront naturellement la couleur du PdC.
Je ne vois pas de cas ou de configuration qui nécessiterait 6 couleurs.
Il est vrai que je me place dans le cas où les deux zones concernées sont limitrophes.
Peut-on me donner un exemple (même artificiel) ?

[minushabens]

un pays enclavé dans un autre ne crée pas de difficulté: il suffit de le colorier avec une couleur différente de celle du seul pays qui lui soit voisin. Si en revanche cette enclave est une partie d'un autre pays (ou département comme dans le cas que tu cites) alors il peut y avoir une difficulté si le reste du pays n'est pas adjacent au pays englobant l'enclave et donc pourrait être de la même couleur. Mais dans ce cas on a au moins un pays non connexe (celui de l'enclave) et on n'est plus dans les conditions du théorème des quatre couleurs, mais dans celui qui considère les empires.

[Dlzlogic]

Bonsoir,
La création de ce topic ne concerne pas les conditions particulière de ce théorème, mais simplement un défi d'établissement d'algorithme de calcul de ces quatre couleurs. Je sais calculer cela pour n'importe quel ensemble de zones. Donc c'est juste pour proposer un exercice intéressant. Autrement dit, toute référence à ds choses existantes est sans intérêt.
Bonne soirée.

[Tryss2]

Je ne vois pas de cas ou de configuration qui nécessiterait 6 couleurs.

Tiens, une configuration a 6 pays qui nécessite 6 couleurs (je peux même te donner une configuration à n pays qui nécessite n couleurs)




C'est facile à voir : tout les empires sont frontaliers

[JohnArto]

Merci Tryss pour cet exemple "2-pires" (il faut supprimer l'inutile zone F incluse dans la zone A, sinon F a 3 composantes connexes)

[minushabens]

Il existe des exemples sans enclaves.

[mike.p]

Bonsoir,
La création de ce topic ne concerne pas les conditions particulière de ce théorème, mais simplement un défi d'établissement d'algorithme de calcul de ces quatre couleurs. Je sais calculer cela pour n'importe quel ensemble de zones. Donc c'est juste pour proposer un exercice intéressant. Autrement dit, toute référence à ds choses existantes est sans intérêt.
Bonne soirée.

Salut,

vous savez traiter le problème classique dans tous les cas, super.
Indépendamment du défi, c'est intéressant de savoir si vous recollez à la démo et si vous l'avez testé avec des cas réputés difficiles.

[minushabens]

A ma connaissance, la démonstration du théorème des quatre couleurs ne donne pas de méthode pour effectivement colorier une carte (ou un graphe). C'est un théorème d'existence, il procède par l'absurde: si tous les graphes ne sont pas 4-coloriables, il existe un graphe minimal (au sens du nombre de sommets) qui ne l'est pas. On montre alors qu'on peut toujours trouver un sous-graphe et un 4-coloriage de ce sous-graphe qui peut être étendu au graphe entier. Mais ça ne constitue pas un algorithme.

[Deedee81]

Salut,

Concernant les algorithmes de coloriage, on peut juste regarder dans wikipedia. Ils donnent plusieurs algorithmes : https://fr.wikipedia.org/wiki/Colora...rithmes_exacts

[mike.p]

@minushabens : une démo qui vaut d'être connue ... merci pour le tuyau , je chercherai

[minushabens]

J'avais lu l'article de Appel & Haken (100 pages et 2000 figures!) mais je te recommande plutôt le livre de Fritsch & Fritsch "The four-color theorem" publié chez Springer.

[Dlzlogic]

Bonjour,
J'ai un peu de mal à comprendre.
Il y a un "fameux" théorème. Il y a quelques années, il était très à la mode. Il y a même eu un article d'information, signé, avec références et tout. J'ai essayé de contacter l'auteur parce que le sujet m'intéressait. Impossible, c'était un faux nom et de fausses références.
Apparemment, l'énoncé du théorème est clair (zones limitrophes, quatre couleurs etc.). La littérature précise que la démonstration rigoureuse (au sens mathématique) n'a pas été faite, mais qu'on a établi une démonstration grâce à un traitement informatique.

Je propose le défi qui consiste à établir l'algorithme de calcul, étant donné une liste de zones répondant à l'énoncé. Je propose la carte des départements français parce que je suis français et que ce forum est français. Pas de chance, il y a 2 ou 3 départements qui comportent des enclaves.
Puis on peut voir une configuration avec 6 pays qui nécessite 6 couleurs. Fort bien. Alors l'algorithme est impossible à réaliser. De toute façon, il n'y avait pas besoin d'aller chercher si loin pour trouver un contre-exemple, il suffisait que cette enclave du PdC, au lieu d'être dans le Nord soit située dans le département de la Seine.
Bonne continuation.

[Médiat]

Bonjour

La littérature précise que la démonstration rigoureuse (au sens mathématique) n'a pas été faite, mais qu'on a établi une démonstration grâce à un traitement informatique.

Avez-vous des références ?

La démonstration initiale avec l'aide d'un ordinateur consistait à étudier plus de 500 configurations particulières (dont on a démontré qu'elles représentaient l'exhaustivité des cas possibles), il va de soi que le programme a été vérifié et re-vérifié, je ne vois pas en quoi cette démonstration serait moins rigoureuse que si elle avait été faite par un être humain étudiant ces 500 et quelques configurations à la main.

[JohnArto]

Je pense qu'il y a eu bien davantage qu'un <<article d'information>> sur le théorème, avec des auteurs bien réels, avec de vraie références.
Et l'exemple de 6 pays (non connexes) nécessitant 6 couleurs n'implique pas l'impossibilité d'avoir un algo de coloriage en 4 couleurs les cartes de territoires connexes... parce que les hypothèses ne sont pas les mêmes !
Faut pas tout mélanger.

[Dlzlogic]

@ Médiat,
"La littérature précise que la démonstration rigoureuse (au sens mathématique) n'a pas été faite,"
Ceci n'a rien de péjoratif de ma part. Dans mon esprit l'expression "démonstration rigoureuse" sous-entend une hypothèse, un argumentaire et une conclusion, tel qu'on a appris à le faire en particulier en géométrie.
Une opération qui consiste à répertorier tous les cas possibles et à faire tourner un ordinateur pendant un très grand nombre d'heures permet de montrer que l'hypothèse est juste puisqu'on n'a pas réussi à trouver de contre-exemple, ou plus précisément de configuration qu'il n'est pas possible de colorier avec seulement quatre couleurs.
Mais là n'est pas le sujet de ma question d'origine. Je ne remets rien en cause, je ne cherche aucun contre-exemple, je ne cherche pas plus à démontrer quoi que ce soit, je propose simplement de trouver un algorithme qui réalise ce coloriage à partir d'une liste de zones limitrophes définies par leur périmètre.

[Médiat]

Ceci n'a rien de péjoratif de ma part. Dans mon esprit l'expression "démonstration rigoureuse" sous-entend une hypothèse, un argumentaire et une conclusion, tel qu'on a appris à le faire en particulier en géométrie.

Et si vous utilisez une calculatrice à la fin de votre démonstration pour calculer 17*13, votre démonstration n'est plus rigoureuse ?

Une opération qui consiste à répertorier tous les cas possibles et à faire tourner un ordinateur pendant un très grand nombre d'heures permet de montrer que l'hypothèse est juste puisqu'on n'a pas réussi à trouver de contre-exemple, ou plus précisément de configuration qu'il n'est pas possible de colorier avec seulement quatre couleurs.

Donc d'avoir fait une démonstration rigoureuse !

[Deedee81]

je propose simplement de trouver un algorithme qui réalise ce coloriage à partir d'une liste de zones limitrophes définies par leur périmètre.

Les algorithmes wiki que j'ai indiqué plus haut ne conviennent pas ?

[Dlzlogic]

@ DeeDee,
A vrai dire, je n'ose pas imaginer le temps d'exécution que ça prendrait. Faire un boucla systématique, c'est casse-cou en informatique.
Pour ce qui me concerne, mon algorithme et le code qui le met en oeuvre marchent très bien. J'utilise le fait qu'un triangle ne peut avoir que 3 voisins.
17*13 = 245. Pas sûr que ça conclue efficacement une démonstration dans un contexte bancaire.

[pm42]

il va de soi que le programme a été vérifié et re-vérifié, je ne vois pas en quoi cette démonstration serait moins rigoureuse que si elle avait été faite par un être humain étudiant ces 500 et quelques configurations à la main.

Le programme a été fait plusieurs fois et même formalisé en Coq pour être 100% rigoureux par Werner et Gonthier. Ce genre de preuve est effectivement très solide, largement autant que de très longues démonstrations écrites par un seul humain et vérifiées par très peu d'autres.

[JohnArto]

Pour ce qui me concerne, mon algorithme et le code qui le met en oeuvre marchent très bien.

Avez-vous une "preuve rigoureuse" que votre algorithme fonctionne dans tous les cas, et de manière rapide ? ou bien est-ce un constat valable sur quelques exemples ?

[Dlzlogic]

C'est une bonne question.
Si j'avais la preuve demandée, cela vaudrait démonstration.
L'expérience montre que deux ou trois essais sont généralement nécessaires. Entre un essai et le suivant la seule différence est le départ. Je ne crois pas avoir trouvé de configuration nécessitant plus de trois essais. Les essais successifs sont très rapides.
Naturellement j'ai beaucoup réfléchi à ce problème. Je suis arrivé à la conclusion que si ce théorème est vrai et je sais que c'est le cas, quelle que soit la méthode utilisés, alors l'algorithme trouve forcément la solution.

[JohnArto]

Si je comprends bien, il trouve une solution en quelques essais, donc rapidement. Quels est le nombre de zones à colorer dans vos exemples ?

[Dlzlogic]

J'ai été très clair dans mon premier message. Je ne cherche ni une solution pour un problème qu'on m'aurait posé (je suis assez grand pour me débrouiller tout seul) ni faire la promotion de mon algorithme (ce genre de préoccupation m'indiffère complètement), par contre le sujet me parait intéressant, alors je le propose à titre de défi. Et puis c'est tout. Point.