Page 684 - Discrete Mathematics and Its Applications

10.2 Graph Terminology and Special Types of Graphs 663

in exactly one bit. The hypercube network balances the number of direct connections for each
processor and the number of intermediate connections required so that processors can com-
municate. Many computers have been built using a hypercube network, and many parallel
algorithms have been devised that use a hypercube network. The graph Q m , the m-cube, rep-
m
resents the hypercube network with n = 2 processors. Figure 14 displays the hypercube net-
work for eight processors. (Figure 14 displays a different way to draw Q 3 than was shown in
Figure 6.) ▲

New Graphs from Old

Sometimes we need only part of a graph to solve a problem. For instance, we may care only
about the part of a large computer network that involves the computer centers in New York,
Denver, Detroit, and Atlanta. Then we can ignore the other computer centers and all telephone
lines not linking two of these specific four computer centers. In the graph model for the large
network, we can remove the vertices corresponding to the computer centers other than the four
of interest, and we can remove all edges incident with a vertex that was removed. When edges
and vertices are removed from a graph, without removing endpoints of any remaining edges, a
smaller graph is obtained. Such a graph is called a subgraph of the original graph.

DEFINITION 7 A subgraph of a graph G = (V, E) is a graph H = (W, F), where W ⊆ V and F ⊆ E.A
subgraph H of G is a proper subgraph of G if H
= G.

Given a set of vertices of a graph, we can form a subgraph of this graph with these vertices
and the edges of the graph that connect them.

DEFINITION 8 Let G = (V, E) be a simple graph. The subgraph induced by a subset W of the vertex set V
is the graph (W, F), where the edge set F contains an edge in E if and only if both endpoints
of this edge are in W.

EXAMPLE 18 The graph G shown in Figure 15 is a subgraph of K 5 . If we add the edge connecting c and e to
G, we obtain the subgraph induced by W ={a, b, c, e}. ▲

REMOVING OR ADDING EDGES OF A GRAPH Given a graph G = (V, E) and an edge
e ∈ E, we can produce a subgraph of G by removing the edge e. The resulting subgraph, denoted
by G − e, has the same vertex set V as G. Its edge set is E − e. Hence,

G − e = (V, E −{e}).

Similarly, if E is a subset of E, we can produce a subgraph of G by removing the edges in E

from the graph. The resulting subgraph has the same vertex set V as G. Its edge set is E − E .
a a

e b b
e
P 0 P 1 P 2 P 3 P 4 P 5 P 6 P 7

d c c

FIGURE 14 A Hypercube Network for Eight Processors. FIGURE 15 A Subgraph of K 5 .