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.
Following the lead in Example 14, we construct a bipartite graph in which the vertex set consists of two subsets—one for the employees and one for the jobs. Let V1 = {Zamora, Agraharam, Smith, Chou, Macintyre}, and let V2 = {planning, publicity,sales, marketing, development, industry relations}. Then the vertex set for our graph is V = V1 ∪ V2 . Given the list of capabilities in the exercise, we must include precisely the following edges in our graph: {Zamora, planning}, {Zamora,sales}, {Zamora, marketing}, {Zamora, industry relations}, {Agraharam, planning}, {Agraharam, development}, {Smith, publicity}, {Smith,sales}, {Smith, industry relations}, {Chou, planning}, {Chou,sales}, {Chou, industry relations}, {Macintyre, planning}, {Macintyre, publicity}, {Macintyre,sales}, {Macintyre, industry relations}.
b) Find an assignment of responsibilities such that each employee is assigned one responsibility.
Following the lead in Example 14, we construct a bipartite graph in which the vertex set consists of two subsets—one for the employees and one for the jobs. Let V1 = {Zamora, Agraharam, Smith, Chou, Macintyre}, and let V2 = {planning, publicity,sales, marketing, development, industry relations}. Then the vertex set for our graph is V = V1 ∪ V2 . Given the list of capabilities in the exercise, we must include precisely the following edges in our graph: {Zamora, planning}, {Zamora,sales}, {Zamora, marketing}, {Zamora, industry relations}, {Agraharam, planning}, {Agraharam, development}, {Smith, publicity}, {Smith,sales}, {Smith, industry relations}, {Chou, planning}, {Chou,sales}, {Chou, industry relations}, {Macintyre, planning}, {Macintyre, publicity}, {Macintyre,sales}, {Macintyre, industry relations}.
c) Is the matching of responsibilities you found in part (b) a complete matching? Is it a maximum matching?
Following the lead in Example 14, we construct a bipartite graph in which the vertex set consists of two subsets—one for the employees and one for the jobs. Let V1 = {Zamora, Agraharam, Smith, Chou, Macintyre}, and let V2 = {planning, publicity,sales, marketing, development, industry relations}. Then the vertex set for our graph is V = V1 ∪ V2 . Given the list of capabilities in the exercise, we must include precisely the following edges in our graph: {Zamora, planning}, {Zamora,sales}, {Zamora, marketing}, {Zamora, industry relations}, {Agraharam, planning}, {Agraharam, development}, {Smith, publicity}, {Smith,sales}, {Smith, industry relations}, {Chou, planning}, {Chou,sales}, {Chou, industry relations}, {Macintyre, planning}, {Macintyre, publicity}, {Macintyre,sales}, {Macintyre, industry relations}.