Suppose that a new company has five employees: Agraharam, Chou, McIntyre, Smith, and Zamora. Each employee will assume one of six responsibilities: develop- ment, industry relations, marketing, planning, publicity, and sales. Each employee is capable of doing one or more of these jobs.
Zamora could do planning, sales, marketing, or industry relations; Agraharam could do planning or development; Smith could do publicity, sales, or industry relations; Chou could do planning, sales, or industry relations; and Macintyre could do planning, publicity, sales, or industry relations.
a) Model the capabilities of these employees using a bipartite graph.
b) Find an assignment of responsibilities such that each employee is assigned one responsibility.
c) Is the matching of responsibilities you found in part (b) a complete matching? Is it a maximum matching?