25.1.4.3. Complete Matching

Try these first

1. 1.

   What is a bipartite graph?

   Hint

   Think about how vertices can be categorized.

2. 2.

   Define maximum matching in a bipartite graph.

   Hint

   Consider the total number of pairs.

3. 3.

   Which of the following defines a bipartite graph?

   • A graph with all vertices connected to each other.
   • A graph whose vertices can be divided into two sets.
   • A graph without edges.

   Hint

   Think about how vertices are grouped.

4. 4.

   True or False: A maximal matching is always a maximum matching.

   • True
   • False

   Hint

   Consider the sizes of the matchings.

5. 5.

   Design a bipartite graph representing a system where seven students need to be assigned to five projects. Demonstrate if a complete matching is possible based on the skills listed for each student.

   Hint

   Use Hall's theorem to check if the coverage is sufficient.

6. 6.

   Given a bipartite graph showing four employees and their skills related to three tasks, demonstrate potential matchings and identify which type of matching it constitutes.

   Hint

   Compare the number of skills to needed tasks.