(W8) Network Flow Flashcards
(18 cards)
Describe a flow network?
- Single source vertex, often denoted by s, which only has outgoing edges.
- Single sink/target vertex, denoted by t, which only has incoming edges.
Each edge has a capacity (non-negative, usually integers)
2 Properties of a Flow Network
- For each edge, the flow is bound by the capacity
- Except for source/sink, for each vertex flow in = flow out
What is a Cut of a Flow Graph?
Cut (S,T) of a flow partitions the vertices into two disjoint sets S and T
Source is in S, Sink is in T
What is the Cut-Set
The set of the edges that cross the graph
Capacity vs Flow of a Cut
Capacity is the sum of all capacity of outgoing edged
Flow is outbound flow - inbound flow
Min-cut Max-flow Theorem big idea + proof
the flow of every cut is the same is equal to the max-flow
- Remember - the 1st cut must include the source and the 2nd cut most include target
- Therefore -> the flow over the cut (i.e. the edges that connect A to B) must equal the total flow.
- Think about this logically, the flow over a cut that disconnects A to B would equal the total flow
What is the Min-Cut
The edges reachable from Source in the residual network (so extra capacity > 0)
The smallest capacity of edges that you’d need to remove
This effectively represents the bottleneck - the cut-set from the min-cut is the edges that are at max capacity
What does the capacity of the min-cut equal
The max-flow of the entire graph
Example Question: Prove the netflow out of s is equal to the netflow into t
We know the flow of every cut is equal to the flow of the network
Flow of the cut {s} \ V (flow out of s) = cut {t} \ V (flow into t) (as per flow conservation principle)
What is the Residual Network in FordFulkerson?
Same vertices as the original network
For every directed edge a -> b, we add two edges to the residual network
Forward: edge in the same direction with the remaining capacity (how much more can we push down this path)
Backward: basically the flow in the forward path - think about this as the flow you could push backwards
What is an Augmenting Path?
Simple path from s to t along edges with positive weight in the residual network
(so importantly, you omit edges with weight 0 in the residual)
What is the residual capacity along an agumenting path?
It’s the min edge weight in the residual along the augmenting path (so min weight across all the weights in the path)
What is the Ford Fulkerson Method?
Set the initial flow to 0 on all edges
max_flow = 0
While there exists an augmenting path p in the residual network G
- Augment the flow f along the augmenting path p as much as possible (forward edge weight = augmented flow, backward edge weight -= augmented flow)
- increase the max_flow by augment flow
We will run out of augmenting paths when there is no forward ways to go from source to target in the residual network
What is the complexity of FordFulkerson with DFS and why
O(|E| * max_flow)
note - when using bipirate graphs, max_flow is often the degree from the source (as the capacity is 1)
this is because it often finds the deepest path - so in the worst case it may only send 1 unit of flow along the augmenting path
What is the complexity of FordFulkerson with BFS and why
O(|V| x |E|^2)
this is because the augmenting stage takes O(VE) - BFS looks for the shortest path by number of edges
How can you find the capacity through a graph when vertex’s have capacity flows?
Turn each vertex v into vin -> vout, and set the capacity on the edge to the original capacity of the vertex
How can you find the number of edge-disjoint paths in a graph?
give each edge a capacity of 1
the max flow is the numbe of edge-disjoint paths
How can you find the number of vertex-disjoint paths in a graph
Put a capacity on the vertex of 1.
then make a v-in and v-out with an edge between them of weight 1
