Differences

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

--- courses:cs211:winter2018:journals:lesherr:home:chapter7 [2018/04/01 23:02] – [Section 2] lesherr
+++ courses:cs211:winter2018:journals:lesherr:home:chapter7 [2018/04/02 00:24] (current) – [Section 7] lesherr
@@ Line 4: / Line 4: @@
 ===== Section 2: Maximum Flows and Minimum Cuts in a Network =====
 The next goal of this problem is to show that the value of the flow returned by the Ford-Fulkerson Algorithm is the max possible flow for the graph. We will use the idea of a cut to develop a way to place an upper bound on the maximum-flow value. We consider dividing the nodes in the graph into two sets A and B, where the source is in the set A and the sink is in the set B. We say that an s-t cut is a partition (A, B) of the nodes in the graph, with the source in A and the sink in B. The capacity of a cut (A, B) is the sum of the capacities of all edges out of A into B. 'Let f be any s-t flow, and (A, B) any s-t cut. Then v(f) = fout(A)-fin(A). 'Let f be any s-t flow, and (A, B) any s-t cut Then v(f) = fin(B)-fout(B). Let f be any s-t flow, and (A, B) be any s-t cut. Then v(f) is less than or equal to the capacity of (A, B).' Thus the value of every flow is upper-bounded by the capacity of every cut. Thus, we can find any s-t cut, and know that the s-t flow can't be greater than the capacity of that cut. Conversely, if we find a flow value, we know there can't be an s-t cut of a capacity less than that flow value. 'If f is an s-t flow such that there is no s-t path in the residual graph G, then there is an s-t cut in G for which v(f) = capacity (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.' Thus we know that the flow returned by the Ford-Fulkerson Algorithm is a maximum flow, and given the max flow value, we can compute an s-t cut of minimum capacity in O(m) time. For every flow network , the maximum value of an s-t flow is equal to the minimum capacity of an s-t cut. Additionally, if all capacities in the flow network are integers, then there is a max flow f for which every flow value f(e) is an integer. This section was a bit harder to read and understand, and I still didn't understand how to find a minimum cut, and had to do some outside reading. Overall I would give this section a 5/10.
-===== Section 5 =====
+===== Section 5: The First Application: The Bipartite Matching Problem =====
-===== Section 7 =====
+Having found an algorithm that solves the Maximum-Flow problem, we know look towards finding situations were we can apply the algorithm. One very basic algorithm of maximum flows and minimum cuts is the Bipartite Matching Problem. A bipartite graph is an undirected graph whose node set can be partitioned into two smaller sets, with the property that every edge of the graph must have one end in each of the two subsets. A matching M in G is a subset of the edges such that each node appears in at most one edge in M. The bipartite matching problem is finding a matching in F of the largest possible size. While the flow networks are directed graphs, and we are working with undirected graphs, it is not difficult to use the algorithm we developed to solve this problem. Beginning with a bipartite graph g, we can construct a flow network, directing all edges in G from X to Y, and adding a source node s and an edge from s to all nodes in X, and a sink node t and an edge to t from all nodes in Y. Consider a flow f' in G' of value k edges. All edges in the path have a value of 1, and all other edges have a value of 0. Thus the set M' of edges of the form (x, y) on which the flow value is 1. M' contains k edges, since every edge value is 1 and the total value is k. Each node in X is the tail of at most one edge in M'. Each node in Y is the head of at most one edge in M'. 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. However, not all bipartite graphs have perfect matchings. To determine if a bipartite graph has a perfect matching, we can use the algorithm to find the maximum matching, and check if it is a perfect matching, but there is a better way. We can look for the minimum capacity s-t cut, and if it is less than n, then we know that the max flow value must be less than n, and thus, there is not a perfect matching. If a bipartite graph G with two sides X and Y has a perfect matching, then for all nodes in X we must have a distinct match in Y, and thus the size of Y must be at least as large as X. 'Assume that the bipartite graph G has two sides X and Y and that they are the same size. Then the graph G either has a perfect matching or there is a subset such that the corresponding subset is smaller. A perfect matching can be found in O(mn) time. This section was more difficult to follow, but hopefully will make more sense after studying it in class. I would give this section a 3/10.
+===== Section 7: Extensions to the Maximum-Flow Problem =====
+The major strength of the Maximum-Flow Problem is that it can be used to solve other problems with a nontrivial combinatorial search component in polynomial time because they can be reduced to finding a maximum flow or minimum cut in a directed graph. Bipartite matching is the first application that utilizes this approach but we can also look at other generalizations of maximum flow. The first generalization can be applied if we consider the Maximum-Flow Problem to have multiple source nodes initiating flow, and multiple sinks receiving flow. For this problem, we consider a situation where we have fixed supply values and fixed demand values, and the gogal is to ship flow from nodes with available supply to those with given demands. We are not seeking to maximize a particular value, we are simply trying to satisfy all the demand using the available supply. We are given a flow network G with edge capacities. With each node, we have a demand. If the demand is greater than 0, it is a sink and wants to receive flow, and if the demand is less than 0, it is a source and wants to send out flow. S denotes the set of all nodes with a demand less than 0, and T denotes the set of all nodes with a demand greater than 0. Nodes in S can receive flow, but must compensate by sending out more flow. Likewise, nodes in T can send out flow, but most compensate by receiving more flow in. Like the Maximum-Flow problem, the circulation demand problem has two conditions: that the flow on each edge not exceed the capacity, and that the flow into a node minus the flow out of the node must equal the demand of the node. In this problem, we are concerned with a feasibility problem; we want to know if it is possible to meet the two conditions. 'If there exists a feasible circulation with demands, then the sum of the total demands is 0.' There is a feasible circulation with demands dv in G IF AND ONLY IF the maximum s-t flow in G has value D. If all capacities and demands in G are integers, and there is a feasible circulation, then there is a feasible circulation that is integer-based. The graph G has a feasible circulation with demands Dv IF AND ONLY IF for all cuts (A,B) the sum of the Dv values is less than or equal to the capacity of the (A,B) cut. The second problem we will look at is the circulation with demands and lower bounds. In this problem, we not only want to satisfy the demands of the nodes, but we also want to force the flow to travel over certain edges. To do this we place lower bounds in addition to the upper bounds for the capacities of each edge. The same conditions apply to this variation of the Circular demand problem.  'There is a feasible circulation in F IF AND ONLY IF there is a feasible circulation in G'. If all demands, capacities, and lower bounds are integers, and there is a feasible circulation, then there is a feasible circulation that is integer-based.' This section was very difficult to read and understand. Hopefully discussing it in class will make it easier to understand. I would give this section a 1/10.