Consider the 7 × 7 matrix of 0\'s and l\'s 1 01 01 00 110 1100 1 01 01 00 (a) Wi

Question

Consider the 7 × 7 matrix of 0's and l's 1 01 01 00 110 1100 1 01 01 00 (a) With the rows labelled a, b,...,g in order, and the columns labelled 1,2,...,7 in order, regard the matrix as a bipartite graph. Specify an alternating path, which includes the edge (e,5), and involves all the vertices except f and 6. You do not need to draw the bipartite graph. (b) Identify an augmenting path starting at node f and finishing at node 6 (c) Using this augmenting path, identify a matching of size 7 (d) Draw a minimum line cover for the matrix, and specify how the result relates your answer in (c). Which theorem did you use?

Explanation / Answer

(a) An alternating path starts at an unmatched node on one side of the bipartite graph and finishes at an unmatched node on the other side of the bipartite graph. Our alternating path must start at an unmatched node.

1. the first step in the path must be along an arc that is not in the initial matching. Looking at the graph this must be to either a or c or d, e, f. Let us choose (a, 3) since this is an unmatched pair.

2. the second step is then along the arc that is in the initial matching, i.e. b

3. the third step is then along an arc not in the initial matching, i.e. (b, 4)

Proceeding, we get the alternating path as (a, 3), (b, 4), (e, 5)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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