Matchings Flashcards
0
Q
Matching
A
A way of pairing the vertices of a bipartite graph so that no edges share a vertex
1
Q
Bipartite graph
A
Has two sets of vertices, the edges of which are only connected to vertices from the other set
2
Q
Maximum matching
A
A bipartite graph which contains the largest possible number of edges
3
Q
Complete matching
A
Connect every single vertex
4
Q
Why is it complete matching not always possible?
A
If 2 vertices want to connect up to 1 vertices
5
Q
What is the alternating path algorithm used for?
A
For finding a maximum possible matching
