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