Differences

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

--- courses:cs211:winter2012:journals:joey:home [2012/04/04 02:58] – [Chapter 7 - Network Flow] brownjn
+++ courses:cs211:winter2012:journals:joey:home [2012/04/04 04:31] (current) – [Chapter 7 - Network Flow] brownjn
@@ Line 263: / Line 263: @@
 **7.5 - A First Application: The Bipartite Matching Problem**
-.7
+In order to solve this one, just add a source node and a sink node, make the current graph directed from one grouping to the other, and then add in the source and sink so that everything flows in the same direction. Then it is as simple as just implementing the Ford-Fulkerson Algorithm on this graph. The algorithm will run in O(mn) time. This will find an a matching of the largest possible size.
+Sometimes there is no perfect matching in a bipartite graph. We can check whether or not a matching is perfect if the flow coming into the sink or leaving the source is 1/2 the size of n.
+**7.7 - Extensions to the Maximum-Flow Problem**
+Imagine the situation in which there are multiple sinks and sources. In this case, instead of max flow, each node has a demand or a supply. In order to solve this problem, again, add a sink and source, or super-sink and super-source. The capacities of the edges going from the super-source to the supply nodes are equal to the supply offered by those nodes; and the edges going from the demand nodes to the super-sink are equal to the demand by those nodes. Then it is just a max flow problem.
+**Interest:** 10 (taking Networks with Stough and this is pretty relevant)
+**Readiblity:** 5 (the language could have been clearer)