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.

[Schpountz42]

C'est justement pas ce que j'ai entendu.
Mais de toute façon on s'en fout, ca me donne pas des algo pour autant^^

[SpiceGuid]

De plus ca garantie de trouver une solution? ou juste une grande probabilité de trouver une bonne solution?

Comme l'a suggéré millie tu pourrais peut être commencer par faire un test de planarité ?
(à moins que tu te fiches de la planarité)

[Schpountz42]

oui la planarité du graphe n'est pas le problème. On part du principe qu'il l'est. (en théorie je ne devrais même pas savoir ce que c'est lol)

[cedriku]

En ce qui concerne le probleme de coloration d'un graphe, la modelisation en SAT ou CSP s'y prete bien. D'ailleurs, il y a eu enormement de travaux fait dessus (en fait ce ne sont que des contraintes de differences) et les meilleurs algos sur ce genre de probleme sont ceux qui detectent les symetries. En fait, dans ce genre de probleme, il y a enormement de symetrie en general (1 couleur n'est pas differente d'une autre mais dans la modelisation elle seront considerees comme differente, ce qui fait que lalgo risque dessayer toutes les couleurs alors quen fait il pourrait voir que si avec une ca marche pas, les autre non plus -> elagage dans l'espace de recherche !).

En tout cas (sans me rappeler du nom des algos de tete la), cherche des algos qui exploitent des symetries dans les problemes avec contraintes de differences.

[Graffito]

A: De plus ca garantie de trouver une solution?
ou
B: juste une grande probabilité de trouver une bonne solution?

A: non
B: c'est l'objectif, avec en cas de problème un minimum de back-tracking.

En fait, un meilleur algo consisterait à recalculer le coefficient de difficulté après chaque affectation de couleur. Mais, je n'arrive pas à formaliser un coeff qui tiennent compte des sommet auquels on a dèjà affecté une couleur.

[Schpountz42]

L'algo dont tu me parles ne serait pas le DSATUR?

http://fr.wikipedia.org/wiki/Dsatur

Celui ci me parait intéressant car il n'a pas l'air de faire un rebroussement de chemin.

[cedriku]

C'est un des algorithmes dont je te parlais mais il en existe beaucoup d'autres (d'ailleurs je crois que dans mon labo certains ont travaille dessus...).

C'est normal qu'il n'y ai pas de retour arriere (backtrack) puisque pour cet algo il est supposé que tu as autant de couleurs que tu veux (quand tu colorie le sommet a l'étape 4 de l'algo, tu choisis la plus petite couleur qui ne rentre pas en conflit avec une couleur d'un sommet voisin, donc tu peux toujours choisir une couleur).

Par contre, si tu cherches un algo pour colorier un graphe avec un nombre de couleurs limité au depart alors cet algo ne marche plus sans y rajouter une operation de backtrack.

Donc tout dépend de ton probleme au depart... est-ce que tu imposes un nombre de couleurs ou alors tu peux en choisir tant que tu veux ?

[Schpountz42]

Je vais emmerder le monde mais... les 2

Ca dépend de l'option que choisit l'utilisateur de l'application final. Il me faut des algorithmes dans les 2 cas.
Mais je retient déjà le DSATUR et l'algorithme de Welsh et Powell.

http://fr.wikipedia.org/wiki/Coloration_de_graphe

[cedriku]

Ben deja le truc c'est que c'est completement different !

Dans un cas (celui ou l'on n'impose pas le nombre de couleurs), le problème est "simple" (pas de backtracking).

Dans le 2eme cas (avec un nombre k de couleurs), savoir s'il existe une solution pour colorier le graphe avec k couleurs est un probleme NP-Complet !!! (donc il n'existe pas d'algorithme polynomial CONNU pour résoudre ce probleme). C'est pour ce cas la que je préconisai l'utilisation de CSP (avec par exemple du Forward-Checking dessus ou toute autre technique).

[Schpountz42]

Désolé de l'inactivité mais je finissait le reste de l'application. Maintenant il me reste qu'à implanter d'autres algorithmes.

Donc pour résumé ce que j'ai pour le moment:
- Si on impose le nombre de couleurs max :
+ Back-Tracking (avec CSP?)

- Si on impose PAS le nombre de couleur max :
+ DSATUR
+ RLF (Recursive Largest-First)


D'autre idée?

[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.

[Jedai]

C'est justement pas ce que j'ai entendu.
Mais de toute façon on s'en fout, ca me donne pas des algo pour autant^^

En fait si, si les systèmes de preuve formelles ont été utilisé alors la preuve est un algorithme de coloriage. Grosso modo, démontrer le théorème dans un système de preuve formelle consiste à construire un programme de type "g :: Graph -> Planar(g) -> exists c :: Coloring-4(g) . NeverTwoSameColorAdjacent(c)". Donc à la fin on peut exécuter ce programme sur un graphe et obtenir un coloriage correct. Mais bon, je ne garantis pas les performances !

--
Jedaï