Section 6.1 Graphs and Their Representations
485
Structures that are the same except for relabeling are called isomorphic structures. To show that two structures are isomorphic, we must produce a relabeling
(one-to-one, onto mappings between the elements of the two structures) and then
show that the important properties of the structures are “preserved” (maintained)
under this relabeling. In the case of graphs, the elements are nodes and arcs. The
“important property” in a graph is which arcs connect which nodes.
The given mappings f 1 and f 2 are one-to-one, onto functions from the nodes
and arcs, respectively, of the graph in Figure 6.14 to the nodes and arcs of the graph
in Figure 6.16. Furthermore, if an arc a in the graph of Figure 6.14 has endpoints x–y,
then the arc f 2 (a) in the graph of Figure 6.16 has endpoints f 1 (x) –f 1 ( y), and vice versa.
For example, arc a 1 in Figure 6.14 has endpoints 1–3, while its corresponding arc e 2 in
Figure 6.16 has endpoints a–b, which are the nodes in Figure 6.16 that correspond to
nodes 1 and 3 in Figure 6.14. We can formalize this idea.
1
3
a 1
4
2
a 2
Figure 6.14
a 1
2
3
1
4
a 2
Figure 6.15
e 2
a
b
d
c
e 1
Figure 6.16
Definition IsomorphIc Graphs
Two graphs (N 1 , A 1 , g 1 ,) and (N 2 , A 2 , g 2 ) are isomorphic if there are bijections
f 1 : N 1 S N 2 and f 2 : A 1 S A 2 such that for each arc a [ A 1 , g 1 (a) = x–y if and
only if g 2 3 f 2 (a) 4 = f 1 (x) –f 1 ( y).
example 11
The graphs shown in Figure 6.17 are isomorphic. The bijections that establish the
isomorphism are partially given here:
f 1 : 1 S c
f 2 : a 1 S e 1
2 S e
a 2 S e 4
3 S d
a 3 S e 2
4 S b
…
5 S a
a 1
a
b
e 5
e 7
e 8
e 6
d e 3
e 1
c
e 4
e 2
e
a 2
a 3
a 6
a 5
a 7
a 4
a 8
1
2
3
4
5
Figure 6.17