Discrete Mathematics for Computer Science

332 CHAPTER 6 Graph Theory

Job Assignment Problem

GIVEN: A list of jobs to be filled and a list of job applicants who may be qualified

for more than one job.

FIND: An assignment of each job to a qualified applicant with no applicant assigned

to more than one job.

For this problem, every job needs a qualified applicant, but not every applicant needs to be

assigned to a job. Obviously, a necessary condition for the assignment problem to have a

positive solution is that the number of applicants must be at least as large as the number of

jobs. Clearly, however, this is not a sufficient condition, because two of the job applicants

could be qualified for exactly one and the same job as well as not qualified for any other job.

The first step toward the problem's solution will be to find an appropriate model. In

this case, we will use a graph. To begin, we present an intuitive notion of graphs; a more

formal introduction to this structure will follow.

The data for the Job Assignment Problem is shown in Table 6.1.

Table 6.1 Qualified Applicants and Jobs

Qualified Applicant Job

Jack technical writer

Jack market analyst

James sales representative

Jane photographer

Jane copy editor

Jane production manager

John photographer

John technical writer

June copy editor

June production manager

June sales representative

Table 6.1 suggests that the information can be represented as a relation between pairs of

objects, with one object being a qualified applicant and the other being a job. A graphical

representation of this information for Jane is shown in Figure 6.1.

photographer

Jane copy editor

production

Figure 6.1 Applicant and jobs. manager