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

判断两图是否同构是一个经典问题。nauty算法作为时下较为流行的主流算法,具有效率高,剪枝力度强等优势。当然,在某些特殊情况会失灵。虽然该算法的概念在上世纪80年代就提出来了,但发展至今,仍然是不可忽略的一种方法。本人翻遍了中文互联网,没找到详细相关介绍,在stackoverflow上边找到了一个问答,顺着帖子的回复找到了算法原作者自建的网站,如获至宝。再结合离散数学,看懂了这个算法的大致流程。总结如下:nauty算法:判断两个图是否同构。思路:①设置一套编号系统,给两个图进行编号,如果两个

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

判断两图是否同构是一个经典问题。
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账号...

(0)


相关推荐

  • java如何打印数组的值,Java打印数组元素的值[通俗易懂]

    java如何打印数组的值,Java打印数组元素的值[通俗易懂]本篇文章帮大家学习java打印数组元素的值,包含了Java打印数组元素的值使用方法、操作技巧、实例演示和注意事项,有一定的学习价值,大家可以用来参考。以下实例演示了如何通过重载MainClass类的printArray方法输出不同类型(整型,双精度及字符型)的数组:publicclassMainClass{publicstaticvoidprintArray(Integer[…

  • Linux下查看CPU型号,内存大小,硬盘空间的命令(详解)

    Linux下查看CPU型号,内存大小,硬盘空间的命令(详解)

  • 【C语言】求最小公倍数和最大公约数(辗转相除法)

    【C语言】求最小公倍数和最大公约数(辗转相除法)用到的名词:最小公倍数,最大公约数,辗转相除法一、名词解释:1).最小公倍数:最小公倍数(LeastCommonMultiple,LCM),如果有一个自然数a能被自然数b整除,则称a为b的倍数,b为a的约数,对于两个整数来说,指该两数共有倍数中最小的一个。计算最小公倍数时,通常会借助最大公约数来辅助计算。 最小公倍数=两数的乘积/最大公约(因)数,解题时要避免和最大公约(因)…

  • setContentView剖析[通俗易懂]

    setContentView剖析[通俗易懂]1、setContentView的作用是将View加载到根view之上,这样当显示view时,先显示根view,然后在显示子view,以此类推,最终将所有view显示出来。2、setContentView必须要放在findviewbyid之前,因为view在加载之前是无法引用的。3、setContentView最本质的作用是为要显示的view分配内存。4、act

  • No input file specified的解决方法apache伪静态

    No input file specified的解决方法apache伪静态

  • 详解网站WEB日志格式

    详解网站WEB日志格式WEB日志是网站的WEB服务处理程序,根据一定的规范生成的ASCII文本。它主要记录了网站访问记录数据内容,是网站分析和网站数据仓库的数据基础来源,而网站分析和数据分析也将对SEO产生一定的影响,所以了解WEB日志的格式和组成将有利于我们更好地进行网站数据的收集、处理和分析,从而更好的进行网站优化。一、WEB日志格式分类目前常见的WEB日志格式主要由两类,一类是Apache的NCSA日志格

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号