MST

Problem 11.34. 6.042 is often taught using recitations. Suppose it happened that 8 recitations were "mes" -2015/5/18-1:43 -page 451-#459 11.11. References 451 needed, with two or three staff members running each recitation. The assignment of staff to recitation sections, using their secret codenames, is as follows: . R1: Maverick, Goose, Iceman R2 Maverick, Stinger, Viper R3: Goose, Merlin R4: Slider, Stinger, Cougar RS: Slider, Jester, Viper R6: Jester, Merlin R7: Jester, Stinger R& Goose, Merlin, Viper Two recitations can not be held in the same 90-minute time slot if some staff member is assigned to both recitations. The problem is to determine the minimum number of time slots required to complete all the recitations (a) Recast this problem as a question about coloring the vertices of a particular graph. Draw the graph and explain what the vertices, edges, and colors represent. (b) Show a coloring of this graph using the fewest possible colors. What schedule of recitations does this imply