Discussion :

[Schpountz42]

Bonjour,
Je recherche plusieurs algorithmes pour la coloration d'un graphe non orienté pour une application qui est censée appliquer la conjecture des 4 couleurs:
http://fr.wikipedia.org/wiki/Théorèm...uatre_couleurs

Pour résumer le problème, tous les sommets doivent être colorés de tel façon que 2 sommets voisins n'aient pas la même couleur.

Dans cette application, il est déjà prevu d'implanter l'algorithme du BackTracking (résolution par rebroussement). je recherche donc d'autre algo^^

merci d'avance.

PS: j'ai bien fait des recherches sur internet et la FAQ avant mais je ne trouve pas d'algo juste des définitions ou vocabulaire sur les graphes.

[Graffito]

Bonjour,

Une technique pour trouver une solution assez bonne dès le départ, consiste à affecter à chaque sommet un coefficient de "difficulté" qui tient compte du nombre de points adjacents, puis du nombre d'adjacence des adjacents, et ainsi de suite. Puis, on trie les sommets par coeff de difficulté décroissant avant d'esayer de leur trouver une couleur. Ainsi, on devrait arriver à une solution quasi correcte.

Pour le calcul du coeff, on peut procéder ainsi :

• on détermine le nombre maxi N_Max_Adj de sommets adjacents à un sommet sur l'ensemble du graphe.
• On l'initialise à 1 les coeff de chaque sommet,
• On itère le calcul sur N étapes (N à determiner en fonction de la précision du coeff et de NmaxAdj) qui consiste à faire :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
        NouveauCoeff(i) = AncienCoeff(i) +
                somme_pour_tous_les_j_adjacents(AncienCoeff(j)) /
                     ((N_Max_Adj+1) <puissance> N°_d'étape)

[Schpountz42]

j'aime bien cet algo mais c'est pas un peu lourd? La complexité doit pas etre magnifique.
De plus ca garantie de trouver une solution? ou juste une grande probabilité de trouver une bonne solution?

[millie]

Pour info, la conjecture n'est plus une conjecture mais un théorème et ne fonctionne qu'avec des graphes planaires

[Schpountz42]

non c'est bien une conjecture car il n'a jamais vraiment été démontré correctement. Sauf erreur la seul "démonstration" a été une démonstration informatique en générant un nombre astronomique de cas. Ce qui n'est pas super rigoureux

[millie]

Ca a tout de même étant prouvé formellement par des systèmes de preuves formelles (même si la preuve est vraiment dégueulasse, je te l'accorde ^^) (désolé d'avoir fait un HS)

[droggo]

Jai,

non c'est bien une conjecture car il n'a jamais vraiment été démontré correctement. Sauf erreur la seul "démonstration" a été une démonstration informatique en générant un nombre astronomique de cas. Ce qui n'est pas super rigoureux

La preuve a été acceptée par la communauté des mathématiciens, c'est donc bien un théorème, quoi que tu puisses en penser.

[Obsidian]

Sauf erreur la seul "démonstration" a été une démonstration informatique en générant un nombre astronomique de cas. Ce qui n'est pas super rigoureux

Je ne me suis jamais penché réellement dans la théorie, je n'en sais donc que ce que l'on en dit sur les articles de vulgarisation, mais il me semble que, d'une part, le problème avait été ramené à 1478 cas critiques, ce qui n'a rien d'astronomique et que, d'autre part, les ordinateurs ont été utilisés pour vérifier ces cas, soit faire la validation.

Le problème avait alors été déplacé au fait qu'il fallait valider l'algorithme ainsi que le programme qui l'implémentait. Ce sont des problèmes devenus courants avec le développement de l'informatique, aujourd'hui.

Par ailleurs, il paraît que cela avait nécessité 1200 heures de calcul en 1976. On peut raisonnablement penser qu'il n'en faudrait qu'une pour faire le même travail de nos jours. On aurait pu trouver aussi 500 personnes motivées de par le monde pour vérifier chacune 3 cas de figure, mais les embûches seraient restées les mêmes (fiabilité de l'ensemble des vérificateurs), tout comme la difficulté principale, qui résidait dans la quantité de travail à mener.