Discrete Math 1 Given Example 1044 and Theorem 1045 in the t

Discrete Math:

1. Given Example 10.4.4 and Theorem 10.4.5 in the textbook, explain how you would transform the matching problem into a maximal flow problem. (Show all work)

2. Once you complete question 1, use the already known linear program that solves the maximal flow problem. Show all of your work and how you are doing the reduction. (Show all work)

Hint 1: Transform the matching problem into a matching network, and then find the maximal flow to this network.

Hint 2: The goal here is to learn that, while problems might appear different, they are often the same. Knowing how to transform a new problem into a known problem can save a lot of solving time. Use the Internet and your textbook.

Information:

10.4.4 A Matching Network

Model the matching problem of Example 10.4.1 as a network.

Theorem 10.4.5

Let G be a directed, bipartite graph with disjoint vertex sets V and W in which the edges are directed from vertices in V to vertices in W . (Any vertex in G is either in V or in W.)

(a)A flow in the matching network gives a matching in G. The vertex v (the element of) V is matched with the vertex w (element of) W if and only if the flow in edge(v,w)is 1.

(b)A maximal flow corresponds to a maximal matching.

(c)A flow whose value is |V| corresponds to a complete matching.

Proof

Let a(z) represent the source (sink) in the matching network, and suppose that a flow is given.

Suppose that the edge (v,w),v (element of) V,w (element of) W, has flow 1. The only edge into vertexvis (a,v). This edge must have flow 1; thus the flow into vertexv is 1. Since the flow out of v is also 1, the only edge of the form (v,x) having flow 1 is (v,w). Similarly, the only edge of the form (x,w) having flow 1 is (v,w). Therefore, if E is the set of edges of the form (v,w) having flow 1, the members of Ehave no vertices in common; thus E is a matching for G.

Parts (b) and (c) follow from the fact that the number of vertices in V matched is equal to the value of the corresponding flow.

More Information:

A linear programming problem consists of an objective (that is, a value to be maximized or minimized) and constraints.

Each of the graphical optimization problems discussed in this class can be rephrased as a linear programming problem by altering the objective or the constraints to refit the problem at hand. Another way to use a linear program to solve an optimization problem is to transform a new problem into a problem for which we already have a linear program solution—this is a reduction. The idea is that you already have a solution for a known linear programming problem. If you can somehow transform a new problem that you have into this known linear programming problem, you already have the solution. The tricky part is to figure out how to transform your problem into a known solution problem.

For this assignment, read the Notes section on pages 534 and 535 of your textbook. There is a linear program on these pages that describes finding a maximal flow in a network G, with a source a, a sink z, flows F, and capacities C. If we want to find a solution to a different problem, maybe the matching problem, for example, we could (1) formulate a linear program for the matching problem or (2) transform the matching problem into a maximal flow problem, then use the already known linear program that solves the maximal flow problem.

Linear program:

Figure 10.4.3 The matching problem (Figure 10.4.1) as a matching network. J1 1,0 A 1,1 1, 0 1,1 1,0 1,1 B 1,0 1,1 1,1 1,0 J3 1,1 c 1,0 1,0 J4 1,0 D 1,0 1,0 1, 1

Solution