My notes on the assigned sections of Chapter 6 of Algorithm Design by Jon Kleinberg and Éva Tardos. This chapter details network flow algorithms like Bipartite Matching and Maximum-Flow.
The max flow problem arises from having flow in transportation networks. Transportation networks model some sort of network like a highway system or a system of pipes carrying water. Each edge in the network has a capacity, and the network has both source and sink nodes. The Ford-Fulkerson algorithm finds the maximum flow of such a network, arranging the traffic to make efficient use of the available capacity. This algorithm finds such a maximum flow in no worse than O(mC) time.
Overall, I found this section fairly each to understand and fairly interesting. I'd give it a 7/10 for both.
One main goal of the Ford-Fulkerson algorithm is to show that the flow returned has the maximum possible value for any flow in G. An s-t cut can be defined as a partition (A, B) of the vertex set V, so that s is in A and t is in B. The capacity of this cut is the sum of the capacities of all edges out of A. Also, it should be noted that maximum flow and minimum cut are both equal. If all capacities in a flow network are integers, then there is a max flow f for which every flow value is an integer.
I'd give this section a 6/10 on interestingness and an 8/10 on readability.
A bipartite graph is an undirected graph whose node set can be partitioned as V = X union Y, with every edge with one end in X and one end in Y. A matching M in G is a subset of the edges such that each node appears in at most one edge in M. The Bipartite Matching problem is to find a matching of the largest possible size. The Ford-Fulkerson algorithm can find a maximum matching in a bipartite graph in O(mn) time. This approach works except when there is a bipartite graph with no perfect matching.
Overall, I'd give this section a 7/10 on both readability and interestingness.
This section focuses on 2 generalizations of maximum flow. Both of these generalizations can be reduced to the basic Maximum-Flow problem. The first generalization is circulations with demands. This occurs when there is a set of sinks that can absorb flow. The second generalization is circulation with demands and lower bounds. This also occurs when there is a set of sinks that can absorb flow, but we also want this flow to make use of specific edges by placing lower bounds on edges.
I'd give this section an 8/10 on both readability and interestingness.