Page 662 - Discrete Mathematics and Its Applications

CH A P TER

10 Graphs

10.1 Graphs and raphs are discrete structures consisting of vertices and edges that connect these vertices.
Graph Models GThere are different kinds of graphs, depending on whether edges have directions, whether
multiple edges can connect the same pair of vertices, and whether loops are allowed. Problems
10.2 Graph in almost every conceivable discipline can be solved using graph models. We will give examples
Terminology to illustrate how graphs are used as models in a variety of areas. For instance, we will show how
and Special graphs are used to represent the competition of different species in an ecological niche, how
Types of graphs are used to represent who influences whom in an organization, and how graphs are used
Graphs
to represent the outcomes of round-robin tournaments. We will describe how graphs can be used
10.3 Representing to model acquaintanceships between people, collaboration between researchers, telephone calls
Graphs and between telephone numbers, and links between websites. We will show how graphs can be used
Graph to model roadmaps and the assignment of jobs to employees of an organization.
Isomorphism Using graph models, we can determine whether it is possible to walk down all the streets
10.4 Connectivity in a city without going down a street twice, and we can find the number of colors needed to
color the regions of a map. Graphs can be used to determine whether a circuit can be imple-
10.5 Euler and mented on a planar circuit board. We can distinguish between two chemical compounds with the
Hamilton
same molecular formula but different structures using graphs. We can determine whether two
Paths
computers are connected by a communications link using graph models of computer networks.
10.6 Shortest-Path Graphs with weights assigned to their edges can be used to solve problems such as finding the
Problems shortest path between two cities in a transportation network. We can also use graphs to schedule
exams and assign channels to television stations. This chapter will introduce the basic concepts
10.7 Planar Graphs
of graph theory and present many different graph models. To solve the wide variety of problems
10.8 Graph that can be studied using graphs, we will introduce many different graph algorithms. We will
Coloring also study the complexity of these algorithms.

10.1 Graphs and Graph Models

We begin with the definition of a graph.

DEFINITION 1 A graph G = (V, E) consists of V , a nonempty set of vertices (or nodes) and E, a set of
edges. Each edge has either one or two vertices associated with it, called its endpoints.An
edge is said to connect its endpoints.

Remark: The set of vertices V of a graph G may be infinite. A graph with an infinite vertex
set or an infinite number of edges is called an infinite graph, and in comparison, a graph with
a finite vertex set and a finite edge set is called a finite graph. In this book we will usually
consider only finite graphs.

Now suppose that a network is made up of data centers and communication links between
computers.We can represent the location of each data center by a point and each communications
link by a line segment, as shown in Figure 1.
This computer network can be modeled using a graph in which the vertices of the graph
represent the data centers and the edges represent communication links. In general, we visualize

641