∑
MathTCG
#085 / 200•Foundations•MathTCG #085 / 500•★Commune•⊦Maths Discrètes•Théorème

Théorème des mariages de Hall

Période historique : 1935 (Philip Hall)

La condition nécessaire et suffisante pour coupler entièrement deux ensembles d'éléments compatibles.

Contenu & Formulation mathématique

Hypothèses nécessaires
Graphe biparti fini sans arêtes multiples.
Énoncé formel
Un graphe biparti G = (X ∪ Y, E) admet un couplage couvrant X si et seulement si tout sous-ensemble S de X possède un voisinage N(S) au moins aussi grand que S.
∀S⊆X,  ∣N(S)∣≥∣S∣  ⟺  ∃ couplage complet de X dans Y\forall S \subseteq X, \; |N(S)| \ge |S| \iff \exists \text{ couplage complet de } X \text{ dans } Y

Genèse & Portée historique

Théorème fondamental de combinatoire énonçant la condition pour qu'un graphe biparti admette un couplage complet couvrant une partition : chaque groupe de k éléments doit avoir au moins k voisins compatibles au total. Utilisé pour les affectations optimales et l'analyse de réseaux.

Philip Hall l'énonça en 1935 sous forme d'énigme récréative : 'À quelle condition un groupe d'hommes et de femmes peut-il être marié de sorte que chacun épouse une personne qu'il connaît ?'

« Pour que chacun trouve son partenaire sans dispute, nul groupe ne doit se partager trop peu d'élus. »

Filiations & Relations conceptuelles (1)

Repose sur le concept#027

Graphe

Caractérise l'existence d'un couplage parfait dans les graphes bipartis.

Objet de collection MathTCG

#085
★Commune
⊦

Théorème des mariages de Hall

Maths Discrètes•THÉORÈME

Hypothèses : Graphe biparti fini sans arêtes multiples.

∀S⊆X,  ∣N(S)∣≥∣S∣  ⟺  ∃ couplage complet de X dans Y\forall S \subseteq X, \; |N(S)| \ge |S| \iff \exists \text{ couplage complet de } X \text{ dans } Y
1935 (Philip Hall)

Dans l'édition physique et numérique de MathTCG, cette carte appartient à l'extension Foundations.

Extension : Foundations (#085 / 200)
Numéro global MathTCG : MathTCG #085 / 500
Rareté officielle : Commune (★)
Domaine théorique : Maths Discrètes
Identifiant pérenne : theoreme-des-mariages-de-hall
Consulter mon classeurExplorer tout le recueil