Graph Theory Suppose that a random selection of students will be able to screen a new movie early. There are four screening sessions. For scheduling purposes, each of the selected students will specify which of the four screenings don’t conflict with their schedule—every student is available for at least two out of the four screenings. However, each screening has only 20 available seats, not all of which need to be filled each time. The event organizers are faced with a difficult scheduling problem: how do they make sure each of the chosen students is able to find a seat at a screening? They’ve recruited you to help solve this dilemma. (a) Describe how to model this situation as a matching problem. Be sure to specify what the vertices/edges should be and briefly describe how a matching would determine seat assignments for each student in a screening for which they are available. (This is a modeling problem; we aren’t looking for a description of an algorithm to solve the problem.) (b) Suppose 41 students have been selected. Can you guarantee that a matching exists, or are there some situations where not all of the 41 students can be accommodated? Briefly explain. (c) If instead only 40 students are chosen, prove that there is always a matching. Hint: Use Hall’s Theorem or something similar. Is your graph degree constrained?
Graph Theory
Suppose that a random selection of students will be able to screen a new movie early. There are
four screening sessions. For scheduling purposes, each of the selected students will specify which
of the four screenings don’t conflict with their schedule—every student is available for at least two
out of the four screenings. However, each screening has only 20 available seats, not all of which
need to be filled each time. The event organizers are faced with a difficult scheduling problem:
how do they make sure each of the chosen students is able to find a seat at a screening? They’ve
recruited you to help solve this dilemma.
(a) Describe how to model this situation as a matching problem. Be sure to specify what
the vertices/edges should be and briefly describe how a matching would determine seat
assignments for each student in a screening for which they are available. (This is a modeling
problem; we aren’t looking for a description of an
(b) Suppose 41 students have been selected. Can you guarantee that a matching exists, or are
there some situations where not all of the 41 students can be accommodated? Briefly explain.
(c) If instead only 40 students are chosen, prove that there is always a matching. Hint: Use Hall’s
Theorem or something similar. Is your graph degree constrained?
Step by step
Solved in 2 steps
