Calculateur de Coloration de Graphes

Calculateur de Coloration de Graphes

Le Calculateur de coloration de graphes calcule le nombre chromatique χ(G) et une coloration de sommets valide pour tout graphe non orienté. Saisissez votre graphe sous forme de liste d'arêtes ou de liste d'adjacence et l'outil renvoie le nombre minimum de couleurs nécessaires pour qu'aucun sommet adjacent ne partage la même couleur, accompagné d'une visualisation SVG interactive, d'une trace DSATUR animée et d'une répartition couleur par couleur des sommets.

Qu'est-ce que la coloration de graphe ?

Une coloration de sommets propre d'un graphe G = (V, E) attribue une couleur à chaque sommet de sorte que chaque arête ait des extrémités de couleurs différentes. Le nombre chromatique, noté χ(G), est le plus petit nombre de couleurs pour lequel une telle coloration existe. Le calcul de χ(G) est globalement NP-difficile, mais le problème possède une théorie mathématique riche et de nombreuses applications pratiques : planification d'examens, attribution de fréquences radio, allocation de registres dans les compilateurs et le célèbre théorème des quatre couleurs pour les cartes planaires.

Théorèmes et bornes clés

• Bornes triviales : 1 ≤ χ(G) ≤ |V| pour tout graphe.
• Borne inférieure de clique : χ(G) ≥ ω(G), où ω(G) est la taille de la plus grande clique.
• Caractérisation bipartie : χ(G) ≤ 2 si et seulement si G n'a pas de cycle impair (König).
• Théorème de Brooks : χ(G) ≤ Δ(G), sauf si G est un graphe complet ou un cycle impair, auquel cas χ(G) = Δ(G) + 1. Ici Δ(G) est le degré maximum.
• Théorème des quatre couleurs : Tout graphe planaire est 4-colorable.
• Borne supérieure gloutonne : Tout algorithme glouton utilise au plus Δ(G) + 1 couleurs.

Algorithmes utilisés par ce calculateur

DSATUR (Degré de saturation)

Introduit par Daniel Brélaz en 1979, DSATUR est l'une des heuristiques pratiques les plus performantes pour la coloration de graphes. Il choisit de manière répétée le sommet non coloré dont les voisins utilisent déjà le plus de couleurs distinctes (sa saturation), lève les ambiguïtés par le degré du sommet, et lui attribue la plus petite couleur non utilisée par ses voisins. DSATUR est prouvé optimal sur les graphes bipartis et sur de nombreuses familles de graphes structurés, et produit des colorations de haute qualité en quelques millisecondes sur des graphes comportant des centaines de sommets.

Welsh-Powell

L'algorithme de Welsh-Powell trie les sommets par ordre décroissant de degré puis les colore de manière gloutonne. Il s'exécute en un temps O(|V|²) et garantit au plus Δ(G) + 1 couleurs. Il est extrêmement rapide et constitue souvent une bonne première approximation, bien qu'il puisse être surpassé par DSATUR sur des graphes à structure locale variable.

Glouton (ordre de saisie)

L'algorithme le plus simple : parcourir les sommets dans l'ordre de saisie et attribuer à chacun la plus petite couleur non utilisée par un voisin déjà coloré. Le résultat est sensible à l'ordre de saisie, mais un ordre aléatoire donne une base de comparaison pour les heuristiques plus intelligentes.

Backtracking exact

Pour les petits graphes (jusqu'à environ 18 sommets), le calculateur peut trouver le vrai nombre chromatique en essayant k = 2, 3, 4, ... et en tentant de k-colorer le graphe par backtracking en profondeur. La recherche trie les sommets par degré décroissant et s'arrête lorsqu'aucune couleur n'est disponible. Lorsque l'algorithme exact réussit, le résultat est marqué comme "Exact".

Formats de saisie

Liste d'arêtes

Écrivez chaque arête sous la forme de deux étiquettes de sommet séparées par un trait d'union, un espace ou une flèche. Séparez les arêtes par des virgules ou des sauts de ligne. Les étiquettes de sommets peuvent être des lettres, des chiffres ou des tirets bas. Exemple :

Liste d'adjacence

Écrivez chaque sommet, un deux-points, et la liste de ses voisins séparés par des virgules. Exemple :

Les boucles sur soi-même sont rejetées car un sommet ne peut pas recevoir une couleur différente de lui-même. Les arêtes en double sont supprimées silencieusement et le graphe est traité comme non orienté.

Comment utiliser ce calculateur

1. Choisir un format : Basculez entre liste d'arêtes et liste d'adjacence avec les boutons radio.
2. Entrer le graphe : Collez vos données ou cliquez sur l'un des exemples rapides (triangle, complet K₅, roue type Petersen, biparti K₃,₃, planification d'examens).
3. Choisir un algorithme : Laissez sur Auto pour le meilleur choix par défaut, ou forcez Welsh-Powell, glouton, DSATUR ou backtracking exact.
4. Cliquez sur "Colorer le Graphe" : Le nombre chromatique, une liste par couleur, un SVG interactif avec des nœuds déplaçables et une trace animée étape par étape apparaissent ci-dessous.
5. Explorer : Appuyez sur Lecture pour voir l'algorithme colorer les sommets, faites glisser les nœuds pour réorganiser la mise en page, et utilisez Retour / Suivant pour parcourir manuellement la trace.

