11.1.3. Perfect Match and Network Flows

Try these first

1. 1.

   Define a bipartite graph.

   Hint

   Think about how vertices are organized.

2. 2.

   What does a perfect match in a bipartite graph mean?

   Hint

   Consider what 'one-to-one' pairing means.

3. 3.

   What is a bipartite graph?

   • A graph with only one set of vertices
   • A graph where edges connect two distinct sets of vertices
   • A graph with cycles only

   Hint

   Think about how vertices are paired.

4. 4.

   True or False: A perfect matching requires that at least one vertex in the bipartite graph be left unmatched.

   • True
   • False

   Hint

   Relate this to the definition of 'perfect'.

5. 5.

   Consider a school with 5 teachers: T1, T2, T3, T4, T5 and 4 courses: C1, C2, C3, C4. The preferences are as follows: T1 (C1, C2), T2 (C2, C3), T3 (C3), T4 (C1), T5 (C2, C4). Determine if a perfect matching exists and justify your answer.

   Hint

   Remember to evaluate all teachers' potential matches before concluding.

6. 6.

   A university has to assign courses among 6 professors and 5 classes, where classes have specific capacity limits and professors have their preferences. Develop a flow network and find a maximum flow configuration that indicates potential assignments.

   Hint

   Keep track of the flow capacities while ensuring no professor is overloaded beyond their willing assignments.