Discrete Mathematics for Computer Science

Introduction to Graph Theory 333

A line or edge from a person to a job represents the fact that the person is qualified for

that job. The picture that represents all the data in the problem is shown in Figure 6.2.

photographer

John

technical writer

Jane

copy editor

James

production manager

Jack

sales representative

June

market analyst

Figure 6.2 Set of applicants and set of jobs.

The structure in Figure 6.2 is called a graph. The assignment problem is to choose a
set of the edges (lines joining pairs of points) such that each job is at the end of at most
one edge and no applicant is at the end of more than one edge. In this example, there are
more jobs than applicants, so it will be impossible to fill all the jobs. One solution that finds
qualified applicants for five of the jobs is shown in Figure 6.3.

John "ý photographer

0 technical writer

Jane (^6) ý
copy editor
James
production manager
Jack
sales representative
June
market analyst
Figure 6.3 One set of job assignments.
An efficient algorithm for finding a solution to the assignment problem is an applica-
tion of the theory of flows in networks. A solution of the problem using flows has complex-
ity O(1V1^3 ) where V is the set of points in the graph. A discussion of flows in networks
can be found in most books dealing with algorithms.