Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Théorème de Menger
Résumé
In the mathematical discipline of graph theory, Menger's theorem says that in a finite graph, the size of a minimum cut set is equal to the maximum number of disjoint paths that can be found between any pair of vertices.
Proved by Karl Menger in 1927, it characterizes the connectivity of a graph.
It is generalized by the max-flow min-cut theorem, which is a weighted, edge version, and which in turn is a special case of the strong duality theorem for linear programs.
The edge-connectivity version of Menger's theorem is as follows:
Let G be a finite undirected graph and x and y two distinct vertices. Then the size of the minimum edge cut for x and y (the minimum number of edges whose removal disconnects x and y) is equal to the maximum number of pairwise edge-independent paths from x to y.
Extended to all pairs: a graph is k-edge-connected (it remains connected after removing fewer than k edges) if and only if every pair of vertices has k edge-disjoint paths in between.
The vertex-connectivity statement of Menger's theorem is as follows:
Let G be a finite undirected graph and x and y two nonadjacent vertices. Then the size of the minimum vertex cut for x and y (the minimum number of vertices, distinct from x and y, whose removal disconnects x and y) is equal to the maximum number of pairwise internally vertex-disjoint paths from x to y.
Extended to all pairs: a graph is k-vertex-connected (it has more than k vertices and it remains connected after removing fewer than k vertices) if and only if every pair of vertices has at least k internally vertex-disjoint paths in between.
All these statements (in both edge and vertex versions) remain true in directed graphs (when considering directed paths).
Most direct proofs consider a more general statement to allow proving it by induction. It is also convenient to use definitions that include some degenerate cases.
The following proof for undirected graphs works without change for directed graphs or multi-graphs, provided we take path to mean directed path.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.