CMI2019-A-7

Question

An interschool basketball tournament is being held at the Olympic sports complex. There are multiple basketball courts. Matches are scheduled in parallel, with staggered timings, to ensure that spectators always have some match or other available to watch. Each match requires a team of referees and linesmen. Two matches that overlap require disjoint teams of referees and linesmen. The tournament organizers would like to determine how many teams of referees and linesmen they need to mobilize to effectively conduct the tournament. To determine this, which graph theoretic problem do the organizers have to solve?

• A. Find a minimal colouring.
• B. Find a minimal spanning tree.
• C. Find a minimal cut.
• D. Find a minimal vertex cover.

Answer 1

Answer: $\mathbf A$

Explanation:

Let's represent this situation in the form of a graph. Consider matches as the nodes in which the same edge represents that the different matches are overlapping. So, for this situation, we need different referees and linesmen.

So, how would you solve this?

Definitely by taking care that the nodes which have the same edge do not have the same referee or linesman(think of referee and linesman as the color of the nodes now)

So, basically we just have to solve the minimal coloring problem now, which will be the required answer to the above problem.

Answer 2