1
$\begingroup$

I have this problem in my Question paper for the BE exam I appeared. I am not able to understand the problem statement and dont know how to use max flow min cut theorem to use it.

Please guide me through this. The problem statement is as below.

Students p, q, r, s, t are members of three committees A, B, and C; r and s belong to committee A; p, r, t belong to committee B and p, q and t belong to committee C. Each committee is to select a student representative. Use the Max-flow-Min-cut theorem to determine if a selection be made such that each committee has a distinct representative?

$\endgroup$
  • $\begingroup$ This might be useful sce.carleton.ca/faculty/chinneck/po/Chapter9.pdf $\endgroup$ – Kirthi Raman Mar 15 '12 at 0:54
  • 1
    $\begingroup$ The problem statement defines a graph, and you need to check if in this graph there is a matching with some property. You could extend this graph in a clever way, and by using max-flow-min-cut it may be that max flow will be sufficient to determine the problem solution. (My comment is so vague by intention.) $\endgroup$ – dtldarek Mar 15 '12 at 1:15
2
$\begingroup$

I think enough time has passed to expand on dtldarek's hint.

Create a network with nodes Source, $A,B,C,p,q,r,s,t$, and Sink; an arc from Source to each of $A,B,C$; an arc from a committee to a student if that student is on that committee; and an arc from each student to the Sink, all arcs having capacity one. Now use max-flow-min-cut to show there's a system of distinct representatives if and only if there's a flow of value 3, and the arcs in such a flow give you the system of distinct representatives.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.