Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
This might be useful sce.carleton.ca/faculty/chinneck/po/Chapter9.pdf –  Kirthi Raman Mar 15 '12 at 0:54
1  
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.) –  dtldarek Mar 15 '12 at 1:15

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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