判断图同构大杀器—nauty算法

全栈程序员-站长 • 2022年4月8日下午6:40 • 未分类 • 阅读 35

大家好，又见面了，我是你们的朋友全栈君。

判断两图是否同构是一个经典问题。
nauty算法作为时下较为流行的主流算法，具有效率高，剪枝力度强等优势。当然，在某些特殊情况会失灵。
虽然该算法的概念在上世纪80年代就提出来了，但发展至今，仍然是不可忽略的一种方法。

本人翻遍了中文互联网，没找到详细相关介绍，在stack overflow上边找到了一个问答，顺着帖子的回复找到了算法原作者自建的网站，如获至宝。
再结合离散数学，看懂了这个算法的大致流程。总结如下：

nauty算法：判断两个图是否同构。
思路：
①设置一套编号系统，给两个图进行编号，如果两个图对应的正则编号是一样的，两图同构。

②设置编号系统：
1）对图进行划分，使得任意一个节点的不同颜色的邻接节点的个数相同。
2）对于包含节点个数大于1的子集合再划分，一直化到所有子集合元素个数为1。
3）回溯，得到第二个划分。对比两个划分方式，得到置换群信息，利用这一信息去剪枝。
4）回溯，得到第三个划分，再得到一些置换群的信息，进一步剪枝。
5）最终存留的划分结果即是这个图的可行的命名方式。选择其中最大字典的一种作为正则编号，与另外一个图进行比对。

③剪枝过程中还利用了【节点不变量】信息。具体来说，用一个函数评价某节点的【节点不变量】。
在同一深度下，某节点的函数值相较另一个节点高，则正则编号将出现在该节点的子树下。
在同一深度下，某节点的函数值与另一个节点不相等，则二者的子树不一样。
两节点在某一群作用下相同，则两节点的子树有对应相等值。

部分理解存在偏差，对该算法感兴趣的朋友可以去作者自建的网站了解详情，里边有漂亮的PPT，排版也很好。

另外，nauty算法剪枝的核心是求解自同构群，这一过程在网站的search tree那一栏也有详尽的说明（类似PPT），结合基础群论知识，很容易理解。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/126816.html原文链接：https://javaforall.net