1.Given Example 10.4.4 and Theorem 10.4.5 in the textbook, explain how you would

Question

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.

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.

10.4.4 A Matching Network

Model the matching problem of Example 10.4.1 as a network.

We first assign each edge in the graph of Figure 10.4.1 capacity 1 (see Figure 10.4.3). Next we add a supersource a and edges of capacity 1 from a to each ofA,B, C, and D. Finally, we introduce a supersink z and edges of capacity 1 from each of J1, J2, J3, J4, and J5 to z. We call a network such as that of Figure 10.4.3 amatching 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 ? V is matched with the vertex w ? 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 ? V, w ? W, has flow 1. The only edge into vertexvis (a, v). This edge must have flow 1; thus the flow into vertex v 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 E have 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

Explanation / Answer

Maximal flow, d = min (d1, d2)

where d1 = min [c(vi,vi+1)-f(vi,vi+1)],where vi,vi+1 is flow in forward direction and

d2= min of flow in backward direction

In the example given above , all the flows are in forward direction so,

d1= min[(1-1),(1-1),(1-1),(1-0),(1-1),(1-0),(1-0),(1-1),(1-0),(1-1),(1-0),(1-0),(1-0),(1-0),(1-0),(1-1),(1-1),(1-0),(1-1)]

min[0,0,0,1,0,1,1,0,1,0,1,1,1,1,1,0,0,1,0]= 0

and

d2= 0 as there is no backward flow

Now, d= min (d1,d2) = min (0,0)= 0

So, maximal flow= 0

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.