Flow value is at most cut capacity
Builds on Directed graphFlow network
Statement
Let be a flow network on a finite directed graph. It has a source , a sink , and a capacity on each edge .
Let be a flow in . That is, for each edge , and at each vertex other than and the flow in equals the flow out.
Let be a cut. That is, and are disjoint, and . The capacity of the cut is the sum of over the edges that go from to .
Then the value of is at most the capacity of the cut.
Reading path
To understand this page from the ground up, read these 3 pages in order. The foundations come first.
Show the path as a graph
- no evidence level
- Directed graph definition
- Flow network concept
- Flow value is at most cut capacity statement
Further reading
- Web https://github.com/mitchkeller/applied-combinatorics/blob/ebd95d6bd59e23c633c65cf560bcb93efa912aae/source/s_networkflow_flows-cuts.ptx#L36, source/s_networkflow_flows-cuts.ptx:36
About this page
| Tag | 7TQK5EC8B8 |
|---|---|
| URI | m2://7TQK5EC8B8 |
| Kind | statement, theorem |
| Writing | W1 stated |
| MSC | 05C21, 90B10, 90C35 |
| Status | This copy of the site has no build data. Run m2 status 7TQK5EC8B8. |
| Uses | Directed graph, Flow network |
| Changed | 4 November 2026 |
Markdown · JSON · Edit on GitHub
What this page needs for W2
- edge about out: the concepts that the statement is about (0 of 1)
- edge proves in: at least one proof node (0 of 1)
- edge instance_of or illustrates in: one example that shows the statement at work (0 of 1)
- explanation L2 (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.
What links here
No page links to this page yet.