Coloration de graphes

siham
siham
dans Combinatoire et Graphes
Bonjour,
S’il vous plait, je cherche un algorithme pour colorer un graphe de tolérance bornée.

Réponses

  • Udani
    Udani
    Bonjour,
    Je pense que l'algorithme de Welsch Powel satisfait tes conditions. Bien qu'il ne fournit pas le nombre chromatique, il aide à le calculer à l'aide d'un encadrement que vérifie le dernier.
  • siham
    siham
    Bonjour,
    Merci pour votre repense, mais j'ai besoins d'un algorithme efficace qui permet de colorer le graphe une coloration minimum.
  • Udani
    Udani
    Celui que je vous propose est efficace ! Vous cherchez un qui serait plus efficace que celui de Welsch Powel , c'est ça ?
  • Alannaria
    Alannaria
    Et l'algorithme des quatre couleurs par K. Appel et W. Haken va aussi ...
  • christophe c
    christophe c
    pour colorer un graphe de tolérance bornée

    Ca veut dire quoi "tolérance bornée"?
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • aoraki
    aoraki
    Je ne sais pas ce que veut dire "tolérance bornée".

    Il n'existe pas d'algorithme de coloration donnant une coloration optimale en un temps polynomial pour tout graphe.

    Cependant, l'algorithme DSAT de Brelaz est rapide, et il est optimal pour les catégories classiques de graphes. Je recommande cet algorithme.
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 32

ChaurienCyranoKarnajLP2MagnéthoraxMatricule_63OShinePaul Broussousdedekind93natounouvpf +21 Invités