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.
image illustrant la théorie des graphes
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é[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,‎ , p. 96-115
  • Ron Aharoni, « 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).

Manuels et vulgarisation[modifier | modifier le code]