Applications pratiques de la coloration de graphe

Planification d'examens

Considérons chaque examen comme un sommet et traçons une arête entre les examens qui partagent au moins un étudiant. Une coloration propre avec k couleurs donne un planning avec k créneaux horaires tel qu'aucun étudiant n'ait de conflit. Le nombre chromatique est le nombre minimum de créneaux.

Attribution de fréquences radio

Les émetteurs situés dans la zone d'interférence les uns des autres doivent diffuser sur des fréquences différentes. Le nombre chromatique du graphe d'interférence est le nombre minimum de fréquences nécessaires.

Allocation de registres

Dans les compilateurs, les plages de vie des variables sont des sommets ; deux plages de vie qui se chevauchent dans le temps signifient qu'il y a une arête entre elles. Une k-coloration affecte les variables à k registres CPU sans collision.

Coloration de cartes

Les pays qui partagent une frontière doivent recevoir des couleurs différentes. Le théorème des quatre couleurs (Appel-Haken, 1976) prouve que quatre couleurs suffisent toujours pour n'importe quelle carte planaire.

Sudoku et puzzles de contraintes

Un Sudoku terminé est une 9-coloration d'un graphe dont les sommets sont les 81 cellules et dont les arêtes relient les cellules d'une même ligne, colonne ou bloc 3×3. La coloration de graphe est le cœur mathématique de nombreux puzzles de satisfaction de contraintes.

Cas particuliers intéressants

• Graphe complet K_n : χ(K_n) = n. Chaque paire de sommets est adjacente, toutes les couleurs doivent donc être distinctes.
• Cycle C_n : χ(C_n) = 2 si n est pair, 3 si n est impair.
• Arbre : Tout arbre ayant ≥ 2 sommets a χ = 2 (les arbres sont bipartis).
• Graphe biparti : χ = 2 si le graphe possède au moins une arête.
• Graphe de Petersen : Un célèbre graphe 3-régulier avec χ = 3.
• Roue W_n : Un sommet central relié à un cycle de longueur n. χ = 3 si n est pair, 4 si n est impair.

Foire aux questions

Qu'est-ce que le nombre chromatique d'un graphe ?

Le nombre chromatique χ(G) est le plus petit nombre de couleurs nécessaires pour colorer les sommets d'un graphe afin que deux sommets adjacents ne partagent pas la même couleur. Les graphes bipartis ont un nombre chromatique d'au plus 2 ; tout graphe contenant un triangle a un nombre chromatique d'au moins 3 ; et selon le théorème de Brooks, le nombre chromatique ne dépasse jamais le degré maximum, sauf pour les graphes complets et les cycles impairs.

Quel algorithme ce calculateur utilise-t-il ?

Pour les petits graphes, le calculateur lance une recherche par backtracking exact pour trouver le vrai nombre chromatique. Pour les graphes plus grands, il utilise l'heuristique DSATUR, qui colore de manière répétée le sommet non coloré ayant le plus de voisins déjà colorés. Vous pouvez également forcer Welsh-Powell ou un simple algorithme glouton dans le menu déroulant Algorithme.

Comment dois-je saisir mon graphe ?

Utilisez le mode liste d'arêtes pour taper une arête par ligne telle que A-B, ou séparées par des virgules comme A-B, B-C, C-A. Utilisez le mode liste d'adjacence pour écrire chaque sommet suivi de deux-points et de ses voisins, comme A: B, C. Les boucles sur soi-même sont rejetées car un sommet ne peut être coloré différemment de lui-même.

Pourquoi DSATUR ne trouve-t-il pas toujours le vrai nombre chromatique ?

La coloration de graphe est un problème NP-difficile, donc aucun algorithme rapide connu ne trouve toujours le nombre minimum de couleurs. DSATUR est une excellente heuristique pratique et correspond souvent au nombre chromatique réel, mais sur des graphes conçus pour le piéger, il peut utiliser plus de couleurs que nécessaire. Le calculateur indique les couleurs utilisées et une borne inférieure basée sur la plus grande clique trouvée pour vous aider à évaluer le résultat.

Quelle est l'application réelle de la coloration de graphe ?

