使用自循环枚举图

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，那么它们必须有相同数量的带有“特殊”节点的连接，那么你可以额外地加快速度。