Almgorithme Welsh-Powell

[Poésie]

Bonjour,

Je souhaiterai avoir vos avis concernant ma réponse sur un graphe à l'aide d'un Algorithme de Welsh-Powell dont le but est de:

Colorer le graphe ci-dessus à l'aide de l'algorithme de Welsh-Powell, au moyen des couleurs bleu/rouge/vert/jaune/violet (dans cet ordre). Pour chaque sommet, mentionner la couleur associée.Après exécution de cet algorithme, vous avez eu besoin de combien de couleurs ? Cette coloration est-elle optimale en terme du nombre de couleurs utilisées ?

J'ai trois couleurs bleu, rouge, vert.
Sommets: B E D A C F G
Degré: 5 4 3 3 2 2 1
Bleu: B x x x B x x
Rouge: x R x R x x R
Vert: x x V x x V x
Conclusion: AEG en rouge, DF en vert, CB en bleu.Je n'ai pas utilisé les autres couleurs donc poursuivie l’algorithme car chaque lettres avaient déjà une couleur.
Avec l'application de l'algorithme, je pense qu'il est optimale.

Le graphe est en pièce jointe.

Je vous remercie de votre compréhension.

Bien à vous,
OnPointe

 

[julesx]

Bonsoir et bienvenue sur le site,

Pour moi, ta coloration est optimale, je ne vois pas comment n'utiliser que deux couleurs en respectant les contraintes. Pour info, si quelqu'un d'autre veut s'y attaquer...