418 CHAPTER 6 Graph Theory
cost. Repeat the procedure if there must be a data link between branches 2 and 5.
Repeat the procedure if branches 1 and 4 cannot be connected by a data line.- Suppose that a group of computers were linked together in a simple ring as shown:
A B
In this arrangement, each computer can communicate directly with the computers on
either side of it. Since the communication lines are all separate, each computer can
pass information to the computer to the right of it all at the same time. To pass a
message from computer A to computer B, just pass it along the line from computer to
computer until it reaches its destination. The communication lines are supposed to be
bidirectional, so the message can be passed in seven steps if it is passed to the right
and in three steps if passed to the left.
Some obvious graph-theoretic data are important to how quickly the computers
can share information and to how much it costs to connect the computers together. For
example, consider:
(a) The Degree of the Graph: The maximum degree of any vertex. For example, in the
graph shown, each computer has a degree of two, so the degree of the entire graph
is two. Here, the communication lines are fairly cheap to build. If the degrees of
each vertex were large, or if there were many interconnections then the network
of computers would be much more expensive to build.
(b) The Diameter of the Graph: The maximum distance between any two vertices.
For example, in a path with n vertices, the diameter is n. For such a graph, it
can take a relatively long time to send information from one computer to another.
This also means that a programmer, trying to get maximum programming speed
out of such a computer configuration, will have to program very cleverly to avoid
communication taking too long.
For each of the following graphs, compute the degree and diameter of the graph:
(a) A complete graph with n vertices.
(b) A hypercube with n vertices. (Of course, here, n has to be a power of 2.)
(c) A complete binary tree (see Exercise 25 in Section 6.13) with n vertices where
n = 2m - 1 for some non-negative integer m:
Level 0
Level 1
Level 2
Level 3(d) A square grid with n vertices (pictured with 16 vertices):
•-0-e-•--0
I I _ I II I I _ I
I I I
O--0 -S-0-