Accueil🇫🇷Chercher

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é

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é

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érences

Bibliographie

Articles

Manuels et vulgarisation

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.