Coloriage graphe
Réponses
-
dlzlogic écrivait:
> 4- concernant les zones, dans mon langage, le périmètre est une ligne fermée qui définit 2 espaces, l'un intérieur, l'autre extérieur.
ok, en dimension 2, disons que cela ressemble fort à ce que l'on nomme connexité en mathématique.
5- tu parles des enclaves. Ca n'a rien à voir avec le théorème dont on parle.
Et ben justement si, c'est en plein sujet, puisque ces enclaves montrent que les hypothèses du théorème des couleurs ne sont pas vérifiées dans le cadre d'un coloriage de la carte de la métropole. Je me tue à te le répéter...
Par contre il est vrai que c'est un cas dont il faut tenir compte. Il faut une astuce, mais rien à voir avec le théorème.
Là, je suis d'accord, et c'est pourquoi colorier les départements de la métropole ne rentre pas dans le cadre du théorème des 4 couleurs.
Par ailleurs, je ne sais pas si on peut parler d'astuce (je ne pense pas qu'un algo comme celui-ci soit astucieux). Je dirais plutôt que c'est un coup de chance due à une situation géographique favorable. Si on veut éliminer ce coup de chance, on peut fabriquer une carte de France bis (avec un Vaucluse bis), que tu ne pourras pas colorier avec 4 couleurs.
> 6- le seul but poursuivi est "colorier des zones avec seulement 4 couleurs, de façon que 2 zones
> ayant une limite commune aient des couleurs différentes".
> La lecture de la doc précise qu'on peut le faire.
De quelle doc parles-tu ??
> 7- Alors, si j'utilise plus de 4 couleurs, je suis un menteur. Sinon, tu dois me présenter des excuses.
As-tu lu ce que j'ai écrit ? << Cela me suffit pour dire que ton algo existe et qu'il est capable de donner un résultat correct si les circonstances sont favorables. >> Tu crois que tu as fait mieux que cela avec ton algo ?? Tu n'as fait que constater qu'il donnait une réponse valide (ok, le résultat est valide), croyant que c'est l'effet attendu du théorème des 4 couleurs (et là, tu te trompes). -
dlzlogic écrivait:
> Mais, je me répète, théorie ou théorème, ça m'est égal, la seule chose dont je parle est le
> dessin de zones adjacentes avec seulement 4 couleurs. Comment on fait ?
Ben tout le monde peut faire un algo naif qui donnera un résultat valide (comme celui que j'ai rapidement programmé).
Mais quel est l'intérêt d'avancer dans le noir et toucher la cible par chance ? -
Bon, là je suis en admiration.
Pour info, conformément à ce qu'a expliqué Soland, il n'y a aucune raison que ça marche du premier coup. C'est à dire "toucher la cible par chance". D'ailleurs, dans le cas du coloriage des départements, de mémoire, on obtient le résultat au troisième essai.
C'est la logique de l'algorithme qui me parait intéressante.
Par contre apparemment ce qui vous intéresse toi et H, c'est de montrer que j'ai tort.
Ciao. -
dlzlogic écrivait:
> il n'y a aucune raison que ça marche du premier coup. C'est à dire "toucher la cible par chance".
Par "toucher la cible", j'entendais "trouver une solution", et pas nécessairement au premier coup.
D'ailleurs, dans le cas du coloriage des départements, de mémoire, on obtient le résultat au troisième essai.
C'est la logique de l'algorithme qui me parait intéressante.
Ok quelques essais. Comme je te l'avais demandé dans l'autre discussion, cette logique d'algorithme (comme tu dis), ne serait-ce pas une mise en place d'un backtracking (bien connu) ? ou au contraire, il y a-t-il une technique plus profonde ?
Par contre apparemment ce qui vous intéresse toi et H, c'est de montrer que j'ai tort.
Tort sur quoi ? -
Bonjour,
Je viens d'apprendre un nouveau mot "backtracking".
C'est pas comme ça que j'ai fait. De mémoire, je commence par une zone, si ça marche pas, je recommence en commençant par la suivante. En effet, dans le calcul il n'y a aucun choix, puisque a tout instant un triangle défini un zonage pour 4[couleurs]. Comme on colorie de proche en proche, soit ça marche, et on continue, soit ça marche pas et on recommence avec une autre zone de départ.
Tu devrais tout de même prendre 5 minutes pour lire la description de l'algorithme.
J'aime bien ton expression, oui il y a une "technique plus profonde", mais je n'aurais jamais osé le dire moi-même.
Il ne faut pas non plus oublier que la base de l'information est constituée d'une liste de périmètres (ou contours) de zones, qui sont des lignes brisées fermées définies par leurs sommets. (laissons de côté les enclaves). Si la base de l'information est une liste déjà faite, c'est à mon avis un autre problème.
Tort tout simplement. Tort d'exister (conseils répétés de H de consulter un psy) tort d'écrire, tort de ne pas admettre sans réagir les bêtises que je lis. etc. Il suffit de constater que les arguments donnés (par H et toi) ne sont pas des preuves (et pour cause) mais des choses du genre "tu dis n'importe quoi", "c'est plus subtile que ça", "répond à ma question" et j'en passe.Léon a écrit:Tort sur quoi ? -
dlzlogic éécrivait:
> Je viens d'apprendre un nouveau mot "backtracking".
Ce n'est pas faute de t'en avoir déjà parlé. Mais mieux vaut tard que jamais ;-)
> C'est pas comme ça que j'ai fait. De mémoire, je commence par une zone, si ça marche pas, je
> recommence en commençant par la suivante. En effet, dans le calcul il n'y a aucun choix,
> puisque a tout instant un triangle défini un zonage pour 4[couleurs]. Comme on colorie de
> proche en proche, soit ça marche, et on continue, soit ça marche pas et on recommence avec une
> autre zone de départ.
Ok.
Ce "soit on continue, soit on recommence" ressemble quand même pas mal à du backtraking sur les zones.
Tort tout simplement. Tort d'exister, tort d'écrire, tort de ne pas admettre sans réagir les bêtises que je lis.
Oh, pauv' choux... :-(
Vu cette réponse, j'en conclus que tu ne sais pas sur quoi précisément tu as soit-disant tort, mais que cela te plait de jouer la victime. -
Léon a écrit:Ce "soit on continue, soit on recommence" ressemble quand même pas mal à du backtraking sur les zones.
C'est vrai, j'ai aussi des problèmes de compréhension.Wikipédia a écrit:Le retour sur trace (appelé aussi backtracking en anglais) est un algorithme qui consiste à revenir légèrement en arrière sur des décisions prises afin de sortir d'un blocage.
Si la définition de Wiki est bonne, alors justement je ne fais pas de backtracking, pour la bonne raison que une fois le calcul démarré à partir d'une zone, il n'y a aucun choix : un triangle n'a que 3 côtés.
T'as rien d'autre à dire sur l'algorithme ? -
Merci de rappeler qu'un triangle à 3 coté, et pas davantage : ça aide vraiment à la compréhension.
Ok, une fois le calcul démarré à partir d'une zone, il n'y a plus de retour en arrière dans ton algorithme. Des questions, j'en ai aux moins deux :
-- Comment choisis-tu la zone initiale ?
-- Comment justifies-tu qu'il n'y aura pas d'obstruction dans le déroulement de ton algo ? -
Réponse rapide.
La première zone est la première de la liste.
L'ordre des zones est ce qu'il est, c'est à dire qu'il ne dépend de rien de particulier.
En fait, je crois que je commence par le premier triangle, et là c'est vraiment comme ça tombe.
S'il y a "obstruction", on recommence avec le deuxième zone. Le théorème des 4 couleurs dit que la solution existe toujours.
Dans ce que j'ai écrit, mais il faudrait que je le relise, je ne m'intéresse qu'au coloriage lui-même. Le retour au départ avec la zone suivante n'est vraiment pas le plus important. -
dlzlogic écrivait:
> La première zone est la première de la liste. L'ordre des zones est ce qu'il est, c'est à dire
> qu'il ne dépend de rien de particulier. En fait, je crois que je commence par le premier
> triangle, et là c'est vraiment comme ça tombe. S'il y a "obstruction", on recommence avec le deuxième zone.
Ok tu colories la première zone, première zone prise un peu au hasard, en fonction de l'ordre...
Pourquoi il y aurait-il obstruction dès le premier triangle ? Pour l'instant, il y a trop peu de contraintes. En général, c'est plutôt après que les obstructions arrivent, non ?
> Le théorème des 4 couleurs dit que la solution existe toujours.
Hum... je ne vois pas pourquoi le théorème des 4 couleurs justifie qu'il y aura nécessairement une solution suite au début de coloriage que tu as commencé ?
> Dans ce que j'ai écrit, mais il faudrait que je le relise, je ne m'intéresse qu'au coloriage lui-même.
Le coloriage lui-même : tu t'intéresses à la manière dont les pixels d'une couleur fixée vont remplir la zone ?! -
J'ai recopié ma description, juste pour mémoire. (j'ai peut-être rajouté un ou deux mots et corrigé des fautes d'orthographe)Les départements sont définis par des lignes fermées. Les tronçons communs permettent de créer des chemins, un chemin est une ligne brisée comportant une origine et une extrémité. Un chemin n'a aucun point commun avec un autre sauf les extrémités qu'on peut appeler noeuds ou sommets.
Les extrémités de ces chemins sont les points permettent de définir une
triangulation de Delaunay
La triangulation de Delaunay génère des triangles accolées tels qu'il n'y a aucun trou et aucun recouvrement.
Rien ne prouve que les côtés des triangles correspondent toujours à des limites de zone, dont il y a une phase de changement de diagonale.
On remplace les côtés de triangle par la diagonale du quadrilatère correspondant si celle-ci est un côté de polygone.
A cette étape on est sûr que la zone définissant un département est remplacée par un ensemble de triangles accolés et appartenant au même département.
A chaque triangle on attribue une couleurs (de 1 à 4) telle qu'un côté de triangle est une séparation de couleur
Pour chaque polygone, on attribue une couleur.
Les couleurs des triangles contenus dans le polygone seront modifiées et les triangles voisins seront modifiés de la même façon, pour respecter la différenciation des couleurs entre 2 triangles voisins.
Les triangles contenus dans un polygone et n'ayant pas de côté communs avec un autre polygone sont supprimés.
La suite est surtout du traitement informatique.
L'idée est que l'on a des zones, les limites sont des chemins et les extrémités sont des sommets de triangles. Tous les triangles correspondant à une même zone ont la même couleur, ceci est possible, puisqu'ils n'ont aucun côté en commun avec un triangle appartenant à un autre polygone.
Le changement de couleur d'un triangle implique le changement de couleur de tous les triangles de la même zone.
Il est très possible que on arrive à un cas d'impossibilité, alors, on recommence à l'étape où on a fait un choix aléatoire de couleur. Soit un triangle quelconque, il a 3 côtés donc 3 triangles accolés, donc 4 couleurs en tout.
Il est bien évident que ça ne peut coincer que vers la fin, c'est à dire, en gros, quand on se referme ou qu'on a un trou à boucher.
Cette partie strictement informatique est faire uniquement avec les triangles qui sont organisés en liste chainée, avec la référence au polygone déduit de la zone qui l'a créé. Cette partie de traitement est très rapide.
Quand je parle de "coloriage", ça veut dire que j'attribue à chaque triangle un numéro de couleur, de 1 à 4, tel que 2 triangles accolés par un côté ont des couleurs différentes et que tous les triangles issus d'un polygone ont la même couleur. Il me semble que c'est la stricte définition du théorème des 4 couleurs.
Remplir une zone avec une certaine couleur, c'est du graphisme, rien à voir avec ce dont on parle.
Lorsque je commence, je prends le premier triangle, je lui donne une couleur et je donne une couleur à chacun des 3 triangle qui l'entourent.
Puis je m'intéresse à ces 3 triangles. Il a une couleur et au moins un voisin. Il me reste 2 couleurs possibles, au maximum.
Puis je continue de proche en proche, jusqu'au bout, sauf si ça coince.
En ce cas je recommence, soit en partant du second triangle de la liste, soit d'un point où j'ai fait un choix. Tout ça n'est pas très difficile, c'est juste de la gestion de liste chainée.
Il fait que je précise que la partie de traitement la plus longue est la définition des chemins. Ce problème, je l'avais réglé depuis longtemps, je me suis servi de mes fonctions. -
Il est très possible que on arrive à un cas d'impossibilité, alors, on recommence à l'étape où on a fait un choix aléatoire de couleur. Soit un triangle quelconque, il a 3 côtés donc 3 triangles accolés, donc 4 couleurs en tout.
(...)
Puis je continue de proche en proche, jusqu'au bout, sauf si ça coince.
En ce cas je recommence, soit en partant du second triangle de la liste, soit d'un point où j'ai fait un choix.
Si ce n'est pas du backtraking... J'ai du mal à comprendre.
Prenons un exemple très simple où la triangulation de Delaunay est déjà dessinée :
La carte à colorier est formée de zones bornées par les lignes en pointillés. La triangulation de Delaunay est en trait plein.
Que fais-tu après cela ? -
Non, c'est pas ça du tout.
Les traits en pointillé sur ta figure est le dessin du maillage de Voronoï.
Ces deux figures géométriques se correspondent effectivement (par une correspondance géométrique rigoureuse).
Dans la méthode que j'utilise, je calcule un maillage triangulaire. La méthode de Delaunay est très efficace pour faire cela.
Mais ce maillage n'est que provisoire, puisque TOUS les côtés de triangles doivent correspondre à des segments qui joignent les extrémités de chemins. En fait, pour être plus rigoureux, AUCUN côté de triangle ne doit couper un tel segment.
En d'autres termes, j'utilise la méthode de Delaunay pour générer des triangles, mais ce n'est qu'une étape provisoire.
Si tu veux faire un dessin, et c'est une très bonne idée, sers-toi seulement de la triangulation et oublie le maillage. -
Ok, le dessin ci-dessus n'est pas bon, je n'ai pas fait attention à tes explications.
Comme tu dis, prenons donc directement une triangulation de Delaunay qu'il faut colorier :
Il faut maintenant colorier chaque triangle avec 4 couleurs maxi. Comment commences-tu ? -
Bon, très nettement, tu cherches à montrer que je dis n'importe quoi.
J'ai parlé de Delaunay, uniquement parce que c'est une méthode efficace pour dégrossir le problème.
Si tu n'essaye pas de comprendre la méthode que j'ai expliquée il est fort peu probable que tu y arrives.
Je vais tout de même essayer de te répondre. (tout ça de mémoire)
J'ai une structure qui précise un triangle, les adresses des 3 (en général) qui lui sont accolés, le zone dont il provient et la couleur actuellement attribuée. Tous les triangles sont liés par une liste chainée, étant donné l'organisation de la structure.
On peut commencer par n'importe quel triangle, il a 3 triangles voisins etc.
On considère généralement qu'un théorème est valable. Donc j'ai considéré que le théorème des 4 couleurs était vrai. C'est à dire qu'on peut colorier les triangles suivant les condition correspondantes.
Je voudrais bien savoir l'importance que tu attaches au choix du premier triangle.
Admettons qu'il y ait une seule solution. Par permutation on peut commencer par n'importe quel triangle, on aura toujours le même résultat.
J'avoue que tes questions me paraissent tellement basiques que je me demande si tu cherches à ce que je me contredise, ou au moins que je dise une bêtise, ou que tout simplement, tu ne comprends pas le problème posé, et encore moins la solution. -
Ben je te l'ai dit (et je ne suis pas le seul), je ne comprends pas ton algo...
Arrête de parler de liste chaînée : on s'en fout ! Les listes chaînées, c'est de la prog... Et ici, on parle d'algorithme et on essaie de voir comment ton algorithme se déroule.
On considère généralement qu'un théorème est valable. Donc j'ai considéré que le théorème des 4 couleurs était vrai.
(...)
On peut commencer par n'importe quel triangle, il a 3 triangles voisins etc.
Le théorème des 4 couleurs dit qu'il y a une solution sur l'exemple ci-dessus, nous sommes d'accord.
Ok, je fixe une couleur 1 sur le triangle du bas. Ensuite, comment procèdes-tu ?
Il a des voisins au-dessus de lui. On leur donne une couleur chacun, disons 2 et 3, ok ?
Et ensuite ? C'est quoi ton "etc" ? -
Bon, la question que tu poses, c'est la dernière étape, de la gestion informatique pure.
1- on sait qu'un triangle n'a que 3 voisins, donc 4 couleurs en tout.
2- en partant d'un triangle, n'importe lequel, on lui attribue une couleur, ainsi qu'à ses 3 voisins.
3- de proche en proche, on attribue une couleur au(x) voisin(s).
4- le théorème dont il est question dit que c'est possible.
Où est la difficulté ?
Par contre, l'idée de mon algo est de "transformer" les zones en triangles, c'est la partie difficile, et ensuite on leur attribue des couleurs en respectant les conditions
1- tous les triangles issus d'une même zone auront la même couleur
2- deux triangles ayant un côté commun auront des couleurs différentes : 1 parmi 4.
Pour essayer de répondre à ta question, le triangle de départ a 3 voisins (maxi). Cela permet d'attribuer 4 couleurs.
Pour chacun de ces trois triangles, il a au maximum 2 voisins qui n'ont pas encore de couleur : on leur attribue une couleur disponible.
Puis on traite les triangles qui viennent de se voir attribuer une couleur, on procède de la même façon qu'à la ligne précédente.
On effectue cette opération jusqu'à ce qu'on ait attribué une couleur à tous les triangles en respectant les conditions.
S'il te plait évite ce genre de phrase : "(et je ne suis pas le seul)".
Tu sais, je l'ai expliqué à quelqu'un, il est vrai qu'il connaissait les problèmes liés au SIG, il n'a pas posé une seule question, c'est à dire qu'il a compris du premier coup.
Je comptais te faire une copie de la partie du module qui réalise cela, mais c'est tout de même un peu trop long, et c'est vraiment de l'informatique pure (gestion de pointeurs, tests etc.), donc, à moins que tu insistes, je renonce. -
> 1- on sait qu'un triangle n'a que 3 voisins, donc 4 couleurs en tout.
> 2- en partant d'un triangle, n'importe lequel, on lui attribue une couleur, ainsi qu'à ses 3 voisins.
> 3- de proche en proche, on attribue une couleur au(x) voisin(s).
> 4- le théorème dont il est question dit que c'est possible.
> Où est la difficulté ?
Là, en effet, il n'y a aucune difficulté, et l'algorithme sous-jacent est du simple backtracking de base.
> Par contre, l'idée de mon algo est de "transformer" les zones en triangles, c'est la
> partie difficile, et ensuite on leur attribue des couleurs en respectant les conditions
> 1- tous les triangles issus d'une même zone auront la même couleur
> 2- deux triangles ayant un côté commun auront des couleurs différentes : 1 parmi 4.
Là, je comprends bien ce que tu expliques, mais je ne comprends pas ce que vont apporter les triangles. Le fait d'avoir des triangles à traiter va-t'il simplifier la tâche par rapport à des zones (connexes) quelconques ? Surtout qu'en plus, une fois que tu as décomposé les zones en triangles, il faut tenir compte que ces triangles viennent d'une même zone, donc ils ont forcément la même couleur. Cela donne l'impression d'une surcouche de complexité.
> Pour essayer de répondre à ta question, le triangle de départ a 3 voisins (maxi).
> Cela permet d'attribuer 4 couleurs.Pour chacun de ces trois triangles, il a au
> maximum 2 voisins qui n'ont pas encore de couleur : on leur attribue une couleur disponible.
> Puis on traite les triangles qui viennent de se voir attribuer une couleur, on procède de la
> même façon qu'à la ligne précédente.
> On effectue cette opération jusqu'à ce qu'on ait attribué une couleur à tous les triangles en
> respectant les conditions.
Mais ne peut-on pas faire cela avec des zones quelconques (et non triangulaires). Ok, le nombre de voisins d'une zone peut être 1,2,3,4,5, etc. (alors que pour un triangle, c'est 3). Mais cela change quoi ? En effet :
<<
La zone de départ a des voisines, on leur attribue des couleurs (suivant les contraintes).
Pour chacune des voisines, il a encore des voisines qui n'ont pas encore de couleur : on leur attribue une couleur disponible.
Puis on traite les zones qui viennent de se voir attribuer une couleur, on procède de la même façon qu'à la ligne précédente.
On effectue cette opération jusqu'à ce qu'on ait attribué une couleur à toutes les zones en respectant les conditions.
>>
Qu'en penses-tu ? Je ne comprends pas pourquoi tu tiens à passer par une triangulation. -
Oui, je comprends parfaitement tes questions.
L'origine de cet algo est une question sur un forum de SIG.
Un membre voulait pouvoir dessiner des zones avec 4 couleurs (conformément à la théorie qu'il avait lue).
On lui a répondu des choses du genre "te casse pas la tête, dessine avec 5 ou 6 couleurs", bref.
Ce problème m'a intéressé, j'y ai passé le temps nécessaire, c'est vrai que j'ai triché, puisque j'avais largement étudié ces problèmes de zone, et j'ai trouvé une méthode.
Cela n'intéresse personne, seule la démonstration du fameux théorème constitue apparemment un sujet valable.
J'ai bien compris, n'en parlons plus.
En fait pour répondre à ta question : le problème posé est de colorier des zones de façon à ce que deux zones limitrophes aient des couleurs différentes. Comment fais-tu ? Et s'il te plait, ne me répond pas comme H "il y a des algorithmes qui existent" et pas non plus : il suffit de charger un fichier de voisinage de départements (cf topic mis en référence).
En fait, étant donné mes lecture des forum, je crois que la bonne réponse serait "ça ne nous intéresse pas, passons à autre-chose".
Réponse sérieuse.
Dans la pratique, je ne pense pas qu'il soit raisonnable d'imaginer un traitement où on utilise les zones directement.
Par ailleurs, la création de chemins, nécessaire à mon avis pour gérer les zones en tant que polygones, est nécessaire, et c'est la partie la plus coûteuse en temps d'exécution.
J'ai ouvert un topique pour proposer de trouver une autre méthode. Je me suis suis fait envoyer sur les roses.
Bon, pour moi, la question reste ouverte, étant donné les hypothèses de zones définies par leur périmètre, quelle serait une bonne méthode pour dessiner ces zones avec 4 couleurs, de façon que 2 zones limitrophe aient des couleurs différentes. -
dlzlogic écrivait:
> L'origine de cet algo est une question sur un forum de SIG.
Serait-ce là ? http://www.forumsig.org/showthread.php/26663-MapInfo-10-x-Theorie-des-4-couleurs-appliquée-à-une-carte?p=233612&viewfull=1#post233612
Le moindre que l'on puisse dire, c'est qu'il y a effectivement des réactions différentes sur ce forum SIG et sur les forums de maths.
> Comment fais-tu ?
Ben, je te l'ai dit plusieurs fois : méthode naïve de backtracking (car je ne connais pas grand chose en théorie des graphes), c'est-à-dire comme cela (avec quelques optimisations dans les choix des zones),
<<
Choix d'une zone de départ et de sa couleur quelconque.
La zone de départ a des voisines, on leur attribue des couleurs (suivant les contraintes).
Pour chacune des voisines, il a encore des voisines qui n'ont pas encore de couleur : on leur attribue une couleur disponible.
Puis on traite les zones qui viennent de se voir attribuer une couleur, on procède de la même façon qu'à la ligne précédente.
On effectue cette opération jusqu'à ce qu'on ait attribué une couleur à toutes les zones en respectant les conditions.
>>
C'est exactement comme cela que fonctionne les solveurs de suduko les plus simples (sudoku = coloriage de 81 cases avec 9 couleurs, suivant certaines règles de non redondance de couleurs pour des cases "liées", un peu comme ici).
J'aurais pu aussi prendre un algorithme qui colorie d'abord toute la carte avec 5 ou 6 couleurs, puis qui, localement, essaye de diminuer le nombre de couleurs à 4.
Cela n'intéresse personne, seule la démonstration du fameux théorème constitue apparemment un sujet valable.
Simplement faux : démontrer le théorème intéressent les gens, oui, mais ils s'intéressent aussi aux algo de coloriage... Encore faut-il les convaincre, avec de vrais arguments, de l'intérêt de telle ou telle méthode.
Dans la pratique, je ne pense pas qu'il soit raisonnable d'imaginer un traitement où on utilise les zones directement.
Pourquoi ? Mathématiquement, où est le problème ? Ici http://www.les-mathematiques.net/phorum/read.php?8,899260,899604#msg-899604 , j'ai un traitement avec les départements, sans aucune triangulation préliminaire. Je considère de manière abstraite les zones à colorier : les zones se retrouvent être les sommets d'un graphe où les arrêtes désignent le lien de voisinage entre zones sur la carte. Où est le problème dans cette conception ? Merci d'apporter une réponse pour m'éclairer.
Si tu utilises des triangles, c'est pour des raisons pratiques sur machines avec tes logiciels pro ? ou vraiment parce que cela apporte un avantage dans la méthode ? ...en plus, dans chaque zone (connexe) initialement donnée, tu y crées plusieurs triangles, ce qui démultiplie le nombre d'objets à colorier. Cela donne l'impression d'augmenter la complexité. Je me trompe ? -
Bonjour,
Que veux-tu dire par là ?Léon a écrit:Le moindre que l'on puisse dire, c'est qu'il y a effectivement des réactions différentes sur ce forum SIG et sur les forums de maths.
Par ailleurs, je t'admire réellement d'avoir retrouvé l'origine de la demande. J'en suis incapable.
Pour les autres question, je n'ai rien à prouver, rien à justifier.
Avoue que tu n'a répondu à ce topic que pour pouvoir dire "qu'est-ce qu'il a encore écrit comme imbécillité ?".
Si j'ai utilisé les triangles c'est parce que les triangles se manipulent très bien. Je suis presque sûr que ça n'augmente pas la complexité.
Par ailleurs, c'est mon intuition de penser que la gestion avec les polygones serait (plus) difficile.
Ce qui entre en ligne de compte pour la complexité, c'est (un peu) le nombre de zones et beaucoup la finesse de définition des limites (ie le nombre de points).
Une technique qui pourrait être essayée pourrait être de commencer par simplifier les lignes. Mais c'est aussi une opération délicate.
Tu sais j'utilise des triangles pour toute représentation géographique depuis 35 ans. La première publication de cette utilisation est un rapport de fin d'études d'élèves de l'école des Mines de Douai. (1986).Léon a écrit:Si tu utilises des triangles, c'est pour des raisons pratiques sur machines avec tes logiciels pro ?
Par ailleurs, c'est gentil de qualifier mon logiciel de "pro". Ca rachette bien des méchancetés. -
dlzlogic écrivait:
> Pour les autres question, je n'ai rien à prouver, rien à justifier.
Ah visiblement, ce n'est pas ton souci.
C'est peut-être pour cela que tu n'arrives pas à dialoguer avec les matheux, car pour eux, la préoccupation essentielle, c'est de prouver, de justifier.
> Si j'ai utilisé les triangles c'est parce que les triangles se manipulent très bien.
Toi qui voulais parler d'algorithme... Ce serait donc uniquement que pour des raisons de cuisine interne que tu utilises des triangles.
> Je suis presque sûr que ça n'augmente pas la complexité.
Tu obtiens combien de triangles sur les départements français ? 200 , 300, 400 ?
> Par ailleurs, c'est mon intuition de penser que la gestion avec les polygones serait (plus) difficile.
Certes, mais personne n'a dit qu'on devait gérer des polygones.
> Ce qui entre en ligne de compte pour la complexité, c'est (un peu) le nombre de zones et
> beaucoup la finesse de définition des limites (ie le nombre de points).
Mais tu parles de faire du dessin maintenant ?! Finalement, quand je disais pixel plus, c'est pas si loin.
> Une technique qui pourrait être essayée pourrait être de commencer par simplifier les lignes. Mais c'est aussi une opération délicate.
Justement, la triangulation que tu proposes le permets. Le lignes sont remplacées par des segments. Mais je ne vois pas encore cela est utile. -
> Ce qui entre en ligne de compte pour la complexité, c'est (un peu) le nombre de zones et
> beaucoup la finesse de définition des limites (ie le nombre de points).
Mais tu parles de faire du dessin maintenant ?! Finalement, quand je disais pixel plus, c'est pas si loin.
Ce que tu ne sembles pas comprendre, c'est que concernant le dessin, le nombre de points c'est vraiment un détail, alors que quand il s'agit de comparer des lignes là, le nombre de point c'est pas du tout une notion négligeable.
Je voudrais bien savoir où tu veux en venir :
1- occuper ton temps, et comme je réponds aux questions, je suis un membre idéal pour ça
2- trouver un faille dans ce que je dis, je pense que c'est la raison la plus probable
3- le sujet t'intéresse et tu essayes de comprendre, là j'y crois pas vraiment.
A l'évidence, tu n'as pas compris que la PREMIERE opération consiste à rechercher les noeuds, c'est à dire les extrémités de chemins. Je rappelle qu'un chemin est une ligne brisée qui n'a pas d'autre point commun avec un autre chemin que ses extrémités.
> Une technique qui pourrait être essayée pourrait être de commencer par simplifier les lignes. Mais c'est aussi une opération délicate.
Justement, la triangulation que tu proposes le permets. Le lignes sont remplacées par des segments. Mais je ne vois pas encore cela est utile.
Ensuite, à partir de ces noeuds (extrémités de chemins) je crée une triangulation avec la méthode de Delaunay, parce qu'elle est rapide et que le résultat est unique. L'opération qui consiste à reconstruire les zones serait possible aussi, mais j'ai préféré les triangles.
J'avoue que la première ligne de ton message précédent me laisse un peu perplexe. A titre d'exemple, un certain H a absolument voulu me convaincre de quelque chose de faux. Malheureusement il était difficile de trouver des arguments valant preuve. Donc tous mes arguments tombaient à l'eau. Finalement j'ai trouvé un document (un petit programme) sensé prouver la validité de ce dont on parlait. Pendant 2 heures, j'ai cherché la preuve au sens stricte, et finalement j'ai trouvé. Crois-tu que H a compris ? Si tu veux plus de détails sur ces 4 lignes, la seule façon est de me contacter via mon site. Cet exemple a l'avantage d'être d'une grande simplicité. -
Dois-je me laisser insulter par dlzlogic ? Dois-je faire ici un résumé de la discussions privée que nous avons eue pour rétablir la vérité ? Doit-on simplement bannir ce triste individu de tout le forum pour ne plus être importuné ?
-
Dlzlogic,
finalement, ta préoccupation sur la reconnaissance des chemins, de leurs extrémités, faire des petits triangles en multitude, ne sont qu'un préparatif qui n'a que peu d'importance. Quand on parle d'une méthode de coloration de carte, on attend bien autre chose, on attend un algo qui affecte vraiment une coloration à chaque zone. Sur cela, je reste sur ma faim, car tu n'as pas mieux que moi... C'est tout aussi naïf (et avec bien plus de triangles, et de contraintes pour la reconstitution des zones à partir de tes triangles...).
Toi même, tu dis ne pas te préoccuper des preuves et des diverses justifications (c'est tout de même dommage quand on est sur un forum de math),
mais tu n'as pas non plus donné, à mes yeux, d'algorithme intéressant pour l'affectation des couleurs. Toute cette discussion est (encore une fois) vaine...
Quant à tous tes laïus extra-mathématiques, tu devrais te les garder... sinon tu en récolteras les fruits pourris, comme cela a toujours été le cas, sur tous les forums de maths que tu as côtoyés, depuis des années. -
Salut. Après ces discussions je me permets de poser une question sur la conjecture de Hadwiger.
Donc théorème des 4 couleurs démontré, je pense que la conjecture est démontrée et pour n=2 et n=3 trivialement (n dans le post ccnc) et pour n=4, donc 3 couleurs, quelque chose à dire ? (n=5, 4 couleurs ). -
Pour l'état de l'art sur la conjecture de Hadwiger, il suffit de cliquer.
-
Ok merci je voudrais le cas 3 couleurs (n=4)
-
C'est traité explicitement dans le lien. Il suffit de lire (en anglais).
-
Dernière question. Est-ce que l'on peut démontrer que si la conjecture de Hadwiger est vraie pour le rang n, elle est vraie pour le rang n-1 donc pour n-2 etc ?
Merci. -
Ce que je dis est- il équivalent à la conjecture? Donc si on a un résultat faisant intervenir n valeurs si on démontre l' etape n implique n-1 peut on généralement démontrer le cas inverse c'est à dire ce résultat par récurrence je me demande?
-
tomn a écrit:Est-ce que l'on peut démontrer que si la conjecture de Hadwiger est vraie pour le rang n, elle est vraie pour le rang n-1 donc pour n-2 [size=x-large]etc[/size] ?
Mieux vaut éviter les "etc". Il est à peu près évident que Hadwiger(n+1) => Hadwiger(n), mais tu n'iras pas loin avec ça (faire l'exercice de le prouver complètement et rigoureusement te fera peut-être un peu avancer dans la rigueur et la précision si ces choses t'intéressent).
edit: pardon, j'avais mal compris ton "etc" (je ne modifie rien, c'est juste que j'ai eu peur qu'il sous-entende "et tout ce qu'on désire comme autres énoncés" alors qu'il ne sous-entend que "..n-3, etc")Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi -
Il n'y a pas de résultat de réciproque? (Pour une généralisation de récurrence) merci
-
J'avoue que dans d'autre énoncé cette implication n+1 implique n permet de démontrer cet énoncé au moins par récurrence mais ici autre chose (je crois).
Et cette théorie étant nouvelle pour moi telle quelle depuis une semaine les démonstrations rigoureuses prendraient du temps pour moi. -
J'ai dis n'importe quoi sur le dernier post en faite si une propriété n+1 implique n" et que n implique n+1 ça serait une "relation "d'équivalence . Pour revenir a Hadwiger j'ai pensé et trouvé que l'implication n+1 implique n , peut être établi par un algorithme du faite que le graphe est déja colorié on peut par élimination successive arriver au résultat. Enfin je suis intéressé à un énoncé portant sur n entier tel que n implique n+1 et n+1 implique n si il existe? Merci à tous ceux où celles qui me comprennent!
-
Salut de nouveau.
Je me posais la question si un graphe planaire contiendra "au plus" $ K_4$ comme mineur ?
En fait si on arrange un graphe donné sans mineur $K_4$ (en enlevant certains points) alors on serait dans le cas série-parallèle graphe 3-coloriable puis les points qu'on a enlevé retournent avec la 4 ème couleur et fini.
Si quelqu'un m'a relevé ma faute je vous remercie. -
J'ai su ma faute
![[Utilisateur supprimé]](https://w8.vanillicon.com/844673ca676c886b85d26c0b5ef6d73b_100.png)
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
In this Discussion
Qui est en ligne 30
+27 Invités