Suppose that a new company has ?ve employees: Zamora,Agraharam, Smith, Chou, and

Question

Suppose that a new company has ?ve employees: Zamora,Agraharam, Smith, Chou, and Macintyre. Each employee will assume one of six responsiblities: 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 responsibilites 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?

Explanation / Answer

a.)place all the emplyoees in one partite set and all the responsibilities in the other partite set.Now each employee is mapped to the jobs that he is capable to do. thus we can form a bipartite graph b.)after forming the bipartite graph apply maximum flow algorithm and find maximum matching thus we get Zamora -----marketing Agraharam--------development Smith -----------publicity Chou --------planning Macintyre ------------sales c) it is not a complete matching since industrial relations is not there in matching It is a maximum matching.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.