Differences

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

--- courses:cs211:winter2018:journals:cohene:home:chapter7 [2018/04/02 03:04] – [7.2: Maximum Flows and Minimum Cuts in a Network] cohene
+++ courses:cs211:winter2018:journals:cohene:home:chapter7 [2018/04/02 03:44] (current) – [7.7: Extensions to the Maximum-Flow Problem] cohene
@@ Line 19: / Line 19: @@
 ===== 7.5: A First Application: The Bipartite Matching Problem=====
+We can now use the concept of maximizing flows to solve the bipartite matching problem. First, we create a flow network from the bipartite graph. We then find the maximum s-t flow of this network. If there is a matching of k edges, and the flow among those edges is f, one can see that the capacity and conservation conditions are met and f is an s-t flow with value k.
+Considering a set M' where edges of the form (x,y) have a flow value of 1, M' contains k edges, each node in X is the trail of at most one edge in M', and each node in Y is the head of at most one edge in M'. This allows us to see that the maximum matching in G is equal to the value of the maximum flow in G', which carries from from X to Y in G'.  We can perform this matching in O(mn) time.
+Because not all bipartite graphs have perfect matchings, it is easy to wonder how to handle this situation. We can determine whether or not a graph, G, has a perfect matching by checking if the maximum flow in G' has a value of at least n. According to the Max-Flow Min-Cut Theorem, there will be an s-t cut of capacity less than n if the maximum-flow of G' is also less than n.
+This section somewhat reminded me of discussing the pigeon hole principle. If we have too many x nodes to match to y nodes, then there must be an x node that is not matched and therefore a perfect matching does not exist. We can apply Hall's Theorem to this situation to find the solution in O(nm) time.
 ===== 7.7: Extensions to the Maximum-Flow Problem=====
+There are numerous extensions to the Maximum-Flow Problem involving search components that can be solved in polynomial time. One of these extensions is Circulations with Demands. If we have multiple sources and sinks, it becomes complicated to determine where to look to solve a maximization problem. Instead of maximizing flow values, here we would look at fixed supply values for sources and fixed demand values for sinks. We still want to send flow from the sources to the demands. We now associate each node with a demand. A circulation with demands is a function of f that satisfies capacity and demand conditions.
+We can design an algorithm for circulation and demands to find a maximum s-t flow. However, we can only find a feasible circulation with demands in G if and only if the maximum s-t flow in G' has a value of D. We can enforce this by placing lower bounds on edges and upper bounds on edge capacities.