Differences

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

--- courses:cs211:winter2012:journals:ian:chapter7 [2012/04/04 03:39] – 7.1 sturdyi
+++ courses:cs211:winter2012:journals:ian:chapter7 [2012/04/04 04:06] (current) – 7.7 sturdyi
@@ Line 5: / Line 5: @@
    * No insights.
    * No complaints.
+====== 7.2 Maximum Flows and Minimum Cuts ======
+   * If we take a cut separating the source and sink, the total flow equals the flow across the cut minus the backflow across it. Thus the capacity of a cut bounds the capacity of the graph. More powerfully, the maximum flow equals the capacity for some cut (the minimum cut) (if all cuts are under capacity, there must be an augmenting path). Since the FFA terminates at this point, it returns a maximal flow. Moreover, this means that for any graph with integer capacities, there is an integer-valued flow (not necessarily unique, and not all maximal flows need have this property). The requirement of rational capacities is necessary as for some choices of augmenting paths, FFA on real capacities can run infinitely.
+   * No questions.
+   * No insights.
+   * I would have liked to see an explanation of why rational numbers are permissible (which is, I believe, because in any finite graph with rational capacities there is a lcm of the capacities, and if all capacities are multiplied by that we get an integer graph). In any event, unless I miss something they say that the requirement that the flows be integers is necessary, state the problems with irrational capacities, and then state that real problems might have rational capacities, without showing that the rational capacities are workable.
+====== 7.5 Bipartite Matching ======
+   * The FFA can be used to solve bipartite matching, finding the greatest subset of a bipartite graph such that each node has at most one incident edge. Make all edges directed with unit capacity (in uniform direction) and add a source and sink, with unit capacity edges into the nodes chosen as the origin of the edges between the original nodes, and unit capacity edges from the destination nodes to the sink. The subset of the original edges with positive flow in a valid flow through this graph are a valid matching of the original graph, since each origin node only has one unit of incoming flow to distribute and each destination node can only handle one unit of flow. Thus, an optimal flow is a greatest matching. The creation of the new graph is O(m+n), and the capacity out of the source is O(n). Thus, it takes O(mn) (referring back to the FFA running time).
+   * No questions.
+   * No insights.
+   * No complaints.
+====== 7.7 Extensions ======
+   * The algorithm can also handle distributed sources and sinks (each node has a supply or demand associated with it). Add a source with edges to each supply node with capacity equal to the supply of the incident node, and likewise add a sink connected to demand nodes. A circulation exists iff the maximum flow through this graph equals the sum of supplies and the sum of demands. One can further generalize to have lower bounds for nodes; before modeling the supply and demand, increase the demand of origin nodes of edges with lower bounds by that bound, and likewise decrease the demand of the destination nodes, and then solve as above for a maximum flow.
+   * No questions.
+   * No insights.
+   * No complaints.