Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2018:journals:donohuem:chapter7 [2018/04/03 02:26] – donohuem
+++ courses:cs211:winter2018:journals:donohuem:chapter7 [2018/04/03 03:13] (current) – [7.7 More on Maximum-Flow] donohuem
@@ Line 19: / Line 19: @@
 ===== 7.2 Minimum Cuts =====
+This section is entirely concerned with analysis of the Ford-Fulkerson algorithm. There are several important principles applied within the algorithm. For starters, we know that the flow returned by the FF algorithm is the maximum flow. We know this by a very complex proof that utilizes cuts, or partitions of the nodes within a graph. More specifically, we use two cuts, A and B where s is in A and t is in B. The various proofs are confusing, but the overall takeaway is that the algorithm is correct and can run in O(m) time. The readability of this section was 4/10.
+===== 7.5 Bipartite Matching =====
+In this section, we revisit the Bipartite Matching Problem where we wish to find the largest bipartite matching in a graph G. The algorithm that achieves this builds off of the concept of flow networks. The algorithm takes an undirected bipartite graph and constructs a directed flow network from it. Interestingly enough, the size of the maximum matching in G is equal to the maximum flow in the corresponding flow network graph of G. The algorithm is more expensive, however, running in O(mn) time. Overall the readability of this section is 7/10.
+===== 7.7 More on Maximum-Flow =====
+The Maximum-Flow problem can be extended