ConceptTheory & Algos
Perfect matching
A matching in a graph where every vertex is incident to exactly one edge of the matching.
Know first
Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.
Opens up
Concepts that name this one as a prerequisite.
Lecturers
3Each in their own terms, from the easiest level.
Tom Leighton
A matching is perfect if its size is equal to half the number of nodes in the graph.Ryan O'Donnell
A set of edges in a bipartite graph such that every vertex is incident to exactly one edge in the set.
Lectures that assume it
1Connections
13The lectures that define it or assume it, and the concepts next to it.
Concepts9
- Bipartite graph
- Edge
- Graph
- Matching
- Bipartite max perfect matching
- Bipartite max perfect matching problem