Matchings and flows
Jump to navigation Jump to search
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.