Qu'est-ce que la coloration de graphe ?

C'est l'attribution de couleurs (ou de toute étiquette) aux sommets d'un graphe de sorte que deux sommets reliés par une arête ne partagent jamais la même couleur.

Qu'est-ce que l'algorithme de Welsh-Powell ?

C'est une heuristique de coloration gloutonne : trier les sommets par degré décroissant, puis colorier chacun, dans cet ordre, avec le plus petit numéro de couleur pas encore utilisé par l'un de ses voisins déjà coloriés.

Cela trouve-t-il le nombre minimal de couleurs ?

Pas nécessairement — cette approche gloutonne donne une borne supérieure du véritable nombre chromatique du graphe. Trouver le minimum exact est NP-difficile en général, donc cette calculatrice échange des garanties d'optimalité contre de la vitesse, comme la plupart des outils pratiques de coloration de graphe.

Qu'est-ce que le nombre chromatique ?

C'est le plus petit nombre de couleurs nécessaire pour colorier correctement un graphe — le minimum théorique que des algorithmes gloutons comme Welsh-Powell approximent par le haut.

Pourquoi l'ordre de coloration est-il important ?

Colorier d'abord les sommets à haut degré tend à utiliser moins de couleurs au total, car ces sommets ont le plus de contraintes et bénéficient le plus d'être coloriés pendant que le plus d'options de couleurs sont encore disponibles.

Qu'est-ce que le théorème des quatre couleurs ?

Il affirme que tout graphe planaire (pouvant être dessiné sans croisements d'arêtes) peut toujours être colorié avec au plus 4 couleurs — prouvé de façon célèbre à l'aide d'un ordinateur en 1976, et à l'origine de l'intuition de coloration de cartes derrière la coloration de graphe.

Combien de nœuds cette calculatrice peut-elle gérer ?

Cette calculatrice prend en charge jusqu'à 50 nœuds, gardant le calcul de coloration gloutonne instantané tout en couvrant la grande majorité des exemples de graphes saisis à la main.

Où la coloration de graphe est-elle utilisée dans la vie réelle ?

Elle est utilisée pour la planification d'examens et de réunions (les événements en conflit reçoivent des couleurs/créneaux horaires différents), l'allocation de registres dans les compilateurs, l'attribution de fréquences dans les réseaux mobiles, et les problèmes de satisfaction de contraintes de type Sudoku.

Calculatrice de Coloration de Graphe — Coloriez un Graphe Sans que des Nœuds Adjacents Correspondent

Notre Calculatrice de Coloration de Graphe attribue une couleur à chaque sommet d'un graphe de sorte que deux sommets directement connectés ne partagent jamais la même couleur, à l'aide de l'algorithme glouton de Welsh-Powell (nœuds ordonnés par degré décroissant), votre graphe étant saisi sous forme de simple liste d'arêtes textuelle (par ex. A-B, A-C, B-C).

Réponse rapide

Saisissez votre graphe sous forme de liste d'arêtes pour colorier instantanément chaque sommet de sorte qu'aucun deux nœuds connectés ne partagent une couleur, à l'aide de l'algorithme glouton de Welsh-Powell.

Arêtes (séparées par des virgules)

Saisissez des arêtes sous la forme NœudA-NœudB, par ex. A-B, A-C, B-C.

Comment utiliser Calculatrice de Coloration de Graphe — Algorithme de Welsh-Powell en Ligne

1
Saisissez votre graphe sous forme de liste d'arêtes séparées par des virgules, par ex. A-B, A-C, B-C.
2
Cliquez sur 'Calculer' pour colorier chaque sommet à l'aide de l'algorithme de Welsh-Powell.
3
Consultez la couleur attribuée à chaque nœud et le nombre total de couleurs utilisées.

Pourquoi utiliser Calculatrice de Coloration de Graphe — Algorithme de Welsh-Powell en Ligne ?

La coloration de graphe attribue des étiquettes ('couleurs') aux sommets de sorte qu'aucune arête ne relie deux sommets de la même couleur — l'abstraction classique derrière les problèmes de planification (deux examens en conflit ne partagent pas le même créneau horaire) et la coloration de cartes (deux régions adjacentes ne partagent pas de couleur). Trouver le véritable nombre minimal de couleurs (le nombre chromatique) est NP-difficile en général, mais l'heuristique de Welsh-Powell — colorier les sommets par ordre décroissant de degré, en choisissant toujours la plus petite couleur disponible — produit une coloration bonne et rapide qui est prouvée proche de l'optimal pour de nombreux graphes pratiques, exactement ce que calcule cette calculatrice.

Questions fréquentes

Outils similaires

Calculatrice d'Arbre Couvrant Minimal — Algorithme de Kruskal en Ligne

Trouvez l'arbre couvrant minimal d'un graphe pondéré à l'aide de l'algorithme de Kruskal. Calculatrice gratuite avec une simple saisie de liste d'arêtes et détection de cycles par union-find.

Validateur de Séquence de Degrés de Graphe — Théorème d'Erdős–Gallai en Ligne

Vérifiez si une séquence de nombres est une séquence de degrés valide (graphique) à l'aide du théorème d'Erdős–Gallai. Calculatrice gratuite avec vérification étape par étape.

Calculatrice de Matrice d'Adjacence — Construisez une Matrice de Graphe en Ligne

Construisez et affichez la matrice d'adjacence d'un graphe à partir d'une simple saisie de liste d'arêtes, avec sa séquence de degrés. Calculatrice gratuite, pondérée ou non pondérée.

Solveur du Problème des Mariages Stables — Algorithme de Gale-Shapley en Ligne

Trouvez un appariement stable entre deux groupes de même taille à partir de leurs listes de préférences à l'aide de l'algorithme de Gale-Shapley. Calculateur gratuit, résultats stables garantis.