Coloration de graphes
Bonjour,
S’il vous plait, je cherche un algorithme pour colorer un graphe de tolérance bornée.
S’il vous plait, je cherche un algorithme pour colorer un graphe de tolérance bornée.
Réponses
-
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. -
Bonjour,
Merci pour votre repense, mais j'ai besoins d'un algorithme efficace qui permet de colorer le graphe une coloration minimum. -
Celui que je vous propose est efficace ! Vous cherchez un qui serait plus efficace que celui de Welsch Powel , c'est ça ?
-
Et l'algorithme des quatre couleurs par K. Appel et W. Haken va aussi ...
-
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 -
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!
Catégories
- 163.1K Toutes les catégories
- 8 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres