Théorème de Hall

Théorème de Hall
Page d'aide sur l'homonymie Ne pas confondre avec le théorème de Hall en théorie des groupes, ni avec le problème des ménages.

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 (en)[1] et a été à l'origine de la théorie du couplage dans les graphes[2].

Généralités

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, xk appartienne à Ak.

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

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

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 Ak 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.

Application en théorie des graphes

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.

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.

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

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 : on peut convaincre en temps polynomial que la réponse est positive. Ce problème est aussi 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.

Notes

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

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Théorème de Hall de Wikipédia en français (auteurs)

Игры ⚽ Нужна курсовая?

Regardez d'autres dictionnaires:

  • 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… …   Wikipédia en Français

  • 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… …   Wikipédia en Français

  • Theoreme flot-max/coupe-min — Théorème flot max/coupe min Le théorème flot max/coupe min est un théorème de la théorie des graphes. Il généralise le théorème de König et le théorème de Hall (dans les graphes bipartis) et le théorème de Menger (dans les graphes quelconques).… …   Wikipédia en Français

  • Théorème flot-max/coupe-min — Le théorème flot max/coupe min est un théorème de la théorie des graphes. Il généralise le théorème de König et le théorème de Hall (dans les graphes bipartis) et le théorème de Menger (dans les graphes quelconques). Il révèle que le calcul d une …   Wikipédia en Français

  • Theoreme de Maschke — Théorème de Maschke Heinrich Maschke En mathématiques et plus précisément en algèbre, le théorème de Maschke est un des théorèmes fondamentaux de la théorie de la représentation des groupes. Ce théorème permet, si la caractéristique du corps est… …   Wikipédia en Français

  • Théorème de maschke — Heinrich Maschke En mathématiques et plus précisément en algèbre, le théorème de Maschke est un des théorèmes fondamentaux de la théorie de la représentation des groupes. Ce théorème permet, si la caractéristique du corps est soit nulle soit… …   Wikipédia en Français

  • Theoreme de Burnside (probleme de 1902) — Théorème de Burnside (problème de 1902) William Burnside En mathématiques, et plus précisément dans le contexte de la théorie des groupes finis, le théorème de Burnside traite des représentations d un groupe répondant aux critères du problème de… …   Wikipédia en Français

  • Theoreme des quatre sommets — Théorème des quatre sommets Une ellipse (en rouge) et sa développée (en bleu), montrant les 4 sommets annulant k , chacun d eux correspondant à un cusp de la développée. Le théorème des 4 sommets consititue un résultat remarquable de géométrie… …   Wikipédia en Français

  • Théorème de Burnside (problème de Burnside 1902) — Théorème de Burnside (problème de 1902) William Burnside En mathématiques, et plus précisément dans le contexte de la théorie des groupes finis, le théorème de Burnside traite des représentations d un groupe répondant aux critères du problème de… …   Wikipédia en Français

  • Théorème de burnside (problème de 1902) — William Burnside En mathématiques, et plus précisément dans le contexte de la théorie des groupes finis, le théorème de Burnside traite des représentations d un groupe répondant aux critères du problème de Burnside. Ce théorème stipule que toute… …   Wikipédia en Français

Share the article and excerpts

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