Page 689 - Discrete Mathematics and Its Applications

668 10 / Graphs

61. If the simple graph G has v vertices and e edges, how 68. Show that (G conv conv = G whenever G is a directed
)
many edges does G have? graph.
62. If the degree sequence of the simple graph G is 69. Show that the graph G is its own converse if and only if the
4, 3, 3, 2, 2, what is the degree sequence of G? relation associated with G (see Section 9.3) is symmetric.
63. If the degree sequence of the simple graph G is 70. Show that if a bipartite graph G = (V, E) is n-regular for
d 1 ,d 2 ,...,d n , what is the degree sequence of G? some positive integer n (see the preamble to Exercise 53)
∗ 64. Show that if G is a bipartite simple graph with v vertices and (V 1 ,V 2 ) is a bipartition of V , then |V 1 |=|V 2 |. That
2
and e edges, then e ≤ v /4. is, show that the two sets in a bipartition of the vertex set
65. Show that if G is a simple graph with n vertices, then the of an n-regular graph must contain the same number of
union of G and G is K n . vertices.
∗ 66. Describe an algorithm to decide whether a graph is bipar- 71. Draw the mesh network for interconnecting nine parallel
tite based on the fact that a graph is bipartite if and only processors.
if it is possible to color its vertices two different colors 72. Inavariantofameshnetworkforinterconnecting n = m 2
so that no two vertices of the same color are adjacent. processors, processor P(i, j) is connected to the four pro-
The converse of a directed graph G = (V, E), denoted cessors P((i ± 1) mod m, j) and P(i, (j ± 1) mod m),
by G conv , is the directed graph (V, F), where the set F so that connections wrap around the edges of the mesh.
of edges of G conv is obtained by reversing the direction of Draw this variant of the mesh network for 16 processors.
each edge in E. 73. Show that every pair of processors in a mesh network
√
2
67. Draw the converse of each of the graphs in Exercises 7–9 of n = m processors can communicate using O( n) =
in Section 10.1. O(m) hops between directly connected processors.
10.3 Representing Graphs and Graph Isomorphism

Introduction

There are many useful ways to represent graphs. As we will see throughout this chapter, in
working with a graph it is helpful to be able to choose its most convenient representation. In
this section we will show how to represent graphs in several different ways.
Sometimes, two graphs have exactly the same form, in the sense that there is a one-to-one
correspondence between their vertex sets that preserves edges. In such a case, we say that the
two graphs are isomorphic. Determining whether two graphs are isomorphic is an important
problem of graph theory that we will study in this section.

Representing Graphs

One way to represent a graph without multiple edges is to list all the edges of this graph.Another
way to represent a graph with no multiple edges is to use adjacency lists, which specify the
vertices that are adjacent to each vertex of the graph.
EXAMPLE 1 Use adjacency lists to describe the simple graph given in Figure 1.

Solution: Table 1 lists those vertices adjacent to each of the vertices of the graph. ▲

b TABLE 1 An Adjacency List
for a Simple Graph.
a c
Vertex Adjacent Vertices
a b, c, e
b a
c a, d, e
e d d c, e
e a, c, d
FIGURE 1 A Simple Graph.