Coloration de graphe

Colorer un graphe avec le moins de couleurs possible

À propos de cette calculatrice

Le calculateur de coloration de graphe trouve le nombre chromatique χ(G) — le plus petit nombre de couleurs nécessaires pour colorer les sommets d'un graphe de sorte qu'aucune arête ne relie deux sommets de la même couleur — et affiche une coloration optimale. Saisissez le nombre de sommets et une liste d'arêtes ; il calcule χ exactement avec une recherche par séparation et évaluation (branch-and-bound), indique le degré maximal Δ et la plus grande clique ω (une borne inférieure de χ), signale les graphes bipartis et complets, et dessine le graphe coloré. Utile pour l'ordonnancement, l'allocation de registres, la coloration de cartes et l'étude des nombres chromatiques.

Comment colorer un graphe

  1. Saisissez le nombre de sommets ; ils sont numérotés de 1 à n.
  2. Listez les arêtes sous forme de paires comme 1-2, 2-3 — une paire par connexion.
  3. Lisez le nombre chromatique χ(G) et la couleur attribuée à chaque sommet.
  4. Comparez χ à la plus grande clique ω pour comprendre pourquoi autant de couleurs sont nécessaires, ou chargez un exemple pour explorer.

Exemples courants

  • Un triangle (K₃) nécessite 3 couleurs — chaque paire de ses sommets est adjacente.
  • Les cycles pairs sont bipartis et ne nécessitent que 2 couleurs ; les cycles impairs comme C₅ en nécessitent 3.
  • Le graphe complet Kₙ nécessite exactement n couleurs.
  • Une plus grande clique de taille ω force au moins ω couleurs, donc χ(G) ≥ ω.
  • Le graphe de Grötzsch nécessite 4 couleurs sans pourtant contenir de triangle, donc χ peut dépasser le nombre de clique.

Questions fréquentes

Qu'est-ce que le nombre chromatique ?

Le nombre chromatique χ(G) est le plus petit nombre de couleurs nécessaires pour colorer les sommets d'un graphe de sorte qu'aucune arête ne relie deux sommets de la même couleur.

Comment le nombre minimal de couleurs est-il trouvé ?

Comme le graphe est petit, le calculateur effectue une recherche exacte : il essaie 1 couleur, puis 2, et ainsi de suite, en renvoyant le premier nombre pour lequel une coloration propre existe. Ce nombre est garanti d'être le vrai minimum.

Que sont le degré maximal et la plus grande clique ?

Le degré maximal Δ est le plus grand nombre d'arêtes se rencontrant en un seul sommet. La plus grande clique ω est le plus grand ensemble de sommets tous mutuellement adjacents ; comme ils doivent tous différer, χ(G) est au moins égal à ω.

Pourquoi un graphe sans triangle peut-il tout de même nécessiter de nombreuses couleurs ?

Une grande clique force de nombreuses couleurs, mais ce n'est pas la seule raison. Les cycles impairs et les graphes comme le graphe de Grötzsch nécessitent des couleurs supplémentaires même sans aucun triangle, donc χ(G) peut être plus grand que le nombre de clique.

Y a-t-il une limite à la taille du graphe ?

Oui. La coloration exacte de graphe est difficile à calculer, donc le calculateur limite le graphe à 12 sommets pour garder des résultats instantanés et rigoureux.