25.1. Introduction to Bipartite Graphs and Matching

Try these first

1. 1.

   What defines a bipartite graph?

   Hint

   Think about how subsets are structured.

2. 2.

   What is a matching in graph theory?

   Hint

   Consider the relationships between nodes.

3. 3.

   What is a bipartite graph?

   • A graph with cycles
   • A graph with two disjoint sets
   • A graph with no edges

   Hint

   Recall the definition of bipartite.

4. 4.

   True or False: A maximum matching can have less edges than a maximal matching.

   • True
   • False

   Hint

   Consider the meanings of maximal vs maximum.

5. 5.

   Given a bipartite graph with specific employees and their skills, determine if a complete matching exists and justify your answer using Hall's Theorem.

   Hint

   Work through subsets systematically.

6. 6.

   Create a scenario involving 5 tasks and 3 employees, provide a bipartite graph, and manually demonstrate whether a complete matching can be achieved.

   Hint

   Look at overlapping skills closely!