Discussion:Algorithme glouton
- Admissibilité
- Neutralité
- Droit d'auteur
- Article de qualité
- Bon article
- Lumière sur
- À faire
- Archives
- Commons
Cet article est indexé par le projet Mathématiques.
Les projets ont pour but d’enrichir le contenu de Wikipédia en aidant à la coordination du travail des contributeurs. Vous pouvez modifier directement cet article ou visiter les pages de projets pour prendre conseil ou consulter la liste des tâches et des objectifs.
| Avancement | Importance | pour le projet | |
|---|---|---|---|
| Bon début | Moyenne |  | Mathématiques (discussion • critères • liste • stats • hist. • comité • stats vues) |
Cet article ne comporte pas de liste de tâches suggérées. Vous pouvez saisir une liste de tâches à accomplir (par exemple sous forme d'une liste à puces), puis sauvegarder. Vous pouvez aussi consulter la page d'aide.
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)