大家好，又见面了，我是你们的朋友全栈君。
判断两图是否同构是一个经典问题。 nauty算法作为时下较为流行的主流算法，具有效率高，剪枝力度强等优势。当然，在某些特殊情况会失灵。 虽然该算法的概念在上世纪80年代就提出来了，但发展至今，仍然是不可忽略的一种方法。
本人翻遍了中文互联网，没找到详细相关介绍，在stack overflow上边找到了一个问答，顺着帖子的回复找到了算法原作者自建的网站，如获至宝。 再结合离散数学，看懂了这个算法的大致流程。总结如下：
nauty算法：判断两个图是否同构。 思路： ①设置一套编号系统，给两个图进行编号，如果两个图对应的正则编号是一样的，两图同构。
②设置编号系统： 1）对图进行划分，使得任意一个节点的不同颜色的邻接节点的个数相同。 2）对于包含节点个数大于1的子集合再划分，一直化到所有子集合元素个数为1。 3）回溯，得到第二个划分。对比两个划分方式，得到置换群信息，利用这一信息去剪枝。 4）回溯，得到第三个划分，再得到一些置换群的信息，进一步剪枝。 5）最终存留的划分结果即是这个图的可行的命名方式。选择其中最大字典的一种作为正则编号，与另外一个图进行比对。
③剪枝过程中还利用了【节点不变量】信息。具体来说，用一个函数评价某节点的【节点不变量】。 在同一深度下，某节点的函数值相较另一个节点高，则正则编号将出现在该节点的子树下。 在同一深度下，某节点的函数值与另一个节点不相等，则二者的子树不一样。 两节点在某一群作用下相同，则两节点的子树有对应相等值。
部分理解存在偏差，对该算法感兴趣的朋友可以去作者自建的网站了解详情，里边有漂亮的PPT，排版也很好。
另外，nauty算法剪枝的核心是求解自同构群，这一过程在网站的search tree那一栏也有详尽的说明（类似PPT），结合基础群论知识，很容易理解。
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/126816.html原文链接：https://javaforall.cn
