25.1.2. Modeling Job Assignments with Matching

Try these first

1. 1.

   What is a bipartite graph?

   Hint

   Remember the term 'bi' means two.

2. 2.

   Define matching.

   Hint

   Think about connections without overlap.

3. 3.

   What defines a bipartite graph?

   • True
   • False

   Hint

   Recall the definition features two groups.

4. 4.

   A maximum matching can be larger than a maximal matching.

   • True
   • False

   Hint

   Think about how many edges each can have.

5. 5.

   In a bipartite graph with employees A, B, and C, and modules 1, 2, and 3, if A can do modules 1 & 2, B can do 2 & 3, and C can do 1 & 3, illustrate if a complete matching exists.

   Hint

   Review potential overlaps in assignments.

6. 6.

   Create an example of a bipartite graph that demonstrates Hall's theorem failing to hold.

   Hint

   Count neighbors of the subset you select.