11.1.2. Big Hammers in Algorithms

Try these first

1. 1.

   What is a bipartite graph?

   Hint

   Think about how teachers and courses can connect.

2. 2.

   What does the term 'matching' refer to in the context of bipartite graphs?

   Hint

   Consider the connection between teachers and subjects.

3. 3.

   What is bipartite matching?

   • A matching that includes any network structure.
   • A special allocation where connections only exist between two distinct sets.
   • A random assignment of courses to any teacher.

   Hint

   Consider how teachers and courses are organized.

4. 4.

   True or False: In a bipartite matching, a teacher can teach multiple courses.

   • True
   • False

   Hint

   Think about the constraints of the matching problem.

5. 5.

   Given a set of 5 teachers and only 4 courses, devise a method to allocate courses while ensuring no teacher teaches more than one course and explain your reasoning.

   Hint

   Use the concept of capacities to frame your solution.

6. 6.

   If a specific teacher wishes to teach two courses and refuses to pick, how would this affect your bipartite graph and flow algorithm?

   Hint

   Consider how stubborn choices can limit overall network flow.