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