Hopcroft-Karp algorithm for matching in bipartite graphs

Matchings in Graphs Lecturer: Meena Mahajan Scribe: Rajesh Chitnis Meeting: 1 6th Jan 2010 Most of the material in this lecture is taken from the book Fast Parallel Algorithms for Graph Matching Problems" by Karpinski and Rytter, [KR98]. We will only be considering simple undirected nite graphs unless stated otherwise. Graphs will be denoted as G = (V;E). 1 Some preliminary de nitions De nition 1 Let G = (V;E) be a graph. M E is called as a matching

of G if 8v2V we have jfe2M : v is incident on e2Egj 1. De nition 2 A matching M of G is said to be maximal if 8e2EnM the set of edges given by M[feg is not a matching of G. De nition 3 The size of a matching M of G is the number of the edges it contains and is denoted by jMj. De nition 4 A matching M of G is said to be maximum if 8 matching M0 of G we have jMj jM0j. A maximum matching is always maximal but not vice-versa. De nition 5 Let M be matching of G. A vertex v2V is said to be M-saturated if M contains an edge incident on v. Otherwise v is said to be M-unsaturated or M-free. De nition 6 A matching M of G is said to be perfect if all vertices of G are M-saturated. A graph with an odd number of vertices can never admit a perfect matching. De nition 7 A matching M of G is said to be near-perfect if exactly one vertex of G is M-unsaturated. A graph with an even number of vertices can never admit a near-perfect...

Website: www.cin.ufpe.br | Filesize: -
No of Page(s): 7
Download Hopcroft-Karp algorithm for matching in bipartite graphs - CIn.pdf