Théorème de 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

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

Théorème de Menger — Soient G un graphe fini non-orienté, et s et t deux sommets distincts. Le nombre minimum d'arêtes à supprimer pour déconnecter s et t est égal au nombre maximum de chemins arête-disjoints de G reliant s et t.


Résultat liéModifier

Le théorème d'Erdős-Pósa est de même nature que celui de Menger, il relie la taille maximale d'une collection de cycles disjoints à la taille minimale d'un coupe-cycles de sommets (feedback vertex set).

Notes et référencesModifier

BibliographieModifier

ArticlesModifier

Manuels et vulgarisationModifier