Question 3.111

81. The nine standing committees of a state legislature are designing a schedule for when the committees can meet. The matrix shown in the following table has an X in a position where the committees corresponding to the row and column have a common member and, hence, should not be scheduled to meet at the same hour. The committees involved are Agriculture , Commerce , Consumer Affairs , Education , Forests , Health , Justice , Labor , and Rules .

X X X
X X X X
X X X X
X X X
X X X X
X X X X
X X X X
X X X
X X X
  1. Draw a graph that will be of value in determining the minimum number of time slots the committees can meet in without any legislator having to be in two places at one time.
  2. What is the minimum number of time slots in which the committees can be scheduled without a conflict?
  3. How many different rooms are needed at any time that a committee is scheduled to meet? (Why might this issue matter?)

81.

(a) Drawings can vary. Possible renderings include the following:

image

(b) 3

(c) 3; additional answers will vary.