Suppose that a new company has five employees: Zamora, Agraharam, Smith, Chou, and Macintyre. Each employee will assume one of six responsibilities: planning, publicity, sales, marketing, development, and industry relations. 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?