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]

Bibliographie[modifier | modifier le code]

Articles[modifier | modifier le code]

Manuels et vulgarisation[modifier | modifier le code]