Théorème de Menger
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
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
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.