Théorème de Gallai-Hasse-Roy-Vitaver
From Wikipedia, the free encyclopedia
En théorie des graphes, le théorème de Gallai-Hasse-Roy-Vitaver énonce une dualité entre les colorations des sommets d'un graphe non orienté donné et les orientations de ses arêtes. Il dit que le nombre minimum de couleurs nécessaires pour colorer un graphe G (son nombre chromatique) est égal à 1 plus la longueur du plus long chemin dans une orientation de G choisie pour minimiser la longueur de ce chemin[1]. Les orientations pour lesquelles le chemin le plus long a une longueur minimale comprennent toujours au moins une orientation acyclique[2].
Une des conséquences du théorème est que toute orientation d'un graphe de nombre chromatique k contient un chemin orienté simple avec k sommets[3] ; ce chemin peut être forcé à commencer en n'importe quel sommet à partir duquel on peut atteindre tous les autres sommets du graphe orienté[4],[5].
- Un graphe biparti peut être orienté d'un côté de la bipartition vers l'autre; le plus long chemin dans cette orientation n'a que deux sommets. Réciproquement, si un graphe est orienté sans avoir de chemin à trois sommets, alors chaque sommet doit être soit une source (sans arêtes entrantes) soit un puits (sans arêtes sortantes) et la partition des sommets en sources et puits montre qu'il est biparti.
- Dans toute orientation d'un graphe cycle de longueur impaire, l'orientation des arêtes ne peut pas alterner le long du cycle, donc il y a deux arêtes consécutives qui forment un chemin à trois sommets. Ceci correspond au fait que le nombre chromatique d'un cycle impair est trois.
Démonstration
On prouve d'abord que le nombre chromatique est supérieur ou égal au nombre minimum de sommets dans un chemin de longueur maximale. Supposons qu'un graphe donné ait une coloration avec k couleurs, pour un certain nombre k . Il peut alors être orienté de manière acyclique en numérotant les couleurs et en dirigeant chaque arête de son extrémité de numéro inférieur vers l'extrémité de numéro supérieur. Avec cette orientation, les nombres augmentent strictement le long de chaque chemin orienté, et donc il contient au plus k sommets.
On prouve réciproquement que le nombre chromatique est inférieur ou égal au nombre minimum de sommets dans un chemin le plus long. Supposons qu'un graphe donné ait une orientation avec au plus k sommets par chemin orienté simple, pour un entier k . Les sommets du graphe peuvent alors être colorés avec k couleurs en choisissant un sous- graphe acyclique maximal pour l'orientation, puis en colorant chaque sommet par la longueur du chemin le plus long dans le sous-graphe choisi qui se termine en ce sommet. Chaque arête du sous-graphe est orientée d'un sommet avec un nombre inférieur à un sommet avec un nombre plus élevé, et est donc correctement colorée. Pour chaque arête qui n'est pas dans le sous-graphe, il existe un chemin du sous-graphe reliant les deux mêmes sommets dans la direction opposée, sinon l'arête aurait pu être incluse dans le sous-graphe choisi; par conséquent, l'arête est orientée d'un entier plus grand vers un entier plus petit et est à nouveau correctement colorée[1].
La preuve de ce théorème a été utilisée comme test dans le cadre d'une formalisation du l'induction mathématique par Youri Matiiassevitch[6].
