5.2 Finding maximum matchings Flashcards
1
Q
Why doesn’t a greedy algorithm always work for matching
A
Can block more elements by greedily choosing a matching
2
Q
What is an augmenting path in a bipartite graph
A
3
Q
What is the switch function for an augmenting path
A
Switches unmatched edges with matched edges
4
Q
Why does switching always contain an additional edge in the new matching
A
Since starts and ends at unmatched vertex, these vertices will now be matched, more than making up for the one other connection lost (squint not proof)
5
Q
What is the psuedocode for the max-matching algorithm
A
D(m) is a a dirgaph, directing non-matching edges
from A to B and matching edges from B to A
6
Q
What is the runtime of MaxMatching
A
7
Q
What is Berge’s Lemma
A
