布伦丹·麦凯(Brendan McKay)已经完成了查找n个变量的所有非同构图的工作，这些图可以在此处找到(在“简单图”下):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可用于简单图表的数据？
最佳答案
首先，您应该观察到，如果两个图不是同构的，则这些带有一些附加自环的图也不是同构的。
如果您在编程期间需要此程序，并且图形的大小很小，那么我将为每个非iso图生成所有可能的自环图。
最简单的方法是添加其他节点，每个具有自环的节点都将与给定节点连接。 (而不是具有循环)使用nauty，您可以检查是否两个同构。如果您观察到如果两个循环编码的版本是iso，那么它们还必须具有与“特殊”节点相同数量的连接，从而可以进一步加快速度。
关于c - 使用自环枚举图，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/6131784/