1.Given Example 10.4.4 and Theorem 10.4.5 in the textbook, explain how you would
ID: 668522 • Letter: 1
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 of A,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 vertex vis (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
A matching in a Bipartite Graph is a set of the edges chosen in such a way that no two edges share an endpoint. A maximum matching is a matching of maximum size (maximum number of edges). In a maximum matching, if any edge is added to it, it is no longer a matching. There can be more than one maximum matchings for a given Bipartite Graph.
Let us first define input and output forms. Input is in the form of Edmonds matrix which is a 2D array ‘bpGraph[M][N]’ with M rows (for M job applicants) and N columns (for N jobs). The value bpGraph[i][j] is 1 if i’th applicant is interested in j’th job, otherwise 0.
Output is number maximum number of people that can get jobs.
A simple way to implement this is to create a matrix that represents adjacency matrix representation of a directed graph with M+N+2 vertices. Call the fordFulkerson() for the matrix. This implementation requires O((M+N)*(M+N)) extra space.
Extra space can be be reduced and code can be simplified using the fact that the graph is bipartite and capacity of every edge is either 0 or 1. The idea is to use DFS traversal to find a job for an applicant (similar to augmenting path in Ford-Fulkerson). We call bpm() for every applicant, bpm() is the DFS based function that tries all possibilities to assign a job to the applicant.
In bpm(), we one by one try all jobs that an applicant ‘u’ is interested in until we find a job, or all jobs are tried without luck. For every job we try, we do following.
If a job is not assigned to anybody, we simply assign it to the applicant and return true. If a job is assigned to somebody else say x, then we recursively check whether x can be assigned some other job. To make sure that x doesn’t get the same job again, we mark the job ‘v’ as seen before we make recursive call for x. If x can get other job, we change the applicant for job ‘v’ and return true. We use an array maxR[0..N-1] that stores the applicants assigned to different jobs.
If bmp() returns true, then it means that there is an augmenting path in flow network and 1 unit of flow is added to the result in maxBPM().
Maximum Bipartite Matching Given a bipartite graph G = (A B, E), find an S A × B that is a matching and is as large as possible.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.