Théorème des quatre couleurs

[minushabens]

Les précédents posts m'amènent à me poser la question suivante: pour valider et évaluer un programme de coloriage, j'aurais besoin de créer des cartes aléatoires (ou des graphes planaires aléatoires). Es-ce qu'on sait faire ça? Du point de vue des cartes, je pense qu'on pourrait tirer au hasard un certain nombre de grands cercles sur la sphère, qui seraient les frontières. C'est facile puisque deux angles définissent un grand cercle, par contre, si je veux une carte avec un nombre préspécifié de cellules, combien de grands cercles est-ce que je dois tirer? Ca n'est pas clair pour moi. Du côté des graphes planaires, c'est encore moins évident (pour moi, qui n'y connais pas grand-chose). Engendrer un graphe aléatoire en tirant au hasard des arêtes entre un nombre préspécifié de sommets est aisé, mais on a peu de chances d'obtenir un graphe planaire de cette façon.
-----

[Dlzlogic]

Bonjour,
Oui, j'aime bien les triangles.
Pour créer des zones de façon aléatoire, ou pourrait essayer de procéder de la façon suivante :
1- Création de points XY aléatoires
2- création de triangles avec l'hypothèse de Delaunay
3- facultatif : échanger des diagonales
4- regrouper des triangles ayant un côté commun pour créer une zone.
5- enfin regrouper tous ces triangles en une seule zone.
On est assuré de n'avoir ni trou, ni recouvrement, donc un graphe planaire.

[invitebd98b571]

Bonjour Dlzlogic,
pardon d'insister, mais que donne votre méthode à base de triangles sur le problème des 4 couleurs lorsqu'on ajoute à la liste que vous avez donnée la grande zone tout autour des 100 autres zones ? on se retrouve alors avec 101 zones.

[Dlzlogic]

Bof, vous avez créé une grande zone avec 100 enclaves, c'est à dire que la zone N° 101 comporte un gros trou et des petits trous. Ce n'est pas vraiment les hypothèses du théorème des 4 couleurs.
Pour tout vous dire, j'ai essayé de créer une zone "mer", c'est à dire à l'exclusion de tous les départements, mais j'ai pas attendu la fin.
Le problème du traitement de zone est un problème difficile.
Si vous avez réussi à définir une zone correspondant à l'étendue maritime, ça m'intéresse.
J'ai remarque que la couleur est précisée par un petit carré. Comment est défini la position de ce petit carré ?
Bien-sûr, je pourrais définir un critère, par exemple, tout segment qui est la limite entre "zone définie" et "rien" est la mer, donc "rien" doit être colorié en bleu. Ce serait une hypothèse supplémentaire un peu subjective.

[invitebd98b571]

Bof, vous avez créé une grande zone avec 100 enclaves, c'est à dire que la zone N° 101 comporte un gros trou et des petits trous. Ce n'est pas vraiment les hypothèses du théorème des 4 couleurs.

Je n'ai pas compris votre argumentation, mais la grande zone est connexe (mathématiquement parlant) donc elle ne met pas en défaut les hypothèses du théorème des 4 couleurs.

Pour tout vous dire, j'ai essayé de créer une zone "mer", c'est à dire à l'exclusion de tous les départements, mais j'ai pas attendu la fin.
Le problème du traitement de zone est un problème difficile.
Si vous avez réussi à définir une zone correspondant à l'étendue maritime, ça m'intéresse.

Voulez-vous que je vous donne les points formant la frontière de cette grande zone (c'est un bon exercice d'algorithmique) ?
*** Serveur externe ***

J'ai remarque que la couleur est précisée par un petit carré. Comment est défini la position de ce petit carré ?

Pour aller au plus vite dans la programmation, j'ai choisi le barycentre des points de la frontière.

[invitebd98b571]

Voulez-vous que je vous donne les points formant la frontière de cette grande zone (c'est un bon exercice d'algorithmique) ?

[invitebd98b571]

Dlzlogic, ce serait dommage qu'on ne voit pas ce que produit votre algorithme.