Theoreme de Vizing

Theoreme de Vizing

Théorème de Vizing

Le théorème de Vizing est un théorème de la théorie des graphes qui stipule que la coloration des arêtes d'un graphe G peut s'effectuer à l'aide de ρ+1 couleurs au maximum, où ρ est le degré maximal du graphe G.

Démonstration

Montrons la propriété par récurrence sur le nombre d'arêtes du graphe G, noté m. Il s'agit donc de montrer qu'on peut colorier tout graphe à n sommets déterminés à l'avance avec au plus ρ+1 couleurs, où ρ est le degré maximal du graphe considéré.

  • m = 0 :

Un graphe à 0 arête peut se colorer avec une couleur.

  • m = m+1 :

Supposons la propriété vraie pour un entier m quelconque, et montrons qu'elle reste vraie pour l'entier m+1. Soit G un graphe à m+1 arêtes. Enlevons une arête μ de ce graphe. On obtient un graphe G' à m arêtes dont on peut colorier les arêtes, d'après l'hypothèse de récurrence. Essayons à présent de « remettre » μ dans G' pour obtenir à nouveau le graphe G.

On appellera A et B1 les sommets initialement reliés par l'arête μ.

Nécessairement, puisque A est de degré inférieur ou égal à ρ, il existe une couleur parmi les ρ+1 disponibles qui n'est pas utilisée pour colorier les arêtes incidentes au sommet A. De même, il existe une couleur parmi les ρ+1 qui n'est pas utilisée pour la coloration des arêtes de B1.

  • Cas 1 :

Si on peut trouver une couleur non utilisée à la fois pour la coloration des arêtes adjacentes à A et pour la coloration des arêtes adjacentes à B1, alors il suffit de choisir cette couleur pour μ et de replacer cette arête une fois coloriée à son emplacement initial dans G.

  • Cas 2 :

Si les couleurs manquant à A sont présentes au sommet B1 et réciproquement, notons a une des couleurs manquant à A et b1 une couleur manquant à B1. Examinons la chaîne de Kempe associée aux couleurs a et b1 et partant de B1 : H(a,b1). Si cette chaîne ne relie pas A à B1, on échange les deux couleurs dans cette chaîne (les arêtes du graphe G' restent ainsi correctement colorées) puis on choisit la couleur a pour μ et on replace cette arête à son emplacement initial.

  • Cas 3 :

Si en plus de ne pouvoir trouver une couleur manquant à A et à B1, la chaîne de Kempe H(a,b1) relie ces deux sommets, on effectue les opérations suivantes : on identifie l'arête de couleur b1 incidente à A (appelons la μ') et on appelle B2 le sommet à l'autre extrémité de l'arête en question. On extrait cette même arête d'entre A et B2 pour la placer entre A et B1. μ' est à présent l'arête que l'on doit replacer pour obtenir à nouveau le graphe G. Il faut alors procéder comme précédemment pour trouver la couleur adéquate avec laquelle colorer μ'. Il se peut que l'on revienne à chaque fois dans le « cas 3 ».

Au bout d'un certain temps (ρ fois au maximum), il arrive donc que la couleur manquant au sommet Bi ait déjà été la couleur manquant à un sommet Bk (k<i). Notons que l'on a même k < i-1 étant donné que l'on vient juste de retirer la couleur bi-1 au sommet Bi.

Ainsi on a une chaîne de Kempe H(a,bk) qui part de A, qui rejoint Bk+1, et dont les sommets ont tous la couleur bk (sauf Bk+1 puisqu'on a justement retiré l'arête de couleur bk adjacente à ce somment pour la mettre entre Bk et A. On a vu que Bi n'avait pas d'arête adjacente de couleur bk, partant de quoi on affirme que Bi n'est pas sur la chaîne de Kempe H(a,bk) que l'on vient de mentionner.

D'autre part, on sait que le sommet Bi a une arête adjacente de couleur a et que de ce fait il appartient à une autre chaîne de Kempe H'(a,bk), disjointe de la chaîne H(a,bk) (H'(a,bk) peut être réduite à une simple arête de couleur a). Il suffit alors d'intervertir les couleurs des arêtes de H'(a,bk) et de relier Bi et A avec un arête de couleur a pour ainsi reconstruire le graphe G coloré (lors de cette dernière opération, on aura relié les chaînes H(a,bk) et H'(a,bk) ).

  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Th%C3%A9or%C3%A8me de Vizing ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Theoreme de Vizing de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Théorème de Vizing — Le théorème de Vizing est un théorème de la théorie des graphes qui stipule que la coloration des arêtes d un graphe G peut s effectuer à l aide de Δ+1 couleurs au maximum, où Δ est le degré maximal du graphe G. Démonstration Montrons la… …   Wikipédia en Français

  • Theoreme quatre couleurs — Coloration de graphe En mathématiques, la coloration de graphe renvoie à un champ d études appartenant à la théorie des graphes. Il s agit de déterminer combien de couleurs différentes suffisent pour colorer entièrement un graphe de telle façon… …   Wikipédia en Français

  • Coloration de graphe (arêtes) — Coloration des arêtes d un graphe Coloration des arêtes du graphe de Desargues avec trois couleurs. La coloration des arêtes d’un graphe entre dans la catégorie plus générale des problèmes de coloration de graphes, le but étant d’attribuer une… …   Wikipédia en Français

  • Coloration des aretes d'un graphe — Coloration des arêtes d un graphe Coloration des arêtes du graphe de Desargues avec trois couleurs. La coloration des arêtes d’un graphe entre dans la catégorie plus générale des problèmes de coloration de graphes, le but étant d’attribuer une… …   Wikipédia en Français

  • Coloration des arêtes d'un graphe — Coloration des arêtes du graphe de Desargues avec trois couleurs. La coloration des arêtes d’un graphe entre dans la catégorie plus générale des problèmes de coloration de graphes, le but étant d’attribuer une couleur à chaque arête du graphe… …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Coloration De Graphe — En mathématiques, la coloration de graphe renvoie à un champ d études appartenant à la théorie des graphes. Il s agit de déterminer combien de couleurs différentes suffisent pour colorer entièrement un graphe de telle façon qu aucun nœud du… …   Wikipédia en Français

  • Nombre chromatique — Coloration de graphe En mathématiques, la coloration de graphe renvoie à un champ d études appartenant à la théorie des graphes. Il s agit de déterminer combien de couleurs différentes suffisent pour colorer entièrement un graphe de telle façon… …   Wikipédia en Français

  • Coloration de graphe — En théorie des graphes, colorer un graphe signifie attribuer une couleur à chacun de ses sommets de manière à ce que deux sommets reliés par une arête soient de couleur différente. Est souvent recherchée l utilisation d un nombre minimal de… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”