11.1.2. Bipartite Graph

Try these first

1. 1.

   What defines a bipartite graph?

   Hint

   Think about the two-group structure.

2. 2.

   Why can't teachers be matched to courses they don't prefer?

   Hint

   Consider teacher qualifications.

3. 3.

   What characterizes a bipartite graph?

   • Edges between the same set
   • Edges only between different sets
   • All vertices connected

   Hint

   Refer back to the definition.

4. 4.

   True or False: In a bipartite graph, teachers can teach courses they initially didn't prefer.

   • True
   • False

   Hint

   Think about the consequences of misallocation.

5. 5.

   Given a bipartite graph of 3 teachers (T1, T2, T3) and 5 courses (C1 to C5), with the following preferences: T1(C1, C2), T2(C2, C3), T3(C4, C5). Determine if a perfect matching is possible.

   Hint

   Consider the number of vertices in both sets.

6. 6.

   Modify the graph from the previous problem to include a preference for T1 to teach C2 and C3. Analyze the impact on perfect matching.

   Hint

   Think about how additional edges affect matching possibilities.