Théorème des quatre couleurs

[Tryss2]

L'intérêt de cette méthode est qu'il n'y a pas de retour en arrière. Si on tombe sur un cul-de-sac, on recommence au départ en prenant un autre triangle comme origine.

Parce que recommencer du début n'est pas un retour en arrière?
-----

[invitec0f983f7]

Alors, en gros, voila ma méthode :
1- j'identifie tous les points caractéristiques, c'est à dire les "points communs" à 3 zones.
2- à l'aide de ces points je crée une triangulation (cf Delaunay).
3- éventuellement certains côté (diagonales) doivent être échangés.
4- chaque zone est maintenant constituée de triangles. C'est à dire que tous les triangles de cette zone ont la même couleur.
5- point très important et qui justifie la méthode, un triangle ne peut avoir que 3 voisins. Comme la couleur de ce triangle est fixée, ainsi que le voisin qui l'a colorié, il reste au maximum 2 couleurs possibles.

Vous remplacer donc chaque zone à colorier par un ensemble de triangles (qu'il faut évidemment colorier avec la même couleur).
Du coup, vous vous retrouver avec beaucoup plus de triangles qu'il n'y avait de zones initialement.
Il faut maintenant colorier les triangles, en tenant compte du fait qu'ils doivent avoir la même couleur que certains voisins (car dans la même zone) et être de couleur différentes des autres voisins (car pas dans le même zone).
La situation est bien celle-ci ?

[Dlzlogic]

Oui, en gros c'est ça.
Mais il apparait que la phase préparatoire, qui n'est pas un prétraitement, c'est à dire recherche des points particuliers et création de la triangulation est la plus longue. Cette étape doit être faite forcément, d'une façon ou d'une autre. Le reste est linéaire, et, sauf si on doit recommencer, très rapide.
Je crois même que des essais ont été faits avec un programme interprété, en tout cas ils ont validés dans le cadre de ce forum de SIG. Cela date de quelques années, donc cela prouve que ce n'était que d'un intérêt purement intellectuel.

[invitec0f983f7]

Je me suis fendu ce soir d'un petit programme pour colorier la carte de la métropole.

Le programme montre que 3 couleurs ne sont pas suffisantes à cause, par exemple, des départements n°15,7,48,12,43,30.

Mais avec 4 couleurs, c'est tout de même très facile avec juste une astuce bêbête. Voici une méthode (heuristique) :
1- on ordonne 4 couleurs, disons A,B,C,D
2- on considère la liste L des départements dans l'ordre de leur numéro (1 à 95)
3- on parcours dans l'ordre les départements de L en leur attribuant la première couleur possible parmi A,B,C,D (en respectant les règles évidemment).
4- si ça coince au département n°i, on déplace i de la liste L en première place et on recommence l'étape 3.

Il n'y aucune preuve que cet algo termine à chaque fois. Mais déjà, ce bête algorithme donne un résultat positif instantanément (à l'échelle humaine) pour les départements.

On peut l'améliorer en ordonnant au départ (étape 2) les départements par ordre décroissant de nombre de voisins. Dans ce cas, le 5ème retour à l'étape 3 est favorable et c'est terminé.

Je ne sais pas si Dlzlogic parle de cet algorithme...

[invite75a796c1]

il faut reconnaitre que la disponibilité d'une démonstration informatique du coloriage de tous les sous-graphes n'est pas claire et qu'il y a une controverse de fond, pas seulement sur le fait d'utiliser l'informatique.

le wiki en anglais

Ca rend le pb intéressant même si maintenant il semble qu'il n'y ait plus aucun doute quand on considère l'union de toutes les "preuves" avancées.

Cependant, si retrouver tous les sous-graphes est un objectif intéressant, et dans la mesure où on sait que ça veut dire quelquechose, il y a des solutions pour retrouver tous ceux d'un jeu d'essai ... Si on en connait le nombre exact , qu'il faut retrouver dans les dernières communications , il y a moyen d'être exhaustif. Il faut toujours être optimiste ...

[Dlzlogic]

@ JohnArto,
Votre algorithme traite 95 numéros ou 95 zones géographiques définies par leur périmètre ?
Cette description d'"algorithme" me fait pense à une autre réponse.

[invitec0f983f7]

Bonjour

Oui, en gros c'est ça.
Mais il apparait que la phase préparatoire, qui n'est pas un prétraitement, c'est à dire recherche des points particuliers et création de la triangulation est la plus longue. Cette étape doit être faite forcément, d'une façon ou d'une autre. Le reste est linéaire, et, sauf si on doit recommencer, très rapide.

