使用自循环枚举图
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 提供的简单图表数据？
Brendan McKay has already done the work for finding all non-isomorphic graphs of n variables that can be found here (under Simple Graphs): http://cs.anu.edu.au/~bdm/data/graphs.html
I believe this was done using polya enumeration, which I understand the basics of. I would like to expand on this, and allow self loops in these graphs. So, i'd like to find all non-ismorphic graphs of n variables, including self loops. This will be directly used for another part of my code and provide a massive optimization. I'm just not quite sure how to go about it.
To be clear, Brendan Mckay's files give all non ismorphic graphs, ie in edge notation,
1-2 1-3
is a graph with an edge between vertex 1 and 2, and 1 and 3. I want this list to also include self loops, ie:
1-2 1-3 1-1
or
1-2 1-3 1-1 2-2
I want the minimum number of graphs, so all non-ismorphic ones. How can I go about finding them, hopefully using the data Brendan McKay has available for simple graphs?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
首先，您应该观察到，如果两个图不是同构的，那么这些带有一些附加自循环的图也不是同构的。
如果您在编程期间需要这个并且图的大小很小，我将为每个非 iso 图生成所有可能的自循环图。
最简单的方法是添加额外的节点，每个具有自环的节点都将与给定的节点连接。 （而不是有循环）使用 nauty 你可以检查是否有任何两个是同构的。如果您观察到如果两个循环编码版本都是 iso，那么它们必须与“特殊”节点具有相同数量的连接，那么您还可以加快速度。
First of all, you should observe that if two graphs are not isomorphic, then these graphs with some additional self loops are not isomorphic.
If you need this during programming and size of graphs is small, I would generate for each non iso graph all possible self loop graphs.
Easiest thing to do is to add additional node, and every node with self loop will be connected with given node. (instead of having loop) Using nauty you can check if any two are isomorphic. You can additionally speed up things if you observe that if two loop encoded versions are iso, then they have to have same number of connections with "special" node.