Théorème de Menger

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir 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é[modifier | modifier le code]

Le théorème de Menger s'énonce ainsi :

Théorème de Menger — Le nombre minimum d'arêtes dont la suppression déconnecte deux sommets s et t est égal au nombre maximum de chemins arête-disjoints reliant s et t.

Preuve[modifier | modifier le code]

Généralisation[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  1. (Menger 1927)

Bibliographie[modifier | modifier le code]

Articles[modifier | modifier le code]

  • (de) Karl Menger, « Zur allgemeinen Kurventheorie », Fund. Math., vol. 10,‎ 1927, p. 96-115
  • Ron Aharoni, « 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).

Manuels et vulgarisation[modifier | modifier le code]