25.1.1. Job Assignment Problem

Try these first

1. 1.

   What is a bipartite graph?

   Hint

   Think of two groups with connections only between them.

2. 2.

   Define maximum matching.

   Hint

   It's about finding the biggest collection of edges.

3. 3.

   What is a bipartite graph?

   • A graph with edges connecting in one set only
   • A graph with edges connecting two distinct vertex sets
   • A graph with no connections

   Hint

   Think about how the vertices are connected.

4. 4.

   True or False: A maximal matching is the largest matching possible.

   • True
   • False

   Hint

   Consider what 'maximal' means.

5. 5.

   Given a bipartite graph with four employees and three tasks where each employee can handle two tasks, find if a complete matching may be achieved without repeat assignments.

   Hint

   Map tasks to available employees carefully.

6. 6.

   Create a real-world scenario that demonstrates Hall's Marriage Theorem, emphasizing the relationship between tasks and resources. Provide a diagram.

   Hint

   Use a visual aid to assist in your explanation.