Théorème de Menger
Un article de Wikipédia, l'encyclopédie libre.
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
Graph Theory with Applications, J.A. Bondy and U.S.R. Murty, libre d'accès uniquement pour l'usage personnel http://www.ecp6.jussieu.fr/pageperso/bondy/bondy.html ou consulter le Graph Theory de Diestel, http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/GraphTheoryIII.counted.pdf
