判断图同构大杀器—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)


相关推荐

  • 出现这6个信号,领导要提拔你!看懂了升职加薪,看不懂错失良机

    出现这6个信号,领导要提拔你!看懂了升职加薪,看不懂错失良机

  • WPF 入门教程WrapPanel介绍「建议收藏」

    WPF 入门教程WrapPanel介绍「建议收藏」WrapPanel将定位每个子控件的旁边,另外,水平方向(默认值)或垂直,直到没有更多的空间,在那里将换到下一行,然后继续。当您想要一个垂直或水平列表控件在没有更多空间时自动换行时使用它。当WrapPanel使用Horizo​​ntal方向时,子控件将被赋予相同的高度,基于最高的项目。当WrapPanel为垂直方向时,子控件将被赋予相同的宽度,基于最宽的项目。在第一个示例中,我们将检查具有默认(水平)方向的WrapPanel:<Windowx:Class=”WpfTu

  • 【软件工程】详细设计说明书

    【软件工程】详细设计说明书详细设计说明书1引言1.1编写目的说明编写这份详细设计说明书的目的,指出预期的读者。该文档实在概要设计的基础上,进一步的细化系统结构,展示了软件啊结构的图标,物理设计,数据结构设计,及算法设计,详细的介绍了系统各个模块是如何实现的,包括涉及到的算法,逻辑流程等,为下一步系统的实现和测试做准备!1.2背景说明:a.软件名称:机房收费系统;b.本项目的任务提出者:米新江…

  • oracle设置用户密码永不过期_oracle密码设置无限期

    oracle设置用户密码永不过期_oracle密码设置无限期1、查看用户的proifle是哪个,一般是default:sql>SELECTusername,PROFILEFROMdba_users;2、查看指定概要文件(如default)的密码有效期设置:sql>SELECT*FROMdba_profilessWHEREs.profile=’DEFAULT’ANDresource_name=’PASSWORD_LIFE_TIME’;3、将密码有效期由默认的180天修改成“无限制”:sql>ALTERPROF

  • ggplot2数据分析与图形艺术_plot画多条曲线

    ggplot2数据分析与图形艺术_plot画多条曲线接着我们之前复现过的一篇NC文章(复现《naturecommunications》散点小提琴图+蜜蜂图),有一张关于差异蛋白的火山图,但是不同的是他的阈值设定不是我们普通的横向纵向,而是曲线阈值!image.png本来我以为这是一个个例,本篇文章作者博眼球的做法,但是检索了一下发现我付肤浅了,有很多文章,但是有一个特点,双曲线阈值应用在蛋白组差异基因的筛选上,这样的方式类似与“软阈值”吧,能够找到更显著的蛋白,值得在自己的研究中使用。image.png(Reference:ProteomicsofMe

  • MySQL导入sql文件的三种方法

    MySQL导入sql文件的三种方法文章目录一、使用工具NavicatforMySQL导入1.打开localhost_3306,选中右击“新建数据库”3.指定数据库名和字符集(可根据sql文件的字符集类型自行选择)3.选中数据库下的表运行SQL文件4.选中路径导入二、使用MySQLWorkbench导入(MySQL的官方工具)1、第一种方法①.新建一个数据库demo(名字任取),点击指示图标(或者File栏里面的OpenSQLScript…)②.选中路径导入SQL文件③.添加指定库名的命令,并点击运行注意:大概在15、16行

发表回复

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

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