Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Théorème de Vizing
Résumé
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. Il est dû à Vadim G. Vizing.
Une coloration des arêtes d'un graphe consiste à attribuer à chaque arête une couleur, en évitant que deux arêtes ayant une extrémité commune soient de la même couleur. On note χ′(G) le nombre minimum de couleur nécessaire pour avoir une coloration des arêtes.
On remarque que χ′(G) est forcement supérieure ou égal au degré maximum des nœuds (noté Δ), en effet toutes les arêtes adjacentes à ce nœud doivent avoir des couleurs différentes.
Le théorème stipule qu'étant donné un graphe G, le nombre χ′(G) est égal ou bien à Δ ou bien à Δ+1.
D'après la remarque de la section précédente, ce résultat est surtout important comme borne supérieure sur χ′.
File:Desargues graph 3color edge.svg|Un graphe où χ′(G)=Δ.
File:Class-2-planar-3-regular.svg|Un graphe où χ′(G)=Δ+1.
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 colorer 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 colorer 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 colorer 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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.