Differences

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

--- courses:cs211:winter2014:journals:maggie:home [2014/03/31 14:39] – weatherlym
+++ courses:cs211:winter2014:journals:maggie:home [2014/04/01 23:11] (current) – [7.6 Disjoint Paths in Directed and Undirected Graphs] weatherlym
@@ Line 442: / Line 442: @@
 ====== 7.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm ======
+  * Consider a highway system in which the edges are highways and the nodes are interchanges, network models of this type have several ingredients: capacities on the edges indicating how much they can carry; source nodes in the graph which generate traffic; and sink nodes in the graph which absorb traffic as it arrives, and the traffic itself which is transmitted across the edges
+  * We'll refer to the traffic as flow - an abstract entity  that is generated at source nodes, transmitted across edges, and absorbed at sink nodes
+  * flow network is a directed graph G = (V, E) where each edge e is a capacity, which is a nonnegative number denoted ce, there is a single source s in V, and a single sink t in V
+  * we will say that an s-t flow is a function f that maps each edge e to a nonnegative real number where the value f(e) represents the amount of flow carried by edge e
+  * For a flow f, each e in E, we have 0 <= f(e) <=ce, and for each node v other than s and t, we have the sum for all edges e into v, f(e) equals the sum of all edges e out of v f(e)
+  * Given a flow network, the goal is to arrange the traffic so as to make as efficient use as possible of the available capacity
+  *
 ====== 7.2 Maximum Flows and Minimum Cuts in a Network ======
+  * we say that an s-t cut is a partition (A, B) of the vertex set V so that s is in A and t is in B
+  * the capacity of a cut (A, B), which we will denote c(A, B) is simply the sum of the capacities of all edges out of A
+  * cuts provide very natural upper bounds on the values of flows
+  * Let f be any s-t flow, and (A, B) any s-t cut, then v(f) = f out (A) - f in (A), this statement says that by watching the amount of flow f sends across a cut, we can exactly measure the flow value, it is the total amount that leaves A, minus the amount that "swirls back" into A
+  * (7.8) Let f be any s-t flow, and (A, B) any s-t cut, then v(f) <= c(A, B)
+  * Let f bar denote the flow that is returned by the Ford-Fulkerson Algorithm, we want to show that f bar has the maximum possible value of any flow in G
+  * If f is an s-t flow s.t. there is no s-t path in the residual graph Gf, then there is an s-t cut (A*, B*) in G for which v(f) = c(A*, B*). Consequently f has the maximum value of any flow in G, and (A*, B*) has the minimum capacity of any s-t cut in G
+  * The flow f bar returned by the Ford-Fulkerson Algorithm is a maximum flow
+  * Given a flow f of maximum value, we can compute an s-t cut of minimum capacity in O(m) time
+  * The point is that f must be a maximum s-t flow for if there were a flow f' of greater value, the value of f' would exceed the capacity of (A, B), and this would contradict (7.8).  Similarly, it follows that (A, B) is a minimum cut - no other cut can have a smaller capacity, for if there were a cut (A', B') of smaller capacity, it would be less than the value of f, and this again would contradict (7.8), so this gives us the Max-Flow Min-Cut Theorem - In every flow network, the maximum value of an s-t flow is equal to the minimum capacity of an s-t cut
+  * If all capacities in the flow network are integers, then there is a maximum flow f for which every flow value f(e) is an integer
 ====== 7.5 A First Application: The Bipartite Matching Problem ======
+  * Beginning with the graph G in an instance of the Bipartite Matching, we construct a flow network G', first we direct al edges in G from X to Y, we then add a node s and an edge (s,x) from s to each node in X.  We add a node t, and an edge (y, t) from each node in Y to t.  Finally, we give each edge in G' a capacity of 1, we now compute a maximum s-t flow in this network G'
+  * The size of the maximum matching in G is equal to the value of the maximum flow in G'; and the edges in such a matching in G are the edges that carry flow from X to Y in G'
+  * The Ford-Fulkerson Algorithm can be used to find a maximum matching in a bipartite graph in O(mn) time, where m is the number of edges
+  * We can decide if the graph G has a perfect matching by checking if the maximum flow in a related graph G' has value at least n, by the Max-Flow Min-Cut theorem there will be an s-t cut of capacity less than n if the maximum -flow value in G' has value less than n
+  * If there are nodes x1 and x2 in X that have only one incident edge each, and the other end of each edge is the same node y, then clearly the graph has no perfect matching
+  * Assume that the bipartite graph G = (V, E) has two sides X and Y st the size of X is equal to the size of Y.  Then the graph G either has a perfect matching or there is a subset A of X st the size of Gamm(A) < the size of A where Gamm(A) is a subset of Y and denotes the set of all nodes that ar adjacent to nodes in A.  A perfect matching can be found in O(mn) time
 ====== 7.6 Disjoint Paths in Directed and Undirected Graphs ======
+  * We say that a set of paths is edge-disjoint if no two paths share an edge,
+  * Given a directed graph G = (V, E) with two distinguished nodes s, t in V, the Directed Edge-Disjoint Paths Problem is to find the maximum number of edge-disjoint s-t paths in G
+  * The Undirected Edge-Disjoint Paths Problem is to find the maximum number of edge-disjoint s-t paths in an undirected graph G
+  * Both directed and the undirected versions of the problem can be solved using flows, starting with the directed problem, given the graph G = (V, E) we define a flow network in which s and t are the source and sink, and with capacity of 1 on each edge, suppose there are k edge-disjoint s-t paths, we can make each of these carry one unit of flow.  If there are k edge-disjoint paths in a directed graph G from s to t, then the value of the maximum s-t flow in G is at least k
+  * If f is a 0-1 valued flow of value v, then the set of edges with flow value f(e) = 1 contains a set of v edge-disjoint paths
+  * There are k edge-disjoint paths in a directed graph G from s to t if and only if het value of the maximum value of an s-t flow in G is at least k
+  * The Ford-Fulkerson Algorithm can be used to find a maximum set of edge-disjoint s-t paths in a directed graph G in O(mn) time
+  * In every directed graph with nodes s and t, the maximum number of edge-disjoint s-t paths is equal to the number of edges whose removal separates s from t
+  * There are k edge-disjoint paths in an undirected graph G from s to to if and only if the maximum value of an s-t flow in the directed version G' of G is at least k.  The Ford-Fulkerson Algorithm can be used to find a maximum set of disjoint s-t paths in an undirected graph G in O(mn) time
+  * In every undirected graph with nodes s and t, the maximum umber of edge-disjoint s-t paths is equal to the minimum number of edges whose removal separates s from t.