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].
Pour les articles homonymes, voir Menger.
É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, Math Reviews 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
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.