[Nauty] Isomorphism test of labeled graphs
Brendan McKay
bdm at cs.anu.edu.au
Thu Oct 7 15:04:02 EST 2004
Hi. Your mail was delayed (and might have been lost forever) because it
had the sender address akerlund at cs.helsinki.fi but you are subscribed to
the list as arto.akerlund at cs.helsinki.fi . It has to be a perfect match.
(This is a Good Thing because it keeps out tons of spam messages.)
At
http://cs.anu.edu.au/mailman/listinfo/nauty-list
you can unsubscribe/subscribe to fix the problem. It is also ok to
subscribe with two different addresses. You can mark one as
no-delivery so you don't get two copies of everything.
The answer to your question is that the two coloured graphs you
describe are non-isomorphic and nauty finds them non-isomorphic.
Generally speaking, if a graph is adorned with things attached to
the edges or vertices, such as colours, labels, tags, weights,
or whatever they are called, the word "isomorphism" usually implies
that vertices/edges are only mapped to vertices/edges with equal
adornments. Nauty only knows about one type of adornment, namely
colours on the vertices.
Brendan.
* Arto J Akerlund, tkol <akerlund at cs.helsinki.fi> [041007 14:39]:
> Someone has asked something similar before and mr. McKay replied as
> follows.
>
> >Sorry, I somehow missed your message before. In order for two labelled
> >graphs to be isomorphic they must have the same number of vertices of
> >each colour. This is not tested by nauty!
>
> >*If* the graphs have the same number of vertices of each colour, then
> >you can test the graphs for isomorphism by finding the canonical graphs
> >and comparing those.
>
> >Incidentally, the values you put in ptn[] are examined for zero or
> >non-zero only, so there is no point in using values other than 0 and 1
> >(but it doesn't hurt either).
>
> But what if the case was like this.
>
> G1:
>
> A- - - - B
> | |
> | |
> B- - - - A
>
>
> G2:
>
> A- - - - A
> | |
> | |
> B- - - - B
>
> Data structures in nauty would thus be:
>
> G1:
> 0 : 1 3;
> 1 : 0 2;
> 2 : 1 3;
> 3 : 0 2;
> lab[0]=0; lab[1]=2; lab[2]=1; lab[3]=3;
> ptn[0]=1; ptn[1]=0; ptn[2]=1; ptn[3]=0;
>
> G2 :
> 0 : 1 3;
> 1 : 0 2;
> 2 : 1 3;
> 3 : 0 2;
> lab[0]=0; lab[1]=1; lab[2]=2; lab[3]=3;
> ptn[0]=1; ptn[1]=0; ptn[2]=1; ptn[3]=0;
>
>
>
> Now there's an equal number of verticles of both colour and if G1 and G2
> were unlabeled, they would be isomorphic. Is there a way to test
> isomorphims for labeled graphs so that graphs G1 and G2 wouldn't be
> isomorphic.
>
> I'm not exactly sure what is the mathematical definition of 'isomorphism
> of labeled graphs', but in my application G1 and G2 shouldn't be found
> identical anyway.
>
> _______________________________________________
> This is the nauty mailing list
> Post messages to nauty-list at cs.anu.edu.au
> nauty page: http://cs.anu.edu.au/~bdm/nauty/
> list page: http://cs.anu.edu.au/mailman/listinfo/nauty-list
More information about the Nauty
mailing list