Code covered by the BSD License  

Highlights from
Matgraph

Matgraph

by

 

14 Mar 2008 (Updated )

Toolbox for working with simple, undirected graphs

Checking graph isormorphism in Matgraph

Checking graph isormorphism in Matgraph

We show how to determine if two graphs are isomorphic and, if so, how to find the permutation that transforms one into the other.

Contents

Cycle graph

Create two copies of a cycle on 10 vertices, but randomly renumber the second.

g = graph;
h = graph;
cycle(g,10);
cycle(h,10);
renumber(h,random(permutation(nv(h))));
figure(1); clf; ndraw(g);
figure(2); clf; ndraw(h);

[yn,p] = iso(g,h)

renumber(g,p)
if g==h
	disp('Graphs are the same')
else
	disp('Graphs are different')
end
yn =
     1
(1)(2,9,4,3,7,5)(6)(8,10)
Graphs are the same

Large, vertex regular graph

The bucky graph is a vertex transitive graph with 60 vertices. We make two copies (one that is randomly renumbered) and check they are the same.

bucky(g);
bucky(h);
renumber(h,random(permutation(nv(h))));

[yn,p] = iso(g,h)

renumber(g,p)
if g==h
	disp('Graphs are the same')
else
	disp('Graphs are different')
end
yn =
     1
(1)(2,28,6,55,16,24,27,45,8,21,13,43,54,19,12,35,49,56,4,32,52,57,47,51,60,15,3,30,11,41,10,33,59,58,53,40,37,44)(5,34,39,42,9,46,38,18)(7,14,25,36,23,20,29)(17,31)(22,48)(26)(50)
Graphs are the same

Standard random graph

We generate a standard Erdos-Renyi random graph and a randomly renumbered copy, and then verify they are isomorphic.

random(g,100,0.5)
copy(h,g)
renumber(h,random(permutation(nv(h))));

[yn,p] = iso(g,h);

renumber(g,p)
if g==h
	disp('Graphs are the same')
else
	disp('Graphs are different')
end
Graphs are the same

Random regular graph

We generate a random 3-regular graph and a randomly renumbered copy, and then verify they are isomorphic.

random_regular(g,100,3);
copy(h,g);
renumber(h,random(permutation(nv(h))));

[yn,p] = iso(g,h);

renumber(g,p)
if g==h
	disp('Graphs are the same')
else
	disp('Graphs are different')
end
Graphs are the same

Random tree

We generate a random tree and a randomly renumbered copy, and then verify they are isomorphic.

random_tree(g,100);
copy(h,g);
renumber(h,random(permutation(nv(h))));

[yn,p] = iso(g,h);

renumber(g,p)
if g==h
	disp('Graphs are the same')
else
	disp('Graphs are different')
end
Graphs are the same

Two ways to make a grid

We generate a grid graph in two different ways. The graphs are not equal, but they are isomorphic.

grid(g,6,3);
grid(h,3,6);
if g==h
	disp('Graphs are the same')
else
	disp('Graphs are different')
end

[yn,p] = iso(g,h)

renumber(g,p)
if g==h
	disp('Graphs are the same')
else
	disp('Graphs are different')
end
Graphs are different
yn =
     1
(1)(2,4,10,11,14,6,16,12,17,15,9,8,5,13,3,7)(18)
Graphs are the same

Mobius and non-Mobius ladders are not isomorphic

The Mobius ladder on 20 vertices and the Cartesian product of a 10-cycle and an edge are both 3-regular graphs on 20 vertices. But they are not isomorphic.

mobius(g,20);
c10 = graph; cycle(c10,10);
k2 = graph; add(k2,1,2);
cartesian(h,c10,k2);

figure(1); clf; draw(g);
distxy(h);
figure(2); clf; draw(h);

[yn,p] = iso(g,h)

if yn
	disp('Graphs are isomorphic')
else
	disp('Graphs are not isomorphic')
end
Optimization terminated: relative function value
 changing by less than OPTIONS.TolFun.
Embedding score = 20.7351
Elapsed time is 2.634896 seconds.
yn =
     0
()
Graphs are not isomorphic

Release storage

free(g); free(h); free(c10); free(k2);

Contact us