edited by
801 views
2 votes
2 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 
edited by

1 Answer

0 votes
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

Related questions

16 votes
16 votes
2 answers
1
go_editor asked May 27, 2016
2,166 views
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 votes
4 votes
2 answers
4