25.1.4.1. Maximum Matching

Try these first

1. 1.

   What is a bipartite graph?

   Hint

   Think about how we can categorize vertices.

2. 2.

   Define a matching in graph theory.

   Hint

   Consider how edges connect vertices.

3. 3.

   What distinguishes a maximum matching from a maximal matching?

   • Maximum matching can have more edges.
   • Maximum matching is the largest possible matching.
   • Maximal matching must have at least 5 edges.
   • All of the above.

   Hint

   Think about sizes and limitations of the matchings.

4. 4.

   True or False: Every maximum matching is also a maximal matching.

   • True
   • False

   Hint

   Consider if you can add more edges to maximum matching.

5. 5.

   Consider a bipartite graph with 3 employees (A, B, C) and 4 tasks (1, 2, 3, 4). If A can do 1, 2; B can do 1, 3; C can do 2, 4, demonstrate if a complete matching is possible.

   Hint

   Think about how many unique tasks are left.

6. 6.

   Given a bipartite graph with 5 vertices in each set and no missing edges, find out if it's possible to have a complete matching. Justify your answer.

   Hint

   Visualize potential connections.