Alors je ne vois pas l'intérêt de faire ces décompositions en triangles : elle est la plus longue, elle augmente le nombre de cellules à colorier (vous obtenez combien de triangles décomposant les départements ?), elle complique la règle de coloriage (certains triangles doivent être de la même couleur que leur voisin, ou au contraire de couleur différente, suivant les cas).

C'est peut-être un intérêt graphique ?

[invitec0f983f7]

Votre algorithme traite 95 numéros ou 95 zones géographiques définies par leur périmètre ?

L'algorithme colorie un graphe dont les 95 sommets sont les (préfectures des) départements, et dont les arrêtes sont les liaisons avec les (préfectures des) départements voisins.
(94 en fait, car il n'y a pas de département n°20)

Pourquoi cette question ?

[invitec0f983f7]

Une difficulté supplémentaire est de considérer l'extérieur des départements de métropole comme un énorme département supplémentaire, ayant une quarantaine de voisins (= tous les départements frontaliers ou en bord de mer).
C'est comme si on voulait aussi colorier le fond de carte.

[Médiat]

Bonjour

1- j'identifie tous les points caractéristiques, c'est à dire les "points communs" à 3 zones.
2- à l'aide de ces points je crée une triangulation (cf Delaunay).
3- éventuellement certains côté (diagonales) doivent être échangés.
4- chaque zone est maintenant constituée de triangles. C'est à dire que tous les triangles de cette zone ont la même couleur.
5- point très important et qui justifie la méthode, un triangle ne peut avoir que 3 voisins. Comme la couleur de ce triangle est fixée, ainsi que le voisin qui l'a colorié, il reste au maximum 2 couleurs possibles.

Je vois bien l'intérêt de faire ainsi pour déterminer les relations d'adjacence, mais je ne vois pas ce que cela amène pour le théorème des 4 couleurs, ce que vous proposez ressemble beaucoup à de la "force brute" (si on aboutit pas , on recommence depuis le début)

[Dlzlogic]

Bonjour,
Je veux bien détailler et expliquer tout ce qu'on veux, mais si a priori on me dit "c'est pas bon" ou "c'est plus compliqué", alors on arrivera à rien.
J'en conclue que le sujet ne vous a pas intéressé. Désolé.

[Médiat]

J'en conclue que le sujet ne vous a pas intéressé.

Vous pouvez aussi essayer d'expliquer en quoi votre technique apporte quelque chose ...

[invitec0f983f7]

mais si a priori on me dit "c'est pas bon" ou "c'est plus compliqué", alors on arrivera à rien.

Un peu comme vous quand vous refusez les algorithmes sur les graphes, non ?
Personnellement, je ne vois pas en quoi passer de 95 départements à 400 triangles améliore la situation. Merci de vous expliquer.

J'en conclue que le sujet ne vous a pas intéressé. Désolé.

Raisonnement absurde...

[Dlzlogic]

L'un des intérêts principaux de l'utilisation des triangles est que le traitement est linéaire, c'est à dire "on traite le suivant" et il n'y en a qu'un, puisqu'un triangle n'a que 3 voisins. Alors qu'une zone a un nombre variable de voisins.
Concernant la différence entre "retour en arrière" et "recommencer par qu'on est dans un cul-de-sac". L'opération REA fait partie intégrant de l'algorithme, en ce sens qu'il n'y a aucune raison que le coloriage se fasse du premier coup. Dans la méthode avec les triangles, l'arrivée dans un cul-de-sac est un manque de chance rare. C'est à dire que cette attribution de couleur est quasi systématique.

D'abord, cette application date de plusieurs années et je n'ai pas eu à y remettre le nez, donc j'ai un peu oublié. Il y a quelques étapes que je n'ai pas précisées, par exemple pour une zone qui a plus de 5 voisins il y a au moins 1 triangle intérieur inutile. Il faut le supprimer, non pour des problèmes de place, mais parce qu'il ne signifie rien.
Si ça intéresse quelqu'un, je veux bien rédiger en détail l'algorithme et l'argumentaire.

[Médiat]

L'un des intérêts principaux de l'utilisation des triangles est que le traitement est linéaire, c'est à dire "on traite le suivant" et il n'y en a qu'un, puisqu'un triangle n'a que 3 voisins.

En tout état de cause ce serait linéaire par rapport au nombre de triangles et non au nombre de zones, de plus, un triangle a 3 voisins, si on vient d'en traiter 1, il en reste 2 et non 1, donc ce n'est pas linéaire selon le nombre de triangles non plus.
Si vous ne voulez pas expliciter votre algorithme, ne vous étonnez pas qu'il n'intéresse personne !

[Dlzlogic]

Ceci est vrai.
Donc il en reste 2. Il reste aussi 2 couleurs disponibles. Ce qui représente effectivement 2 solutions. Mais en quoi sont-elle différentes puisque ces 2 triangles à colorier ne sont, à ce point de la ligne de traitement, liés à rien.
Par contre, si l'un des deux a déjà des voisins coloriés, alors il n'y a qu'une seule possibilité.
Donc, dans tous les cas, c'est linéaire.

[Médiat]

Donc il en reste 2. Il reste aussi 2 couleurs disponibles. Ce qui représente effectivement 2 solutions. Mais en quoi sont-elle différentes puisque ces 2 triangles à colorier ne sont, à ce point de la ligne de traitement, liés à rien.

Et pourtant, si un choix échoue, il faut souhaiter que l'essai suivant prendra l'autre solution !

Donc, dans tous les cas, c'est linéaire.

Comment pouvez-vous affirmer qu'un algorithme qui repart à 0 en cas d'échec (dont vous n'avez pas donné une borne sup) est linéaire ?

[Dlzlogic]

Si "on échoue", c'est qu'on est tombé dans un "cul-de-sac". Pas question d'espérer quoi que ce soit de la part de la machine en matière de raisonnement.
Donc, si on recommence, on partira naturellement d'un autre point de départ.
Je dis que c'est linéaire, parce qu'il n'y a aucun retour en arrière, sauf échec rare dont on a parlé.
Tout ceci étant dit, si mon algorithme ne fonctionnait pas, je suppose que je m'en serais aperçu. Quand on veut colorier les régions de l'Europe, je vous assure qu'un peut craindre le pire. Je me souviens aussi d'un coloriage de l'Angleterre, c'était pas mal. Les fichier de base étant venu d'autres gens, je n'avais, a priori, aucune certitude de leur qualité.

[Médiat]

Je dis que c'est linéaire, parce qu'il n'y a aucun retour en arrière, sauf échec rare dont on a parlé.

Quelle est la borne sup du nombre d'échec en fonction de n (et un algorithme qui marche pour 95 départements avec "quelques rares "échecs", présentent-ils aussi "quelques rares "échecs" avec 1 000 000 de zones ou 1 000 000 000 ou plus ?), et à moins que la borne sup ne soit une constante (ne dépendant pas de n), ce n'est pas linéaire !

[leon1789]

Si "on échoue", c'est qu'on est tombé dans un "cul-de-sac". Pas question d'espérer quoi que ce soit de la part de la machine en matière de raisonnement.

Pourtant la machine est capable de faire de la récursivité et dégager une piste favorable par une succession d'échecs.
Je ne dis pas que c'est la meilleure chose à faire, c'est de la force brute.

Donc, si on recommence, on partira naturellement d'un autre point de départ.

par exemple en repartant du point qui a posé souci : c'est ce que j'ai proposé dans l'algo du message 64 (tout en gardant prêt de la main les points qui déjà posé souci).

[Dlzlogic]

Dans la pratique, ce type de représentation à 4 couleurs n'est pas vraiment intéressant pour un grand nombre de zones. A titre d'exemple, la nouvelle carte de France administrative colorie les 13 régions avec quatre couleurs. Faisable à la main. Ensuite, les départements de chaque région sont coloriés avec les couleur de la région en faisant varier la teinte (4 teintes). cela est encore faisable à la main.
Concernant les "échecs" je n'en ai pas observés plus de 3 sur un ensemble de zones. En fait, ce cas d'échec correspond à une configuration assez particulière qui relève d'un manque de chance.
L'utilisation de triangles dans de nombreuses application est intéressante et il souvent efficace de remplacer une zone par un ensemble de triangles.

[Médiat]

c'est ce que j'ai proposé dans l'algo du message 64 (tout en gardant prêt de la main les points qui déjà posé souci).

Vous venez d'avouer avoir créé un double pseudo (ce qui est interdit par la charte que vous avez signée) afin de contourner une décision de modération.

L'ensemble de la modération a été prévenue !

Médiat, pour la modération

[Médiat]

Dans la pratique, ce type de représentation à 4 couleurs n'est pas vraiment intéressant pour un grand nombre de zones. A titre d'exemple, la nouvelle carte de France administrative colorie les 13 régions avec quatre couleurs. Faisable à la main. Ensuite, les départements de chaque région sont coloriés avec les couleur de la région en faisant varier la teinte (4 teintes). cela est encore faisable à la main.
Concernant les "échecs" je n'en ai pas observés plus de 3 sur un ensemble de zones. En fait, ce cas d'échec correspond à une configuration assez particulière qui relève d'un manque de chance.
L'utilisation de triangles dans de nombreuses application est intéressante et il souvent efficace de remplacer une zone par un ensemble de triangles.

Alors tout cela n'a rien à voir avec les mathématiques, où la notion de "manque de chance" n'intervient pas, on lui préfère la notion de démonstration

[feanorel]

Bonjour,
Je veux bien détailler et expliquer tout ce qu'on veux, mais si a priori on me dit "c'est pas bon" ou "c'est plus compliqué", alors on arrivera à rien.
J'en conclue que le sujet ne vous a pas intéressé. Désolé.

Un classique...
Le sujet a intéressé pas mal d'intervenant, certains ont appris l'existence d'algo exact ou heuristiques, de bornes de complexité
(je ne savais pas qu'il existait un algor quadratique pour les 4 couleurs par exemple).

Si je puis me permettre ta solution n'en est effectivement pas une au sens mathémtatique (contrairement à celles proposées par d'autres intervenant) :
- que faire si une des zones à un côté courbe par exemple ? Alors ta triangulation ne recouvre pas exactement la zone. Et du coup il n'y a pas bijection entre les zones et les triangles...
- en quoi faire la triangulation n'est pas un prétraitement ?
- l'algo proposé est (en admettant que la décomposition en triangle est possible) une heuristique qui n'est pas garantie de fonctionner, et qui est linéaire en le nombre de triangles (supérieur au nombre de zone) * le nombre d'essai nécessaire (complètement inconnu).

Bref, moi j'ai appris des choses dans les discussion, d'autres aussi j'espère, as-tu appris quelque chose ?

[Dlzlogic]

Bonjour Feanorel,
Je répondrai juste sur un point de détail, les triangles sont formés à partir des points caractéristiques, c'est à dire des points qui apparaissent dans 3 contours de zone ( = dans le contour de 3 zones). Tous les points qui ne sont pas des points caractéristiques sont ignorés. Autrement dit que le tronçon entre 2 points soit un segment une ligne brisée, un arc de cercle ou de parabole ou n'importe quoi, cela n'a aucune importance.

[minushabens]

S'il n'y a pas de points appartenant à quatre frontière ou plus, le graphe sous-jacent à la carte est un graphe cubique, et le graphe dual une triangulation. Dans ce cas on a une cns pour que la carte soit 3-colorable: il faut et il suffit que le degré de chaque sommet du graphe dual soit pair (c'est-à-dire que chaque cellule de la carte soit entourée par un nombre pair de cellules).

[Dlzlogic]

Bonsoir Minushabens,
Par définition, dans l'énoncé du théorème des quatre couleurs les zones sont limitrophes par une ligne et non seulement un point. Donc, le cas de point caractéristique appartenant à plus de trois zones est un cas particulier qu'il me parait indispensable de traiter de façon particulières.
Ceci dit, j'ai un peu de mal à comprendre ton dernier message. On a déjà du mal à démontrer et à dessiner un ensemble de zones avec quatre couleurs, je n'arrive pas à comprendre que tu parles de n'utiliser que trois couleurs. J'imagine bien que dans certains cas ce soit possible (j'ai lu les articles), mai cela me parait un cas assez particulier.

[invitebd98b571]

Bonjour Feanorel,
Je répondrai juste sur un point de détail, les triangles sont formés à partir des points caractéristiques, c'est à dire des points qui apparaissent dans 3 contours de zone ( = dans le contour de 3 zones). Tous les points qui ne sont pas des points caractéristiques sont ignorés. Autrement dit que le tronçon entre 2 points soit un segment une ligne brisée, un arc de cercle ou de parabole ou n'importe quoi, cela n'a aucune importance.

Bonjour Dlzlogic,
Une question simple vient à l'esprit : vous recherchez les points qui apparaissent dans les contours de 3 zones, afin de construire ensuite votre triangulation.
Mais que ce passe-t-il si une zone A est totalement incluse dans une autre zone B ? Schématiquement, un cercle A entouré d'une couronne B. Dans ce cas les points du contours de A n'appartiennent qu'à deux contours, ceux de A et B. Par exemple, en Italie, Saint Marin et le Vatican sont dans ce cas de figure.

[Médiat]

Bonjour,

Mais que ce passe-t-il si une zone A est totalement incluse dans une autre zone B ?

Votre remarque est tout à fait pertinente, néanmoins ce cas ne pose pas de problème de coloriage.

[minushabens]

Ceci dit, j'ai un peu de mal à comprendre ton dernier message. On a déjà du mal à démontrer et à dessiner un ensemble de zones avec quatre couleurs, je n'arrive pas à comprendre que tu parles de n'utiliser que trois couleurs.

il y a même des cartes qu'on peut colorier avec deux couleurs. Un damier par exemple.

pour deux couleurs aussi on a une cns: un graphe est coloriable avec deux couleurs si et seulement si il ne contient pas de circuit impair.