11.2.2. Network Flows

Try these first

1. 1.

   Define a bipartite graph.

   Hint

   Think about how the vertices are structured.

2. 2.

   What is a perfect matching?

   Hint

   Consider scenarios with distinct pairs.

3. 3.

   What is a bipartite graph?

   • A graph with one set of vertices
   • A graph with two distinct vertex sets
   • A graph with edges only between its vertices

   Hint

   Remember the characteristics of vertex sets.

4. 4.

   True or False: A perfect matching can exist in an unbalanced bipartite graph.

   • True
   • False

   Hint

   Consider the implications of unequal sets.

5. 5.

   Imagine a scenario with three courses and five teachers, each having different preferences. Model this using a bipartite graph, and determine if a perfect matching exists.

   Hint

   Check each teacher’s preferences and map them accordingly.

6. 6.

   Transform the following teacher-course assignments into a network flow diagram: Teacher 1 (Math, History), Teacher 2 (Biology), Teacher 3 (Economics). How would you represent this in a flow network?

   Hint

   Visualize how flow connects the teachers to the courses.