# Matchings and flows

Jump to navigation
Jump to 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.