枚举具有自循环的图形

Question

Brendan McKay已经完成了找到n个变量的所有非同构图的工作,这些图可以在这里找到(在Simple Graphs下):http://cs.anu.edu.au/~bdm/data/graphs.html

我相信这是使用polya枚举完成的,我理解了它的基础知识.我想对此进行扩展,并在这些图中允许自循环.所以,我想找到n个变量的所有非同构图,包括自循环.这将直接用于我的代码的另一部分,并提供大量优化.我只是不太确定如何去做.

为了清楚起见,Brendan Mckay的文件给出了所有非变形图,即边缘表示法,

1-2 1-3

是一个在顶点1和2之间以及1和3之间具有边缘的图.我希望​​此列表还包括自循环,即:

1-2 1-3 1-1

要么

1-2 1-3 1-1 2-2

我想要最少数量的图形,所以非所有非图形.我怎样才能找到它们,希望使用Brendan McKay可用于简单图形的数据？

Answer 1

首先，您应该观察到，如果两个图不是同构的，那么这些带有一些附加自循环的图也不是同构的。

如果您在编程期间需要这个并且图的大小很小，我将为每个非 iso 图生成所有可能的自循环图。

最简单的方法是添加额外的节点，每个具有自环的节点都将与给定的节点连接。（而不是有循环）使用 nauty 你可以检查是否有任何两个是同构的。如果您观察到如果两个循环编码版本都是 iso，那么它们必须与“特殊”节点具有相同数量的连接，那么您还可以加快速度。