Théorème de Hall

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En mathématiques, le théorème de Hall ou lemme des mariages est un résultat combinatoire qui donne une condition nécessaire et suffisante, sur une famille d'ensembles finis, pour qu'il soit possible de choisir des éléments distincts, un par ensemble. Il a été démontré par Philip Hall et a été à l'origine de la théorie du couplage dans les graphes.

Formulation combinatoire[modifier | modifier le code]

Énoncé[modifier | modifier le code]

On appelle système de représentants distincts d'une suite de n ensembles finis A_1,\ldots,A_n, toute suite de n éléments x_1,\ldots,x_n distincts tels que pour tout k, x_k appartienne à A_k.

Théorème[1] — A_1,\ldots,A_n possède un système de représentants distincts si et seulement si, pour tout m\in\{1,\ldots,n\}, la réunion de m quelconques des A_i contient au moins m éléments.

Remarques[modifier | modifier le code]

La condition est clairement nécessaire. Parmi les diverses preuves qu'elle est suffisante, celle qui semble la plus naturelle[1] est due à Easterfield[2] et a été redécouverte par Halmos et Vaughan[3].

Son nom folklorique de « lemme des mariages » est lié à l'interprétation suivante d'un système de représentants distincts : étant données n filles, si A_k désigne l'ensemble des partis envisageables pour la k-ième, un système de représentants distincts correspond à un mariage collectif tenant compte de ces contraintes.

Formulation de la théorie des graphes[modifier | modifier le code]

Énoncé[modifier | modifier le code]

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 pour les graphes - 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.

Historique et généralisations[modifier | modifier le code]

Le théorème de Hall a été démontré par Philip Hall[4] et a été à l'origine de la théorie du couplage dans les graphes[1].

Ce résultat généralise le fait, déjà remarqué en 1914 par König, que les graphes bipartis réguliers admettent un couplage parfait. Par-ailleurs, le théorème de Tutte (en) 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ée à tous les sommets de U, tandis que tous les sommets de V sont reliés au sommet puits.

Preuves[modifier | modifier le code]

Ce théorème de Hall n'est pas difficile à démontrer, il en existe au moins trois courtes preuves[5],[6].

Aspects algorithmiques[modifier | modifier le code]

Le problème qui consiste à savoir, étant donné un graphe biparti, si il existe un couplage parfait peut-être résolu en temps polynomial. Mais même sans connaître ce fait, on sait qu'il appartient à la classe NP et d'après le théorème de Hall, à la classe 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.

Notes et références[modifier | modifier le code]

  1. a, b et c M. Aigner et G. Ziegler, Raisonnements divins, Springer, 2006 (ISBN 2-287-33845-4) p.174-175
  2. (en) T. E. Easterfield, « A combinatorial algorithm », Journal of the London Math. Soc., vol. 21, no 3,‎ , p. 219-226
  3. (en) P. R. Halmos et H. E. Vaughan, « The marriage problem », Amer. J. Math., vol. 72,‎ , p. 214-215
  4. (en) P. Hall, « On Representatives of Subsets », J. London Math. Soc., vol. 10, no 1,‎ , p. 26-30
  5. (en) J.A. Bondy et U.S.R. Murty, Graph Theory with Applications
  6. (en) Reinhard Diestel (de), Graph Theory

Articles connexes[modifier | modifier le code]

Lien externe[modifier | modifier le code]