Ask Your Question
1

Working with unlabelled graphs

asked 2021-09-14 11:50:29 +0100

oldani gravatar image

I'm studying certain properties of graphs but I want to work with unlabelled ones i.e. I do not want to distinguish graphs that differs only by the numbering of vertices, which is the case by default if I have correctly understood. Is it possible?

Thanks

edit retag flag offensive close merge delete

2 Answers

Sort by ยป oldest newest most voted
0

answered 2021-09-14 22:41:07 +0100

Max Alekseyev gravatar image

updated 2021-09-15 14:56:16 +0100

It's unclear what do you mean under "distinguish". If it's about creation/generation of unlabeled graphs, then many graph construction methods produce unlabeled (di)graphs. If it's about comparison of unlabeled graphs, then this can be done via comparison of their canonical labels (.canonical_label()). So, example of what you want to achieve would be helpful.

edit flag offensive delete link more
0

answered 2021-09-14 21:06:53 +0100

slelievre gravatar image

Nauty has a generator of graphs up to isomorphism.

Sage has an interface to it.

See the nauty_geng function:

edit flag offensive delete link more

Comments

Graphs have the method is_isomorphic : G1.is_isomorphic(G2) is True if G2 is a relabelling of G1. I am not aware of a built-in way to designate the equivalence classes thus defined :however, my knowledge of (this part of) Sage is quite superficial.

Emmanuel Charpentier gravatar imageEmmanuel Charpentier ( 2021-09-14 22:50:52 +0100 )edit

Canonical representatives of the equivalence classes are produced by .canonical_label().

Max Alekseyev gravatar imageMax Alekseyev ( 2021-09-14 23:23:45 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2021-09-14 11:50:29 +0100

Seen: 721 times

Last updated: Sep 15 '21