[Nauty-list] graph isomorphism
Gordon Royle
gordon at maths.uwa.edu.au
Wed Feb 18 12:19:30 EST 2009
On 18/02/2009, at 9:51 AM, Sara Voss wrote:
> Is there a way for Nauty to find the following two graphs isomorphic?
>
> graph 1 graph2
> 0 = 1 0 = 1
> || || || ||
> 2 = 3 3 = 2
>
> Nauty produces different canonical labellings for these graphs. I'm
It shouldn't...
Here is a "dreadnaut" run with some comments...
(1) Start up dreadnaut and enter the graph, use "t" to type it out
Dreadnaut version 2.4 (32 bits).
> n=4
> g
0 : 1 2;
1 : 3;
2 : 3.
> t
0 : 1 2;
1 : 0 3;
2 : 0 3;
3 : 1 2;
(2) Turn on "canonical labelling", then run nauty, then print the
"canonically labelled graph"
> c
> x
(1 2)
level 2: 3 orbits; 1 fixed; index 2
(0 1)(2 3)
level 1: 1 orbit; 0 fixed; index 4
1 orbit; grpsize=8; 2 gens; 6 nodes; maxlev=3
tctotal=8; canupdates=1; cpu time = 0.00 seconds
> b
0 1 2 3
0 : 1 2;
1 : 0 3;
2 : 0 3;
3 : 1 2;
Note that the labelling required (the line 0 1 2 3) is the identity
so the canonically labelled graph is the same as the original.
(3) Enter the second graph, run nauty and type the canonically
labelled graph
> g
0 : 1 3;
1 : 2;
2 : 3.
> t
0 : 1 3;
1 : 0 2;
2 : 1 3;
3 : 0 2;
> x
(1 3)
level 2: 3 orbits; 1 fixed; index 2
(0 1)(2 3)
level 1: 1 orbit; 0 fixed; index 4
1 orbit; grpsize=8; 2 gens; 6 nodes; maxlev=3
tctotal=8; canupdates=1; cpu time = 0.00 seconds
> b
0 1 3 2
0 : 1 2;
1 : 0 3;
2 : 0 3;
3 : 1 2;
This time the permutation required is 0 1 3 2 and so the canonically
labelled graph is NOT the initial graph but in fact equal to the first
graph.
Gordon
More information about the Nauty
mailing list