Matching in a graph
Matching in a bipartite graph: maximal and maximum matchings, free vertex, alternating and augmenting paths, the augmenting-path algorithm and Hall's condition.
- 27 cards
- 4 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The steps
A few cards from the deck
Matching: what is it?
Show the answer
A set of edges of a graph, no two of which share an endpoint.
Each vertex is used at most once: an intern can be placed in only one company, and a company takes only one intern.
Interns A, B, C; companies 1, 2, 3; wishes A1, A2, B1, C2, C3. Among these sets of edges, which is a matching?
{A2, B1}{A1, B1}{A2, C2}{C2, C3}
Show the answer
{A2, B1}In
{A2, B1}no vertex is repeated.{A1, B1}gives company 1 to two interns;{A2, C2}does the same with company 2;{C2, C3}places C twice.A vertex that no edge of the matching reaches is called …; a matching that leaves none is called ….
Show the answer
A vertex that no edge of the matching reaches is called free; a matching that leaves none is called perfect.
A perfect matching covers every vertex: so it is maximum, and the graph necessarily has an even number of vertices.
Bipartite graph: what is it?
Show the answer
A graph whose vertices split into two groups, every edge joining a vertex of one to a vertex of the other.
Interns on one side, companies on the other: no edge joins two interns, nor two companies. A matching there always pairs an intern with a company.
The augmenting-path algorithm: which step comes after "Start from a matching, even an empty one"?
- Pick a free vertex
- Look for an alternating path to another free vertex
- Flip the edges of that path
- Repeat until no such path exists
Show the answer
Pick a free vertex
Flipping only makes sense once the path is found, and we stop when the search fails: the matching is then maximum.