Méthode de Welsh Powell pour la coloration de graphe

Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
road
Messages: 2
Enregistré le: 19 Oct 2017, 15:56

Méthode de Welsh Powell pour la coloration de graphe

par road » 19 Oct 2017, 16:07

Bonjour,

Ma question est simple : généralement pour colorer un graphe j'utilise la méthode de Welsh Powell.
Cependant il parraît que cette méthode propose une coloration non optimale.
J'aimerai bien m'en convaincre, alors je cherche un contre exemple (ie un graphe où Welsh Powell donne un nombre chromatique > (G) ).

Voilà, merci d'avance !



Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21479
Enregistré le: 11 Nov 2009, 23:53

Re: Méthode de Welsh Powell pour la coloration de graphe

par Ben314 » 19 Oct 2017, 20:02

Salut,
Wiki est ton ami :
Tu trouvera sur la page "Coloriation de Graphes" que :
Remarquons que l'algorithme de Welsh et Powell peut aboutir à la pire des colorations possibles, par exemple si le graphe G a la structure de couronne à n sommets, son nombre chromatique est 2 (si n est pair) tandis que Welsh-Powell donne dans certains cas (selon l'ordre dans lequel sont rangés les sommets) une coloration utilisant n/2 couleurs !
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

road
Messages: 2
Enregistré le: 19 Oct 2017, 15:56

Re: Méthode de Welsh Powell pour la coloration de graphe

par road » 19 Oct 2017, 22:37

Salut Ben314,

Merci pour ta réponse ! J'avais lu cette page wikipédia, mais j'ai beau essayé de 'mal' colorier ces graphes en horloge, j'arrive à une coloration à 2 couleurs (en suivant Welsh Powell)...
Pourrais tu essayer de m'expliquer quel problème pourrait survenir s'il te plaît ?

Merci d'avance !

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21479
Enregistré le: 11 Nov 2009, 23:53

Re: Méthode de Welsh Powell pour la coloration de graphe

par Ben314 » 19 Oct 2017, 23:05

Si les sommets de ton graphe sont et les (uniques) arrêtes sont les pour et que tu applique Welsh et Powell en prenant comme ordre pour les sommets , ça donne quoi ?
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

 

Retourner vers ✯✎ Supérieur

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 91 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite