What is a network flow?
- A flow network G = (V,E) is a weighted graph with vertices V and a set of directed edges E in which each edge has a flow value and a non negative integer capacity c(u, v)
- the flow value: 0 <= f(u,v) <= c(u,v)
- the graph has a source s node and a sink t node
- we assume that s has no in-coming edges and t has no out-going edges
What is the flow conservation constraint?
- for every vertex other than s and t, the amount of flow into the vertex must be equal to the amount of flow out of the vertex
What is the maximum flow problem?
- given a flow network G, with source s and sink t, find the maximum flow value from s to t
How do you calculate the value of the flow? (maximum flow)
By adding all of the flows (NOT THE CAPACITIES) that are outcoming from the source
What is a popular algorithm for find the maximum flow in a flow network?
- the Ford-Fulkerson algorithm
- It searches for a flow augmenting path from the source vertex S to the sink t
- We then send as much flow along it as possible, whilst obeying the capacity constraints
- maximum flow we can send along the augmenting path = minimum of c(u,v) - f(u,v) of any of the edges in the augmenting path
What are the 3 important things the Ford Fulkerson algorithm depends on?
- Residual networks, cuts and augmenting paths
What are residual networks?
- A residual network consists of edges that can admit more flow
- given the flow network G and a flow f in that network, we define the residual network Gf so Gf depends upon the given flow f. We want to account for the edges that can still receive more flow
How is a forward edge’s residual value calculated?
∆ = capacity - flow
so if we have the edge in G - 5/8
- the forward edge’s value = 8-5 = 3
How is a backward edge’s residual value calculated?
∆ = flow value
so if we have the edge in G - 5/8
- the backward edge’s value = 5
What is an augmenting path in a residual graph?
- Given a flow network and a flow f, an augmenting path p is a directed path following forward and backward edges from s to t in the residual network
- informally an augmenting path is a path from the source to the sink in which we can send more net flow down
How do we update the edges in the residual network after we increase the flow along an augmenting path?
- on forwards edges we increase the flow by the minimum residual flow left (out of all the edges in the augmenting path)
- on backwards edges we decrease the flow by the minimum residual flow left
- we then update the residual network, as for example some edges may become backwards edges or may not be forwards edges anymore
What does the max flow/min cut theorem tell us?
- That the flow is maximum if and only if no augmenting paths exist anymore
What is a cut in a flow network?
- A cut (S,T) in a flow network is a partition of the set of vertices in the network into two subsets S and T where T = V - S. In S we include the source node and in T we include all other vertices.
- What is the net flow across a cut?
- What is the capacity of a cut?
- Net flow is the sum of the flows of the edges from S side to T side minus the flows of the edges from T side to S side
- Capacity = sum of capacity of edges that go from S side to T side
What is the maximum flow equal to in a flow network
Maximum flow is equal to the capacity of a minimum cut in the network
How do we know to terminate the Ford-Fulkerson algorithm/know we’ve found the correct cut to observe the max flow min cut theorem?
- If in the residual network, we observe that each of the weights along the incoming edges are saturated (completely full e.g. 1/1, 2/2, 4/4)
- this means that if we look at the residual network each of these edges are denoted as backwards edges
- so if we were to try go towards the sink node t, we have no way of getting there because the only edges that could get us out of the source are pointing back towards the source, so we have no way of producing an augmenting path from the source to the sink
- therefore the BFS/DFS would report there’s no augmenting paths left and the algorithm knows to stop
What is the running time of the Ford Fulkerson algorithm?
O(|f|m)
What are Bipartite graphs?
- A bipartite graph is a graph whose vertex set can be partitioned into two sets X and Y so that every edge joins a vertex in X to a vertex in Y and vice versa
- can’t have cycles in a bipartite graph of an odd length, since if we start at a node and want to return to it, this is always an even number of edges
- an odd cycle would mean the graph isn’t bipartite
- we use bipartite graphs in situations where we want to pair or assign one set of objects with another set of objects
What are matchings?
A matching is a subset of the edges of a bipartite graph where each vertex appears in at most one edge
(matchings share no common endpoints)
What algorithm can we use to find a bipartite graphs maximum matching size?
- we can create a flow network with the bipartite graph by adding on a source and sink node to it and linking all the pairs of nodes, we can then use the ford fulkerson algorithm to find the maximum matching size
