Théorème de Menger
Un article de Wikipédia, l'encyclopédie libre.
 |
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.
Le théorème de Menger s'énonce ainsi : 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.
[modifier] Références
- (en) J. A. Bondy et U.S.R. Murty, Graph Theory with Applications, libre d'accès uniquement pour l'usage personnel
- (en) Reinhard Diestel, Graph Theory
