Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Théorème de Hall
Résumé
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.
On appelle système de représentants distincts d'une suite de n ensembles finis , toute suite de n éléments distincts tels que pour tout , appartienne à .
La condition est clairement nécessaire. Parmi les diverses preuves qu'elle est suffisante, celle qui semble la plus naturelle est due à Easterfield et a été redécouverte par Halmos et Vaughan.
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 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.
Un couplage parfait dans un graphe ayant un nombre pair 2n de sommets est un ensemble de n arêtes du graphe, deux-à-deux disjointes et telles que 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 à X est supérieur ou égal à la cardinalité de X.
Le théorème de Hall a été démontré par Philip Hall et a été à l'origine de la théorie du couplage dans les graphes.
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 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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.