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,‎ 1927, p. 96-115
Ron Aharoni et Eli Berger, « Menger's Theorem for infinite graphs », Inventiones Mathematicae, vol. 176,‎ 2009, 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,‎ 1974, p. 111-114 (DOI 10.1007/BF02993589, MR 0335355).