Graph Theory
Computer scientists use graphs to model problems as diverse as how to detect a dead-
lock condition in an operating system and how to plan efficient routings for transportation
networks. Some problems in artificial intelligence use efficient searching procedures on
the class of graphs called trees as effective heuristics. The scheduling of a sequence of
subassemblies so that no assembly process starts without all its required subassemblies
having been completed is also a problem that can be modeled and solved using directed
graphs. Some of the most difficult AJP-complete problems involve finding special sub-
graphs within large graphs. This chapter introduces graphs as a structure that is used to
represent and solve many problems in a variety of areas in computer science.
The chapter is organized into four main parts. The first introduces the terms that are
used to describe this structure. The second focuses on ideas dealing with graphs that are
connected. As an application of this idea, we will examine Euler's theorem, the first the-
orem of graph theory. This theorem explains when it is possible, for example, to stroll
across a series of bridges and return to the starting point without crossing any bridge twice.
The theorem can even tell how to plot a graph without taking the pen off the paper too
many times. The third part of the chapter covers the special graphs called trees. Trees are
a common data structure in computer science that are used to solve searching and sorting
problems. Finally, the last part of the chapter deals with directed graphs, which extend the
idea of a graph to include the notion of direction. Directed graphs are used to represent
and solve problems such as scheduling a production of subassemblies with no unnecessary
delays or designing a one-way street grid.
We begin the study of this important mathematical theory by examining a problem for
which graph theory may be used to build a model of the problem.Introduction to Graph Theory
The problem we use to introduce graph theory involves filling positions from a pool of
qualified applicants.
331