Examples of isomorphic and non-isomorphic graphs
G1 G2
a b 1 2
e
6 5
f
c d 4 3
|V(G1)| = 6 |V(G2)| = 6
|E(G1)| = 9 |E(G2)| = 9
is regular = true is regular = true
max degree = 3 max degree = 3
diameter = 2 diameter = 2
no. of triangles = 0 no. of triangles = 2
( triangles 1-4-6 and 2-3-5 )
PAL 2020/04 Graph isomorphism notes 1
Examples of isomorphic and non-isomorphic graphs
b 1
G1 G2
a c 2 3
e d 4 5
|V(G1)| = 5 |V(G2)| = 5
|E(G1)| = 6 |E(G2)| = 6
min degree = 2 min degree = 2
max degree = 3 max degree = 3
degree sequence = [3 3 3 3 2] degree sequence = [3 3 3 3 2]
... ...
etc. The question ? etc.
remains:
Are G1 and G2 isomorphic to each other?
?
PAL 2020/04 Graph isomorphism notes 2
Examples of isomorphic and non-isomorphic graphs
b 1
G1 G2
a c 2 3
e d 4 5
G1: Set of
G1: Set of edges: G2: Set of edges:
mapped edges:
{ {a e} Nodes { {4 2} { {1 2}
{a b} mapping: {4 5} {1 3}
{b c} a --- 4 {5 3} {1 5}
{c e} b --- 5 {3 2} {2 3}
{e d} c --- 3 {2 1} {2 4}
{c d} d --- 1 {3 1} {3 5}
{b d} } e --- 2 {5 1} } {4 5} }
G3 Both sets of edges are the same. G1 and G2 are isomorphic.
(Verification: Sort all sets, compare items one by one.)
PAL 2020/04 Graph isomorphism notes 3
Examples of isomorphic and non-isomorphic graphs
a b G1 G2 1 2 3
c d e 4 5 6 7
f g h 8 9 10 11
i j k 12 13 14
l m |V(G1)| = 14 |V(G2)| = 14
|E(G1)| = 16 |E(G2)| = 16
n
degree sequence = degree sequence =
[3 3 3 3 2 2 2 2 2 2 2 2 2 2] [3 3 3 3 2 2 2 2 2 2 2 2 2 2]
diameter = 7, ( distance(l, e) ) diameter = 7, ( distance(4, 11) )
isBipartite = yes isBipartite = yes
... ...
The question
?
remains:
Are G1 and G2 isomorphic to each other?
?
PAL 2020/04 Graph isomorphism notes 4
Examples of isomorphic and non-isomorphic graphs
a b G1 G2 1 2 3
c d e 4 5 6 7
f g h 8 9 10 11
i j k 12 13 14
l m multisets of degrees multisets of degrees
of neighbours of neighbours
n of nodes with degree 3: of nodes with degree 3:
{ {3 2 2} // d { {3 2 2} // 5
{3 2 2} // f {3 2 2} // 6
{3 3 2} // g {3 2 2} // 9
{3 3 2} } // j {3 2 2} } // 10
G1 and G2 are not isomorphic to each other.
Another Invariant:
G1 -- nodes of degree 3 G2 -- nodes of degree 3
form a connected subgraph. form two mutually unconnected subgraphs.
More invariants: Try yourself....
PAL 2020/04 Graph isomorphism notes 5
Difficulty
Is there any set of properties which are (relatively) easy to calculate for any graph
and which values would decide whether two given graphs G 1, G2 are isomorphic?
In the sense:
values calculated on G1 == values calculated on G2
if and only if
G1 is isomorphic to G2
So far, no such set of properties is known in general.
Partial solution
Advanced heuristical approaches solve the problem in many practical settings:
SW: nauty and Traces: [Link]
based on papers by Brendan [Link] and AdolfoPiperno: Practical graph isomorphism I and II.
[Link]
[Link]
PAL 2020/04 Graph isomorphism notes 6
Examples of isomorphic and non-isomorphic graphs
Isomorphism is difficult to confirm/reject when the graphs are highly symmetric.
Informally, symmetry means that a graph "looks the same" in the vicinity of each node.
The number of candidate bijections is then difficult to reduce when there are no obvious
invariants which values would help to distinguish between different nodes.
As a simple example, consider the following pair of graphs.
Picture credit to [Link] and code
g1 = [Link](19, [1,5,8] ); [Link]()
PAL 2020/04 Graph isomorphism notes g2 = [Link](19, [1,4,7] ); [Link]() 7
Isomorphism of directed graphs
In these slides, term graph always refers to an undirected graph, if not specified otherwise.
All isomorphism properties, algorithms, notions, etc. defined for undirected graphs,
can be analogously defined and analyzed/solved in analogous manner
for directed graphs.
Two directed graphs G1=(V1,E1) and G2=(V2,E2) are isomorphic
if there is a bijection f : V1 → V2 such that
∀ x, y V1 : (f (x), f (y)) E2 ⇔ (x, y) E1
Example:
G1 G2 G3
Graphs G1 and G2 are isomorphic, G3 is not isomorphic to any of G1,
G2.
PAL 2020/04 Graph isomorphism notes 8
N Number f(N) of graphs on N nodes (incl. unconnected ones) [Link]
1 1
2 2 N
Approximation of 2
( 2)
3 4 f(N) ≤
the number of graphs: N!
4 11
5 34
6 156 f(N)
7 1044 The formula approximates lim =1
N
8 12346 f(N) tightly, in the sense:
N
2
()
2
9 274668 N!
10 12005168
15 31426485969804308768
20 645490122795799841856164638490742749440 ~ 6.5 ∙ 1038
30 3344943163092576692494395699280800289566314799353930643299678348872177345348
80582749030521599504384 ~ 3.3 ∙ 1098
7793841167914977954582550817575177766066055272533160501864210580719699592280
40 7665987621085074589139360819329653520373728865932592867538838570163833079818
63462449691949358853053120648183808 ~ 7.8 ∙ 10186
N see inset
Applying brute force and checking all graphs for would be a hopeless effort.
PAL 2020/04 Graph isomorphism notes 9
N Number f'(N) of connected graphs on N nodes [Link]
1 1
2 1
3 2
4 6
5 21
6 112
7 853
8 11117
9 261080
10 11716571
15 31397381142761241960
20 645465483198722799426731128794502283004
30 3344942976179029274740625889887714205924003404484971757354867875739197630926
64433461017585013705594
7793841167347901373159586190645563996131177435680973666982243627070377497235
40 4174178748323987582425416768805527046107079810797229883124475331332011126406
04192083672776028633590109166374659
N asymptotically same as all graphs, in the sense: lim { N , f'(N) / f(N) } = 1
Applying brute force and checking all graphs for would be a hopeless effort.
PAL 2020/04 Graph isomorphism notes 10
N Number f''(N) of undirected trees on N nodes [Link]
1 1
2 1
3 1
4 2
5 3
6 6
7 11
8 23
9 47
10 106
15 7741
20 823065
30 14830871802 ~ 1.5 ∙ 1010
40 363990257783343 ~ 3.6 ∙ 1014
100 630134658347465720563607281977639527019590
N Formula is too complex to fit here, see the OEIS reference above
Applying brute force and checking all trees would be a hopeless effort.
PAL 2020/04 Graph isomorphism notes 11
Examples of more graph invariants (a tiny! selection):
(.) Connected - yes/no
(.) Number of edges
(.) Bipartite - yes/no
(.) Regular - yes/no (the degree of all nodes is the same)
(.) Tree - yes/no
(.) Planar - yes/no (can be drawn in a plane without edges crossing)
(X) Hamiltonian - yes/no (Hamilton path or cycle exists in the graph)
(.) Maximum/maximum node degree
(.) Number of nodes with maximum (minimum degree)
(.) Degree sequence (sequence of all node degrees sorted in non-increasing order)
(X) Spectrum (= multiset of eigenvalues) of adjacency (Laplacian) matrix of the graph
(X) Length of the shortest cycle (so called girth of the graph)
(X) Number of triangles
(.) Number of bridges/cutvertices/blocks
(X) Number of automorphisms
(X) Chromatic/independence/dominancy/clique numbers (see respective definitions...)
(X) Diameter, excentricity, number of centers
(X) Bandwidth
...
(.) O(E+V), (X) more complex than O(E+V), polynomial or exponential.
PAL 2020/04 Graph isomorphism notes 12
Two random graphs are extremely(!) probably NOT isomorphic
When two graphs G1, G2 are selected randomly from the set of all graphs on N nodes or
when they are generated randomly, then
A. The probability that G1 and G2 are isomorphic is very close to 0. *)
B. The probability that the values of some (in fact, of many) of invariants in G1 and G2 are
different is very close to 1.
A. Very probably, G1 and G2 are not isomorphic.
B. Very probably, it is (relatively) easy to verify G1 and G2 are not isomorphic .
Conclusion:
When the graphs are not isomorphic,
checking the values of various (easy to compute, preferentially! ) invariants in both graphs,
quickly confirms the fact in majority of (random) cases.
*) How close? The probability p is in the order of n! / 2comb(n,2).
For example, n = 10, p = 10! / 245 107; n = 100, p = 100! / 24950 101332.
PAL 2020/04 Graph isomorphism notes 13
Tree certificate example
01 01 01 01 01 0011 0011 01
d c b a c b
01 g f e 01 01 g f e 0011
01 01
k j h i j
01 01 01 01 01 001011 01 01
0011 00011011 00011011
b
nondecreasing
lexicographic order
00010111 g f 0011 00010111 f
000111 0000101110001101100111
001011
PAL 2020/04 Graph isomorphism notes 14
Tree certificate example
0 1
f
01 01 01 01
d c b a 1
0 0 1 0
g 1 b e
01 g f e 01
0 1 0 1 0 1 0 1
01 j c a i
k j h i 0 1
0 1 0 1
01 01 01 01 k h d
0000101110001101100111
0000101110001101100111
PAL 2020/04 Graph isomorphism notes 15
Tree certificate example
01 01 01 01
d c b a 0 1
f
0 0 1 1
01 g f e 01 g 1 b 0 e
01
k j h i 0 1 0 1 0 1 0 1
j c a i
01 01 01 01
0 1 0 1 0 1
0000101110001101100111 k h d
0000101110001101100111
Perform DFS from the root == center of the tree. Always expand DFS into that subtree
which certificate is lexicographically the smallest.
Output 0 when the node is being open and output 1 when the node is being closed.
The output sequence is the tree certificate, it is obvious by induction.
Drawback: DFS cannot know the subtrees certificates in advance.
The idea can be used only for reconstructing the tree from the certificate.
PAL 2020/04 Graph isomorphism notes 16
Tree certificate example
proc reconstructTree( certificate )
nodesList = emptyList()
edgesList = emptyList() 0 f1
centers = emptyList() // one or two centers
0 e1
stack = emptyStack() 0 g1 0 b1
for digit in certificate
if digit == '0' 0 j 1 0 c 1 0 a1 0 i 1
create node X
[Link]( X ) 0 k 1 0 h1 0 d1
if [Link]()
[Link]( X ) 0000101110001101100111
else
[Link]( pair([Link](),X) )
[Link]( X )
else // digit == '1' 0 1 0 1
f m
[Link]()
0 0 b1 0 i 1 0 e1
g 1
if [Link]() == 2 // two centers
0 1 0 1 0 1 0 1
[Link]( pair(centers[0],centers[1]) ) j c a l
return nodesList, edgesList, centers
0 1 0 1 0 1 0 1
k h d n
0000101110001101110000111011
PAL 2020/04 Graph isomorphism notes 17
Tree certificate example - Python reconstruction
def reconstruct( certificate ):
nodes, edges, stack = [], [], [] 0 1 0 1
centers = [] # 1 or 2 centers f m
newNode = 0 # nodes are integers 0
g 1 0 b1 0 i 1 0 e1
for digit in certificate: 0 1 0 1 0 1 0 1
if digit == '0': j c a l
newNode += 1 # 'create' new node 0 1 0 1 0 1 0 1
[Link]( newNode ) k h d n
if len( stack ) == 0: # empty 0000101110001101110000111011
[Link]( newNode )
else:
[Link]( [newNode, stack[-1]] )
[Link]( newNode )
else: # digit == '1':
[Link]()
if len( centers ) == 2:
[Link]( [centers[0], centers[1]] )
return nodes, edges, centers
cer = "0000101110001101110000111011"
nodes, edges, centers = reconstruct( cer )
PAL 2020/04 Graph isomorphism notes 18