D1 - Matchings Flashcards
0
Q
What is a complete matching?
A
When each node has a matching.
1
Q
What is a bi partied graph?
A
A graph with two sets of nodes.
Arcs connect different sets but never two nodes in the same set.
2
Q
How do you use the maximum matching algorithm?
A
Start with any initial matching.
Look for an alternating path.
If one cannot be found stop.
3
Q
What is an alternating path?
A
Starts at an unmatched node on one set and finished at an unmatched node on the other set.
Alternately she’s arcs that are not in or in the initial matching.
