Page 667 - Discrete Mathematics and Its Applications

646 10 / Graphs

COMMUNICATIONNETWORKS Wecanmodeldifferentcommunicationsnetworksusing
vertices to represent devices and edges to represent the particular type of communications links
of interest. We have already modeled a data network in the first part of this section.
EXAMPLE 4 Call Graphs Graphs can be used to model telephone calls made in a network, such as a long-
distance telephone network. In particular, a directed multigraph can be used to model calls where
each telephone number is represented by a vertex and each telephone call is represented by a
directed edge. The edge representing a call starts at the telephone number from which the call
was made and ends at the telephone number to which the call was made. We need directed edges
because the direction in which the call is made matters. We need multiple directed edges because
we want to represent each call made from a particular telephone number to a second number.
A small telephone call graph is displayed in Figure 8(a), representing seven telephone
numbers. This graph shows, for instance, that three calls have been made from 732-555-1234
to 732-555-9876 and two in the other direction, but no calls have been made from 732-555-4444
to any of the other six numbers except 732-555-0011. When we care only whether there has been
a call connecting two telephone numbers, we use an undirected graph with an edge connecting
telephone numbers when there has been a call between these numbers. This version of the call
graph is displayed in Figure 8(b).
Call graphs that model actual calling activities can be huge. For example, one call graph
studied atAT&T, which models calls during 20 days, has about 290 million vertices and 4 billion
edges. We will discuss call graphs further in Section 10.4. ▲

INFORMATION NETWORKS Graphs can be used to model various networks that link
particular types of information. Here, we will describe how to model the World Wide Web using
a graph. We will also describe how to use a graph to model the citations in different types of
documents.
EXAMPLE 5 The Web Graph The World Wide Web can be modeled as a directed graph where each Web
page is represented by a vertex and where an edge starts at the Web page a and ends at the
Web page b if there is a link on a pointing to b. Because new Web pages are created and others
removed somewhere on the Web almost every second, the Web graph changes on an almost
continual basis. Many people are studying the properties of the Web graph to better understand
the nature of the Web. We will return to Web graphs in Section 10.4, and in Chapter 11 we will
explain how the Web graph is used by the Web crawlers that search engines use to create indexes
of Web pages. ▲

EXAMPLE 6 Citation Graphs Graphs can be used to represent citations in different types of documents,
including academic papers, patents, and legal opinions. In such graphs, each document is rep-
resented by a vertex, and there is an edge from one document to a second document if the

732-555-1001 732-555-1001

732-555-1234 732-555-4444 732-555-1234 732-555-4444

732-555-0069 732-555-0069

732-555-0011 732-555-0011
732-555-9876 732-555-9876

732-555-6666 732-555-6666
(a) (b)

FIGURE 8 A Call Graph.