5.8 Graph Matching Example: set of worker assign to a set of task Four tasks are to be assigned to four tasks workers. workers A Worker I is qualified to do tasks b and o B Worker 2 is qualified to do tasks AC and D Worker 3 is qualified to do tasks B and d 4 Worker 4 is qualified to do task a and c Can all 4 workers be assigned to different tasks for which they are qualified?
5.8 Graph Matching ▪ Example: Set of worker assign to a set of task ▪ Four tasks are to be assigned to four workers. ▪ – Worker 1 is qualified to do tasks B and C ▪ – Worker 2 is qualified to do tasks A,C and D ▪ – Worker 3 is qualified to do tasks B and D ▪ – Worker 4 is qualified to do task A and C. ▪ Can all 4 workers be assigned to different tasks for which they are qualified?
Example 2: The Marriage Problem: Given a set of men, each of whom knows some women from a given set of women, under what conditions is it possible for all men to marry women they know? Four men each know some of four women Peter knows Mary and Ann Kevin knows Mary, Ann, Rose and Tina Brian knows Mary and Ann Fred knows Ann Is it possible for all the men to marry women they know? Graph matching ary eter ose Brian ●Tina Fred
▪ Example 2: The Marriage Problem:Given a set of men, each of whom knows some women from a given set of women, under what conditions is it possible for all men to marry women they know? ▪ Four men each know some of four women ▪ Peter knows Mary and Ann ▪ Kevin knows Mary, Ann, Rose and Tina ▪ Brian knows Mary and Ann ▪ Fred knows Ann ▪ Is it possible for all the men to marry women they know? ▪ Graph Matching
Definition 36: A matching M in a graph g(v; e)is a subset of the edge set e such that no two edges in M are incident on the same vertex. The size of a matching M is the number of edges in M. For a graph G(v; E), a matching of maximum size is called a maximum matching M1={el,e7},M2={el,e2,e5},M3 Rel, e2, e5, e6and M4 e2 Rel, e2, e7, e8 are matching. M3 and m4 are maximum matching 98
▪ Definition 36: A matching M in a graph G(V;E) is a subset of the edge set E such that no two edges in M are incident on the same vertex. The size of a matching M is the number of edges in M. For a graph G(V;E), a matching of maximum size is called a maximum matching. M1={e1,e7},M2={e1,e2,e5},M3 ={e1,e2,e5,e6}and M4= {e1,e2,e7,e8} are matching. M3 and M4 are maximum matching
Definition 37: If M is a matching in a graph G. a vertex v is said to be m-saturated if there is an edge in M incident on v. Vertex v is said to be m-unsaturated if there is no edge in m incident onv M={el,e7},M3={el,e2,e5,e6} MI-saturated: v /e2 MI-unsaturated: u M3-saturated: uv e
▪ Definition 37: If M is a matching in a graph G, a vertex v is said to be M-saturated if there is an edge in M incident on v. Vertex v is said to be M-unsaturated if there is no edge in M incident on v. M1={e1,e7}, M3={e1,e2,e5,e6} M1-saturated : v M1-unsaturated: u M3-saturated:u,v
2 M={el,e3,e7,e8}, MIel, e3, e5, e61 e 3 MI and m are perfect matching. e e e8 e 62 Definition 38: A matching M of g is perfect if all vertices of g are M-saturated. If g(vi;v2)is a 8 bipartite graph then a matching M of g that saturates all the vertices in VI is called a complete matching from VI to V2
▪ Definition 38: A matching M of G is perfect if all vertices of G are M-saturated. If G(V1;V2) is a bipartite graph then a matching M of G that saturates all the vertices in V1 is called a complete matching from V1 to V2. M={e1,e3,e7,e8}, M1={e1,e3,e5,e6} M1 and M are perfect matching