Code covered by the BSD License

# Matgraph

### Ed Scheinerman (view profile)

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.

## 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);
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);
```