Théorème de Menger
Pour les articles homonymes, voir Menger.
Cet article est une ébauche concernant la théorie des graphes.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
En théorie des graphes, le théorème de Menger est à l'origine du théorème flot-max/coupe-min qui le généralise. Il fut prouvé par Karl Menger en 1927[1].
ÉnoncéModifier
Le théorème de Menger s'énonce ainsi :
Théorème de Menger — Le nombre minimum d'arêtes dont la suppression déconnecte deux sommets s et t est égal au nombre maximum de chemins arête-disjoints reliant s et t.
Résultat liéModifier
Le théorème d'Erdős et Pósa est de même nature que celui de Menger, il relie la taille maximale d'une collection de cycles disjoints à la taille minimale d'un coupe-cycles de sommets (feedback vertex set).
Notes et référencesModifier
BibliographieModifier
ArticlesModifier
- (de) Karl Menger, « Zur allgemeinen Kurventheorie », Fund. Math., vol. 10, , p. 96-115
- Ron Aharoni et Eli Berger, « Menger's Theorem for infinite graphs », Inventiones Mathematicae, vol. 176, , p. 1-62 (DOI 10.1007/s00222-008-0157-3, lire en ligne)
- R. Halin, « A note on Menger's theorem for infinite locally finite graphs », Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, vol. 40, , p. 111-114 (DOI 10.1007/BF02993589, Math Reviews 0335355).
Manuels et vulgarisationModifier
- (en) J. A. Bondy et U.S.R. Murty, Graph Theory with Applications, libre d'accès uniquement pour l'usage personnel
