Menger's theorem
id:
menger-s-theorem-282-10783979
title:
Menger's theorem
text:
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.
brand slug:
wiki
category slug:
encyclopedia
description:
Theorem in graph theory
original url:
https://en.wikipedia.org/wiki/Menger%27s_theorem
date created:
date modified:
2024-04-07T04:43:50Z
main entity:
{"identifier":"Q928813","url":"https://www.wikidata.org/entity/Q928813"}
image:
fields total:
13
integrity:
14