Théoreme de Hall

Théorème de Hall

Le théorème de Hall donne une condition nécessaire et suffisante à l'existence d'un couplage parfait dans un graphe biparti (un couplage parfait dans un graphe ayant un nombre pair 2n de sommets est un sous-ensemble de n arêtes deux-à-deux disjointes du graphe, ainsi chaque sommet du graphe est incident à exactement une arête du couplage).

Théorème de Hall (1935) - Un graphe biparti G=(U,V;E) admet un couplage parfait si et seulement si pour tout sous-ensemble X de U (de V, respectivement), le nombre de sommets de V (de U, respectivement) adjacents à un sommet de X est supérieur ou égal à la cardinalité de X.

Ce résultat généralise le fait, déjà remarqué en 1914 par König, que les graphes bipartis réguliers (c'est-à-dire k-régulier pour un entier k, ceci voulant dire que chaque sommet du graphe est incident à exactement k arêtes) admettent un couplage parfait. Par-ailleurs, le théorème de Tutte généralise celui de Hall par une condition nécessaire et suffisante pour tous les graphes. Le Théorème de Hall est en fait un cas particulier du Théorème flot-max/coupe-min, dans les graphes constitués d'un graphe biparti G=(U,V;E) plus un sommet source et un sommet puits, la source étant relié à tous les sommets de U tandis que tous les sommets de V sont reliés au sommet puits.

Le Théorème de Hall n'est pas difficile à montrer (il en existe au-moins trois courtes preuves voir les références).

L'intérêt (a posteriori) du théorème est de fournir un problème de décision dans NP, en l'occurrence déterminer si un graphe admet ou non un couplage parfait, qui est à la fois dans co-NP, puisqu'à l'aide d'un ensemble X violant la condition, on peut vérifier en temps polynomial que son voisinage N(X) est tel que |N(X)|<|X|, et donc convaincre que la réponse au problème de décision est négative.

Références

Graph Theory with Applications, J.A. Bondy and U.S.R. Murty, pour l'usage personnel libre sur http://www.ecp6.jussieu.fr/pageperso/bondy/bondy.html

Graph Theory, de Reinhard Diestel, libre en version électronique à http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/GraphTheoryIII.counted.pdf).

Ce document provient de « Th%C3%A9or%C3%A8me de Hall ».