486
Graphs and Trees
Graph isomorphism is easier to establish if we restrict our attention to simple
graphs. If we can find an appropriate function f 1 mapping nodes to nodes, then a
function f 2 mapping arcs to arcs is trivial because there is at most one arc between
any pair of endpoints. Hence the following theorem is true.
Using these bijections, g 1 (a 3 ) = 1–3 and g 2 3f 2 (a 3 ) 4 = g 2 (e 2 ) = c–d = f 1 (1)–f 1 (3).
We can see that the arc-to-endpoint relationship is preserved under the relabeling
for the case of arc a 3 . To prove that the graphs are isomorphic, we would have to
complete the definition of the f 2 function and then demonstrate that the arc-toendpoint relationship is preserved under these mappings by examining all possible
cases.
praCTiCe 7 Complete the definition of the function f 2 in Example 11.
■
tHeorem on simple Graph isomorphism
Two simple graphs (N 1 , A 1 , g 1 ) and (N 2 , A 2 , g 2 ) are isomorphic if there is a bijection f: N 1 S N 2 such that for any nodes n i and n j of N 1 , n i and n j are adjacent if
and only if f(n i ) and f(n j ) are adjacent. (The function f is called an isomorphism
from graph 1 to graph 2.)
praCTiCe 8 Find an isomorphism from the graph of Figure 6.18a to that of Figure 6.18b.
d
c
a
e
b
f
(b)
(a)
6
4
2
5
3
1
Figure 6.18
■
Proving that two graphs are isomorphic requires finding the bijection (or, for nonsimple graphs, bijections) and then showing that the adjacency property (or arc-to-endpoint relationship) is preserved. To prove that two graphs are not isomorphic, we must
prove that the necessary bijection(s) do not exist. We could try all possible bijections
(because there is a finite number of nodes and arcs, there is a finite number of bijections). However, this method would quickly get out of hand in graphs of any size at
all. Instead, we can try to find some other reason that such bijections could not exist.
Although this task is not always easy, there are certain conditions under which it is clear
that two graphs are not isomorphic (see Exercise 21). These include the following:
1. One graph has more nodes than the other.
2. One graph has more arcs than the other.
Graphs and Trees
Graph isomorphism is easier to establish if we restrict our attention to simple
graphs. If we can find an appropriate function f 1 mapping nodes to nodes, then a
function f 2 mapping arcs to arcs is trivial because there is at most one arc between
any pair of endpoints. Hence the following theorem is true.
Using these bijections, g 1 (a 3 ) = 1–3 and g 2 3f 2 (a 3 ) 4 = g 2 (e 2 ) = c–d = f 1 (1)–f 1 (3).
We can see that the arc-to-endpoint relationship is preserved under the relabeling
for the case of arc a 3 . To prove that the graphs are isomorphic, we would have to
complete the definition of the f 2 function and then demonstrate that the arc-toendpoint relationship is preserved under these mappings by examining all possible
cases.
praCTiCe 7 Complete the definition of the function f 2 in Example 11.
■
tHeorem on simple Graph isomorphism
Two simple graphs (N 1 , A 1 , g 1 ) and (N 2 , A 2 , g 2 ) are isomorphic if there is a bijection f: N 1 S N 2 such that for any nodes n i and n j of N 1 , n i and n j are adjacent if
and only if f(n i ) and f(n j ) are adjacent. (The function f is called an isomorphism
from graph 1 to graph 2.)
praCTiCe 8 Find an isomorphism from the graph of Figure 6.18a to that of Figure 6.18b.
d
c
a
e
b
f
(b)
(a)
6
4
2
5
3
1
Figure 6.18
■
Proving that two graphs are isomorphic requires finding the bijection (or, for nonsimple graphs, bijections) and then showing that the adjacency property (or arc-to-endpoint relationship) is preserved. To prove that two graphs are not isomorphic, we must
prove that the necessary bijection(s) do not exist. We could try all possible bijections
(because there is a finite number of nodes and arcs, there is a finite number of bijections). However, this method would quickly get out of hand in graphs of any size at
all. Instead, we can try to find some other reason that such bijections could not exist.
Although this task is not always easy, there are certain conditions under which it is clear
that two graphs are not isomorphic (see Exercise 21). These include the following:
1. One graph has more nodes than the other.
2. One graph has more arcs than the other.