Network flows
Incomplete
Terminology
Section titled “Terminology”Capacity
Section titled “Capacity”- The capacity of an edge is the weight of the edge.
- It can be thought of as the maximum flow that can pass through that edge.
A cut is the is a line which divides the source(s) from the sink(s). The capacity of a cut is the sum of the capacities of the edges crossing the cut from source side to sink side.
Minimum cut theorem
Section titled “Minimum cut theorem”The minimum cut theorem is able to tell us the maximum flow in a flow network.
How to use it:
- Find all possible cuts in the network
- Calculate the capacity of each cut
- Find the cut which gives the minimum capacity
- This capacity is the maximum flow in the network
Analogy: water tap
Section titled “Analogy: water tap”Supersources
Section titled “Supersources”A supersource is a single source node which has an infinite capacity edge to each of the original sources.
Supersinks
Section titled “Supersinks”A supersink is a single sink node which has an infinite capacity edge from each of the original sinks.