25.1.4. Types of Matching

Try these first

1. 1.

   Define a bipartite graph.

   Hint

   Focus on the structure and edges of the graph.

2. 2.

   What is matching in the context of bipartite graphs?

   Hint

   Think about how tasks can be assigned without overlaps.

3. 3.

   A matching in a bipartite graph must ensure that:

   • No edges share a vertex.
   • All vertices are included in the matching.
   • Each vertex can handle multiple jobs.

   Hint

   Think about the core definition of matching.

4. 4.

   True or False: A maximum matching can be a maximal matching.

   • True
   • False

   Hint

   Consider how 'maximum' and 'maximal' are defined.

5. 5.

   Consider a bipartite graph with 5 employees and 3 tasks. If two employees can do all tasks but one, and the rest of employees can do none, explain how a complete matching might work.

   Hint

   Map each employee’s preferences to visualize the match.

6. 6.

   Create a bipartite graph that illustrates the failure of Hall’s condition. What implications does this have for completing a matching?

   Hint

   Identify subsets and neighbors for rigorous analysis.