11.2.3. Expressing Problems as Linear Programs or Network Flows

Try these first

1. 1.

   Define a bipartite graph.

   Hint

   Think about graphs with 2 distinct categories.

2. 2.

   What is a matching in the context of bipartite graphs?

   Hint

   Consider how students can be paired with courses.

3. 3.

   What is a bipartite graph?

   Hint

   Think about how different categories relate!

4. 4.

   Bipartite matching can be expressed as what kind of flow?

   • Minimum Flow
   • Maximum Flow
   • Constant Flow

   Hint

   Consider what you want to achieve with matching!

5. 5.

   Consider a school with 5 teachers and 3 courses. Each teacher has a specific course they can teach. Formulate the problem as a bipartite graph and address how to maximize the teaching assignments.

   Hint

   Think about how to structure the preferences to visualize the connections.

6. 6.

   Given a scenario of job placement where 4 applicants can fill 6 different roles based on qualifications, how would you go about ensuring all roles available are filled?

   Hint

   Make sure to analyze the connections thoroughly.