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é
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é
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
- ↑ (Menger 1927)
Bibliographie
Articles
- (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
- (en) J. A. Bondy et U.S.R. Murty, Graph Theory with Applications, libre d'accès uniquement pour l'usage personnel
- Portail des mathématiques
- Portail de l'informatique théorique