Histoire et cultureThéorème · Glossaire
théorème de Vizing
Pour un graphe simple, une coloration des arêtes attribue des couleurs aux arêtes de sorte que deux arêtes ayant un sommet commun aient des couleurs différentes ; son nombre chromatique χ′ est le minimum de couleurs nécessaire, et Δ le degré maximal d’un sommet. Le théorème de Vizing affirme que Δ ≤ χ′ ≤ Δ + 1 : la contrainte locale la plus forte impose au moins Δ couleurs, et une seule couleur supplémentaire suffit toujours.
Sommaire
Ce que vous allez apprendre
- Définir le degré maximal et le nombre chromatique des arêtes avant d’énoncer leurs deux valeurs possibles.
- Vérifier sur le cycle à cinq sommets pourquoi deux couleurs échouent et trois couleurs suffisent.
- Distinguer coloration des arêtes, coloration des sommets et degré maximal.
- Repérer l’hypothèse de graphe simple et les preuves nécessaires pour conclure à la classe 1 ou 2.
En clair
Dessinez cinq points en pentagone et reliez chaque point à ses deux voisins. Il faut colorer les cinq segments sans que deux segments qui se touchent aient la même couleur. Deux couleurs obligent à alterner, mais le dernier segment rencontre alors un segment de sa couleur. Une troisième couleur ferme la boucle sans conflit.
Le théorème de Vizing généralise cette économie de couleurs : si le sommet le plus chargé reçoit Δ arêtes, tout graphe simple se contente de Δ couleurs ou demande exactement une couleur supplémentaire.
Définition
Une coloration propre des arêtes d’un graphe simple attribue une couleur à chaque arête de sorte que deux arêtes incidentes à un même sommet portent des couleurs différentes. Le nombre minimal de couleurs nécessaires est le nombre chromatique des arêtes, noté χ′(G) pour le graphe G. Le degré d’un sommet compte ses arêtes incidentes ; le plus grand de ces degrés est le degré maximal, noté Δ.
Au sommet de degré Δ, les Δ arêtes doivent toutes recevoir des couleurs distinctes. Cette contrainte donne la borne inférieure χ′(G) ≥ Δ. Le théorème de Vizing fournit la borne supérieure et enferme donc le résultat entre deux entiers consécutifs : .
Un graphe est dit de classe 1 lorsque χ′(G) = Δ, et de classe 2 lorsque χ′(G) = Δ + 1. Le théorème porte sur les graphes simples, donc sans boucle ni arêtes multiples. Publié en 1964, il est dû au mathématicien soviétique et ukrainien Vadim G. Vizing (1937–2017).
Le principe
Si G est un graphe simple et si son degré maximal est noté Δ, alors ses arêtes admettent une coloration propre avec au plus Δ + 1 couleurs. Comme les Δ arêtes incidentes à un sommet de degré maximal exigent déjà Δ couleurs distinctes, on obtient . Ces deux possibilités définissent respectivement les classes 1 et 2.
Quand l'utiliser
Le résultat s’applique à un graphe simple. Il faut connaître les sommets, les arêtes et le degré de chaque sommet pour déterminer le degré maximal Δ. Une coloration candidate doit ensuite être contrôlée à chaque sommet : toutes les arêtes qui y arrivent doivent avoir des couleurs deux à deux distinctes. Le théorème garantit alors l’existence d’une coloration utilisant au plus Δ + 1 couleurs.
Un dessin comportant une boucle ou deux arêtes parallèles entre les mêmes sommets n’est pas un graphe simple. Le théorème de Vizing sous cette forme ne peut pas y être invoqué, même si une coloration particulière semble fonctionner. Il faut supprimer cette ambiguïté dans le modèle ou employer un résultat adapté aux multigraphes.
Un exemple, pas à pas
Données. On considère le cycle à cinq sommets, noté C5 : cinq sommets forment un pentagone et cinq arêtes relient les voisins successifs. Chaque sommet appartient exactement à deux arêtes.
1. Tous les sommets ont le degré 2. Le degré maximal du graphe vaut donc Δ = 2, et au moins deux couleurs sont nécessaires.
2. Essayons deux couleurs. Après avoir coloré quatre arêtes en alternance, la cinquième touche à ses deux extrémités une arête de chacune des deux couleurs. Aucune couleur n’est disponible : deux couleurs ne suffisent pas.
3. Avec trois couleurs, on peut suivre le pentagone dans l’ordre avec la suite rouge, jaune, rouge, jaune, noir. À chaque sommet, les deux arêtes incidentes ont des couleurs différentes.
4. La coloration à trois couleurs existe et l’essai à deux couleurs a échoué. Ainsi, . Le cycle C5 est de classe 2.
Contrôle. Il suffit de parcourir les cinq sommets et de comparer les deux arêtes qui s’y rencontrent. La figure matérialise cette vérification locale et la couleur supplémentaire nécessaire pour fermer un cycle impair.
En pratique
Pour construire une coloration d’arêtes, on calcule d’abord Δ. Le théorème limite alors la recherche à Δ ou Δ + 1 couleurs. Tester davantage de couleurs peut simplifier un brouillon, mais ne peut pas être nécessaire pour un graphe simple.
Pour vérifier une coloration proposée, on inspecte chaque sommet et on cherche deux arêtes incidentes de même couleur. L’absence de conflit prouve que la coloration est propre ; elle ne prouve qu’elle est minimale que si une borne inférieure correspondante est également établie.
Pour classer le graphe, on tente d’abord d’atteindre la borne Δ. Si une coloration propre à Δ couleurs est trouvée, le graphe est de classe 1. Sinon, il faut démontrer l’impossibilité avant de conclure à la classe 2 ; l’échec d’un seul essai ne suffit pas.
À ne pas confondre
Avec la coloration des sommets. La coloration des sommets interdit une même couleur à deux sommets reliés ; Vizing colore les arêtes et compare celles qui partagent un sommet. Dans un triangle, colorer les trois sommets ou les trois arêtes demande trois couleurs, mais cette coïncidence ne confond pas les deux problèmes.
Avec le degré maximal. Le nombre Δ mesure combien d’arêtes se rencontrent au sommet le plus chargé ; χ′(G) mesure le minimum de couleurs pour toutes les arêtes. Sur le cycle C5, Δ vaut 2 alors que χ′(G) vaut 3 : les deux nombres ne sont pas toujours égaux.
Limites et pièges
La simplicité est une hypothèse. La présence d’une boucle ou d’arêtes parallèles sort du cadre annoncé. Le symptôme est visible directement dans la liste des extrémités. Il faut alors reformuler le graphe ou utiliser un théorème propre aux multigraphes, pas appliquer mécaniquement la borne Δ + 1.
La borne ne donne pas la classe. Vizing réduit le choix à deux valeurs, mais ne décide pas à lui seul laquelle convient. Une coloration à Δ couleurs prouve la classe 1 ; pour la classe 2, il faut aussi exclure toutes les colorations à Δ couleurs. Le cycle C5 fournit cette exclusion par l’alternance impossible.
Cas sans arête. Si le graphe ne possède aucune arête, son degré maximal vaut 0 et aucune couleur n’est nécessaire. Avec la convention χ′(G) = 0, il relève de la classe 1. Il ne faut pas lui attribuer une couleur au seul motif que la borne supérieure vaut Δ + 1 = 1.
Minimalité à justifier. Trouver une coloration propre avec Δ + 1 couleurs montre seulement que cette borne est atteignable. Si une autre coloration utilise Δ couleurs, le graphe est de classe 1. Il faut donc distinguer le nombre de couleurs d’un essai du minimum χ′(G).
Pour aller plus loin
degré d'un sommet d'un graphe — Précise le calcul local dont le maximum fournit la borne Δ.
coloration d'un graphe — Développe la coloration des sommets et permet de la distinguer de celle des arêtes.
nombre chromatique d'un graphe — Éclaire le minimum de couleurs côté sommets, voisin mais différent de χ′(G).
Graphe complet — Offre une famille structurée sur laquelle comparer degré maximal et contraintes de coloration.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres