Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:cs211:winter2018:journals:bairdc:chapter7 [2018/04/03 00:28] – [7.1 – The Maximum-Flow Problem and the Ford-Fulkerson Algorithm] bairdc | courses:cs211:winter2018:journals:bairdc:chapter7 [2018/04/03 00:48] (current) – bairdc | ||
|---|---|---|---|
| Line 8: | Line 8: | ||
| Overall, I found this section fairly each to understand and fairly interesting. I'd give it a 7/10 for both. | Overall, I found this section fairly each to understand and fairly interesting. I'd give it a 7/10 for both. | ||
| + | |||
| + | ===== 7.2 – Maximum Flows and Minimum Cuts in a Network ===== | ||
| + | |||
| + | 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. | ||
| + | |||
| + | ===== 7.5 – A First Application: | ||
| + | |||
| + | 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. | ||
| + | |||
| + | ===== 7.7 – Extensions to the Maximum Flow Problem ===== | ||
| + | |||
| + | 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. | ||
