Differences

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

--- courses:cs211:winter2012:journals:joey:home [2012/04/04 00:26] – [Chapter 7 - Network Flow] brownjn
+++ courses:cs211:winter2012:journals:joey:home [2012/04/04 04:31] (current) – [Chapter 7 - Network Flow] brownjn
@@ Line 250: / Line 250: @@
 **7.1 - The Maximum-Flow Problem and the Ford-Fulkerson Algorithm**
+The problem: Consider a network where the nodes are switches, and the directed edges have capacities. Source nodes in this graph create traffic, and sink nodes absorb traffic. The traffic across this graph will be called flow, and we want to maximize the flow being sent/received. No edges enter the source and no edges leave the sink. In our models, we will only analyze a steady flow of traffic, not bursty traffic. So... given a flow network, how do we arrange the traffic so as to make as efficient use as possible of the available capacity? Or, given a flow network, find a flow of maximum possible value.
-.2
+In order to solve this problem, we will use a method that uses a residual graph, whereas we can push flow backwards on edges that already carry flow , to divert it in a different direction. The Ford-Fulkerson Algorithm involves adding flow onto an edge, then checking for bottlenecks, then undoing the flow according to that bottleneck. The algorithm can be found on pg 344 of the text. The complexity of this algorithm is O(n+m) or just O(m).
-.5
-.7
+**7.2 - Maximum Flows and Minimum Cuts in a Network**
+For this section, we split the graph into two sections, and prove the maximum possible flow for each section. At some point the flow must cross from one section to the other, so if we can be sure that this is optimal, we can ensure that the entire thing is optimal. The value of every flow is upper-bounded by the capacity of every cut.
+In every network, the maximum value of an s-t flow is equal to the minimum capacity of an s-t cut.
+**7.5 - A First Application: The Bipartite Matching Problem**
+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)