Register

CMI2015-A-04a

• edited by
1,225 views
3 3 votes

A college prepares its timetable by grouping courses in slots A, B, C, . . . All courses in a slot meet at the same time, and courses in different slots have disjoint timings. Course registration has been completed and the administration now knows which students are registered for each course. If the same student is registered for two courses, the courses must be assigned different slots. The administration is trying to compute the minimum number of slots required to prepare the timetable.
The administration decides to model this as a graph where the nodes are the courses and edges represent pairs of courses with an overlapping audience. In this setting, the graph theoretic question to be answered is:

  1. Find a spanning tree with minimum number of edges
  2. Find a minimal coloring
  3. Find a minimum size vertex cover
  4. Find a maximum size independent 

1 Answer

0 0 votes
Answer is B

 

If we represent courses as nodes of the graph, an edge between two nodes indicates a common person taking both courses.

Now assigning the minimum no of slots corresponds to finding the chromatic number of the graph
Voting & Accepting an answer helps improve the community
← Previous · CMI2015-A-03Next → · Solve the recurrence...
← Previous in category · CMI2015-A-03Next in category → · CMI2015-A-05
Position:
Show:

Related questions

17 17 votes
2 answers 2 answers
3.1k
3.1k views
go_editor asked May 27, 2016
3,136 views
CMI2015-A-05
An undirected graph has $10$ vertices labelled $1, 2,\dots , 10$ and $37$ edges. Vertices $1, 3, 5, 7, 9$ have degree $8$ and vertices $2, 4, 6, 8$ have degree $7.$ What ...
4 4 votes
2 answers 2 answers
997
997 views
go_editor asked May 27, 2016
997 views
CMI2015-A-03
Suppose each edge of an undirected graph is coloured using one of three colours — red, blue or green. Consider the following property of such graphs: if any vertex is the...
3 3 votes
1 1 answer
913
913 views
go_editor asked May 27, 2016
913 views
CMI2015-B-07
There is a thin, long and hollow fibre with a virus in the centre. The virus occasionally becomes active and secretes some side products. The fibre is so thin that new si...
4 4 votes
2 2 answers
1.3k
1.3k views
go_editor asked May 27, 2016
1,289 views
CMI2015-B-06c
Consider the code below, defining the functions $f$ and $g$:f(m, n) { if (m == 0) return n; else { q = m div 10; r = m mod 10; return f(q, 10*n + r); } } g(m, n) { if (n ...