Because of the incredible popularity of Math for Computer Science, Rajeev decide
ID: 3141519 • Letter: B
Question
Because of the incredible popularity of Math for Computer Science, Rajeev decides to give up on regular office hours. Instead, each student can join some study groups Each group must choose a representative to talk to the staff, but there is a staff rules that a student can only represent one group. The problem is to find a representative from each group while obeying the staff rule. Explain how to model the delegate selection problem as a bipartite matching problem. "mcs" - 2012/1/4 - 13:53 - page 362 - #370 The staff's records show that no student is a member of more than 4 groups, and all the groups must have at least 4 members. That's enough to guarantee there is a proper delegate selection. Explain.Explanation / Answer
a)
Define a bipartite graph with the study group as one set of vertices and everybody who belongs to some group as the other set of vertices. Let a group and a student be adjacent exactly when the student belongs to the group. Now a matching of study groups to students will give a proper selection of delegates: every group will have a delegate, and every delegate will represent exactly one group.
b)
The degree of every group is at least 4, and the degree of every student is at most 4, so the graph is degree-constrained which implies there will be no bottlenecks to prevent a matching. Hall’s Theorem then guarantees a matching. Hall's theorem states that 'let G be a bipartite graph with vertex partition L; R. There is matching in G that covers L iff no subset of L is a bottleneck'.