You are viewing a free preview of this lesson.
Subscribe to unlock all 10 lessons in this course and every other course on LearningBro.
A matching in a bipartite graph is a set of edges with no shared vertices — each vertex is matched to at most one partner. The maximum matching problem and the allocation problem (assigning tasks to people at minimum cost) are key applications of discrete mathematics.
A bipartite graph has two sets of vertices (e.g., workers and jobs) with edges only between the sets. A matching pairs vertices from one set with vertices from the other so that no vertex appears in more than one pair.
| Term | Definition |
|---|---|
| Matching | A set of edges with no shared vertices |
| Maximum matching | A matching with the most edges possible |
| Complete matching | A matching that matches every vertex in the smaller set |
| Perfect matching | A matching that matches every vertex in both sets |
To improve a matching M:
Subscribe to continue reading
Get full access to this lesson and all 10 lessons in this course.