La coloration de graphe modélise l'organisation d'examens, l'attribution de fréquences radio, l'allocation de registres dans les processeurs, la coloration de cartes géographiques, la résolution de sudokus et l'affectation de tâches sous contraintes.

Le nombre chromatique est-il toujours égal à la plus grande clique ?

Non. Le nombre de clique ω(G) est toujours une borne inférieure pour le nombre chromatique χ(G), et ils sont égaux pour les graphes parfaits comme les graphes bipartis ou les arbres. Pour les graphes généraux, χ(G) peut être supérieur ; les graphes de Mycielski en sont l'exemple type : ils n'ont pas de triangles mais nécessitent pourtant beaucoup de couleurs.

Quelle est la taille maximale de graphe que ce calculateur peut traiter ?

Le calculateur supporte jusqu'à 60 sommets et 600 arêtes. Pour l'algorithme exact, les graphes de plus de 18 sommets environ peuvent basculer sur DSATUR car le backtracking devient trop lent. Pour un usage pratique, cela couvre la plupart des exemples scolaires, des problèmes de planning et des applications de taille moyenne.

Lectures complémentaires

• Coloration de graphe — Wikipédia
• Algorithme DSATUR — Wikipédia (en anglais)
• Polynôme chromatique — Wikipédia
• Théorème des quatre couleurs — Wikipédia
• Théorème de Brooks — Wikipédia

Opérations mathématiques avancées:

• Calculateur de Matrice d'Adjacence Nouveau
• Calculatrice d'Antilogarithme
• Calculatrice de la fonction bêta
• Calculateur de Coefficient Binomial
• Calculatrice de distribution binomiale
• Calculatrice de Bit
• Simplificateur d'Algèbre de Boole Nouveau
• Calculateur du Théorème Central Limite
• Calculatrice du Théorème des Restes Chinois
• Calculatrice de Combinaison Populaire
• Calculatrice de Fonction d'Erreur Complémentaire
• Calculatrice de Nombres Complexes
• Calculatrice de fractions continues
• Calculateur de Dérangement (Sous-factorielle)
• Calculateur de plus court chemin de Dijkstra
• Calculatrice d'Entropie
• Calculatrice de fonction d'erreur
• Calculatrice de la fonction indicatrice d'Euler
• Calculatrice de désintégration exponentielle
• Calculatrice de croissance exponentielle
• Calculatrice d'intégrale exponentielle
• Calculatrice des Exposants (Haute Précision) Populaire
• Calculatrice de l'Algorithme Euclidien Étendu
• Calculatrice Factorielle
• Calculatrice de Fonction Gamma
• Calculateur de Nombre d'Or
• Calculateur de Coloration de Graphes Nouveau
• Validateur de séquence de degrés de graphe
• Calculateur d'Ordre en Théorie des Groupes Nouveau
• Calculatrice de demi-vie
• Vérificateur de Chemin Hamiltonien Nouveau
• Calculateur d'Inclusion-Exclusion Nouveau
• Solveur de Tableau de Karnaugh (K-Map) Nouveau
• Solveur de Programmation Linéaire Nouveau
• Calculateur d'état stationnaire de chaîne de Markov
• Calculateur d'arbre couvrant minimum
• Calculateur d'Exponentiation Modulaire Nouveau
• Calculatrice de l'Inverse Multiplicatif Modulaire
• Calculateur de Distribution Binomiale Négative Nouveau
• Calculateur de Flot Maximal dans un Réseau Nouveau
• Calculatrice du Taux de Croissance en Pourcentage Populaire
• Calculatrice de permutation
• Calculateur de Permutations avec Répétition Nouveau
• Calculateur du principe des tiroirs
• Vérificateur de Graphe Planaire Nouveau
• Calculatrice de Distribution de Poisson
• Calculatrice des racines de polynômes avec étapes détaillées
• Calculateur de Racine Primitive
• Calculatrice de probabilité
• Calculatrice de Distribution de Probabilité
• Calculatrice de Proportion
• Calculatrice de Formule Quadratique Populaire
• Calculateur d’Anneaux et de Corps Nouveau
• Calculateur d'Arrondi Nouveau
• Calculatrice Scientifique
• Calculatrice de notation scientifique
• Calculateur de Théorie des Ensembles
• Calculateur de Chiffres Significatifs Nouveau
• Solveur du Problème des Mariages Stables Nouveau
• Calculateur de Nombres de Stirling
• Calculatrice de Somme de Cubes
• Calculatrice de la somme des entiers positifs
• Calculatrice de la somme des carrés
• Calculateur de Tri Topologique Nouveau
• Solveur du Voyageur de Commerce (TSP) Nouveau
• Générateur de table de vérité
• Générateur de Diagramme de Venn (3 Ensembles)