Matchings and flows

From Algorithmist
Jump to: navigation, search

Definitions :

Bipartite Graph : a Graph whose vertices can be split into two groups such that there's no edge between two vertices
of the same group.
Matching in a Bipartite Graph : Let we Call the above groups A and B.
Then a matching is pairing nodes from A with nodes from B (nodes u and v must have an edge 
between them to be paired ), such that every node is paired with one another node only.
Maximum Matching : is a matching which has the maximum possible pairs of nodes.
Perfect Matching : is a matching where every node is paired.