Discussion:Algorithme glouton
Apparence
Autres discussions [liste]
- Admissibilité
- Neutralité
- Droit d'auteur
- Article de qualité
- Bon article
- Lumière sur
- À faire
- Archives
- Commons
L'algorithme glouton en coloration de graphes
[modifier le code]Bonjour,
L'algorithme de coloration de graphe suivant était présenté dans cet article :
Debut Glouton G=(V,E) Y=V couleur = 0 Tant que (Y n'est pas vide Faire) couleur ++ Z=Y Tant que Z (n'est pas vide Faire) Choisir v un sommet de Z colorier v par couleur Y = Y - v Z = Z - v - (les voisins de v) Fin tant que Fin tant que Fin
Cet algorithme est bien un algorithme glouton. Néanmoins, il ne correspond pas à celui que l'on appelle usuellement "l'algorithme glouton" de coloration des graphes. Par exemple, il ne correspond :
- ni à l'algorithme présenté dans ce document pédagogique
- ni à l'algorithme décrit dans l'article en:Greedy coloring
Je l'ai donc remplacé par l'algorithme suivant :
Glouton Entrée : liste ordonnée V des n sommets d'un graphe G liste ordonnée C de couleurs Pour i variant de 1 à n v = V[i] couleur = la première couleur de C non utilisée par les voisins de v colorier(v, couleur) Fin pour
Cordialement, --MathsPoetry (d) 12 avril 2012 à 22:45 (CEST)
Exemples
[modifier le code]Bon, il faut décider ce que l'on fait pour les exemples. J'ai supprimé arbitrairement la coloration gloutonne, mais autant réfléchir ici avant de faire d'autres changements ou de reverter celui-ci. Je n'ai pas vraiment de préférences précises mais je pense tout de même qu'il serait bon d'avoir :
- au plus trois exemples,
- au moins un dans lequel l'algorithme glouton est optimal et au moins un dans lequel il ne l'est pas,
- le problème de l'arbre couvrant de poids minimal, que je pense important (plusieurs algorithmes gloutons classiques et lien privilégié avec les matroïdes (me semble-t-il)).
--Roll-Morton (discuter) 8 mars 2015 à 22:37 (CET)
- Le nombre d'exemples ne me gène pas vraiment, et puis il faut faire attention, un certain nombre sont des classiques.
- Ce qui me gène plutôt dans l'article, c'est son aspect allusif. Il faudrait mieux contextualiser les algorithmes, mieux les expliquer, voire donner un exemple de déroulement.
- Donc plutôt que de supprimer de la matière, je serais plutôt pour en ajouter, quitte à déverser dans des articles détaillés. --Catarella (discuter) 9 mars 2015 à 16:16 (CET)
- J'ai remis la coloration avec une source et déplacé le voyageur dans l'article détaillé. Il faudrait en effet détailler les exemples. Pour ce qui est du nombre et des exemples classiques, on peut peut-être en mettre deux ou trois détaillés, puis une sous-section pour le reste avec des références. J'aimerais que l'article ne ressemble pas trop à une liste. --Roll-Morton (discuter) 9 mars 2015 à 17:55 (CET)