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 — Soient G un graphe fini non-orienté, et s et t deux sommets distincts. Le nombre minimum d'arêtes à supprimer pour déconnecter s et t est égal au nombre maximum de chemins arête-disjoints de G reliant s et t.
Résultat lié modifier
Le théorème d'Erdős-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érences modifier
Bibliographie modifier
Articles modifier
- (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, MR 0335355).
Manuels et vulgarisation modifier
- (en) J. A. Bondy et U.S.R. Murty, Graph Theory with Applications, libre d'accès uniquement pour l'usage personnel
