Pearls in Graph Theory: #7.2.2. An accounting firm has eight CPA\'s available an

Question

Pearls in Graph Theory: #7.2.2. An accounting firm has eight CPA's available and seven audits to be scheduled. The table shows which of the CPA's are qualified for the various audits; there is an x under audit n if the CPA is qualified. Find an assignment of qualified CPA's to the audits.

CPA includes a-h, Audits includes 1-7

a: 3,4,5; b: 1,4,6; c: 3,6,7; d: 2,3,4; e: 1,2,3,7; f: 2,4,6; g: 3,4,5; h: 4,5,6

1. Draw the bipartite graph that represnets the original problem.

2. Use this matching as the first matching M={a,5;b,6;c,3;d,4;e,1}

3. In each step:

-Write out set M.

-Draw andd label the M-augmenting path for your vertex, if it exists.

-If no augmenting path exists for your vertex, draw all possible M-alternating paths and explain why none of those are possible.

-Note which vertices are eligible and which are ineligible at the end of each stage of the algorithm.

4. Draw a graph of your final matching.

5. Give the actual specific assignment in terms of the CPAs and audits.

Explanation / Answer

ans %664 2 ..

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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