引用本文
王卓, 王成红. 复杂无向图的同构判定方法. 自动化学报, 2024, 50(6): 1143−1150 doi: 10.16383/j.aas.c230612
Wang Zhuo, Wang Cheng-Hong. Isomorphism determination methods for complex undirected graphs. Acta Automatica Sinica, 2024, 50(6): 1143−1150 doi: 10.16383/j.aas.c230612
http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c230612
关键词
复杂无向图，邻接矩阵，距离矩阵，特征多项式，同构判定条件
摘要
针对一般复杂无向图的同构判定问题, 给出了基于邻接矩阵之和的特征多项式判定条件; 针对复杂无向连通图的同构判定问题, 给出了基于距离矩阵特征多项式和邻接矩阵特征多项式的同构判定条件, 将该条件用于复杂无向不连通图的各个连通子图, 就可解决复杂无向不连通图的同构判定问题. 上述两个判定条件均是充要条件且当复杂无向图退化为简单无向图时仍然适用.
文章导读
图的同构判定在有机化学、计算机科学和人工智能(机器学习或模式识别中常使用图的邻接矩阵特征值来判定两个对象是否为同一个对象)等领域有着重要的应用[1−3]. 上世纪前半叶, 与图同构相关的问题主要围绕图的邻接矩阵特征值及其应用展开[4], 取得若干重要的理论成果和一批应用成果; 其中一个重要的发现是, 两个互不同构的无向图却具有相同的邻接矩阵特征多项式, 即用邻接矩阵特征多项式判定两个无向图是否同构有时会得出错误的结果[4].
上世纪70年代, Karp和Johnson认为图的同构判定问题是少数几个既不能归类为 P 问题也不能归类为 NP 的问题[1, 3]. 此后, 该问题成为理论计算机领域的公开问题并受到广泛重视. 1982年, Luks给出一个当时最好的两图同构判定算法, 其时间复杂度是exp(O(
))[5−6] (n为图的顶点数). 此后40多年来, 几百篇这方面的文章得以在不同的学术期刊上发表[1]. 2015年, Babai[6]在Luks算法的基础上, 给出两图同构判定问题的拟多项式算法, 其时间复杂度是exp((logn)O(1)). Babai的工作虽然是一个重要进展, 但图的同构判定问题是否在多项式时间内可解仍然悬而未决[1, 3].
图的同构判定问题的另一研究路径是设计可执行的判定算法, 大致可以分为传统和非传统两类判定算法. 传统判定算法有两类: 1) 针对一些特殊图[7−8] (如树和极大外平面图)的同构判定算法(如Ullman算法和Schmidt算法等[9]). 2) 针对一般简单图的同构判定算法, 如一些放在因特网上用于测试两图是否同构的程序(如Nauty和Saucy等[3, 6]). 非传统判定算法也有两类: 1) 基于遗传算法和神经网络的智能判定算法. 这些算法将图的同构判定问题转化为一类优化求解问题, 但其判定结果并不完全可靠. 2) 基于DNA计算[9]和量子计算的判定算法. 这类算法虽然高效, 但不能回答图的同构判定是 P 问题还是 NP 问题. 无向连通图的距离矩阵是素矩阵(邻接矩阵一般不是素矩阵), 它具有邻接矩阵所没有的独特性质[10]. 文献[10]揭示了简单无向图同构与距离矩阵同构之间的一般关系, 将基于邻接矩阵的同构判定条件推广到距离矩阵, 给出几个适合一般简单无向图的同构判定条件. 这些条件均是充要条件且均具有多项式时间复杂度. 上述成果是近年来图同构研究方面的一个重要进展.
简单无向图的同构关系可由其距离矩阵的同构关系确定, 但复杂无向图却不能. 其根本原因在于: 复杂无向图中的自环和顶点间的重边对顶点间的距离没有影响[10]; 换言之, 自环数或重边数不同的复杂无向图可能具有完全相同的距离矩阵. 因文献[10]所给的判定条件不能用于复杂无向图, 故寻找和发现复杂无向图的同构判定条件既是必须的也是重要的. 本文的主要贡献是: 1) 针对一般复杂无向图的同构判定问题, 给出了基于邻接矩阵之和的特征多项式判定条件. 2) 针对复杂无向连通图的同构判定问题, 给出了基于距离矩阵特征多项式和邻接矩阵特征多项式的同构判定条件. 将该条件用于复杂无向不连通图的各个连通子图, 就可解决复杂无向不连通图的同构判定问题. 上述两个判定条件均是充要条件且均具有多项式时间复杂度. 此外, 当复杂无向图退化为简单无向图时, 上述两个判定条件仍然适用.
图 1 例1中的各对应图
图的同构关系是一种等价关系, 凡与图的结构相关的分类、聚类、识别和学习等问题均与图的同构判定问题有关. 时至今日, 图的同构判定问题仍然具有重要的理论和应用价值.
文献[10]将基于邻接矩阵的同构判定条件(引理2)推广到简单无向图距离矩阵(引理6和引理7), 解决了简单无向图的同构判定问题. 但引理6和引理7不能用于复杂无向图的同构判定, 原因在于复杂无向图的同构关系不能由其距离矩阵唯一确定.
本文的主要思路和贡献可概括为: 1) 证明了对角线元素为0或1而其他元素均为正整数的对称矩阵在非同构正交变换下不再是非负整数对称矩阵(定理1); 利用无向完全图邻接矩阵在矩阵同构变换下保持不变的特性, 给出了引理2的另一种等价表示(推论2); 基于定理1和推论2, 给出了基于邻接矩阵之和的特征多项式判定条件(定理2). 2) 针对复杂无向连通图的同构判定问题, 使用图及邻接矩阵的分解方法, 给出了基于邻接矩阵特征多项式和距离矩阵特征多项式的同构判定条件(定理3). 将该条件用于复杂无向不连通图的各个连通子图, 就可解决复杂无向不连通图的同构判定问题. 定理2和定理3中的判定条件均是充要条件且均具有多项式时间复杂度. 需要再次说明的是: 定理2所给的判定条件具有一般普适性, 即对任意的简单、复杂(每一顶点最多允许有一个自环)、连通和不连通无向图均适用; 定理3既适合复杂无向连通图也适合简单无向连通图.
与文献[10]中的结果相比, 定理2和定理3是无向图同构研究方面的又一重要进展. 定理2和定理3的另一理论价值表明, 无向图的同构判定问题是 P 问题. 需要说明的是, 虽然我们解决了无向图的同构判定问题, 但有向图的同构判定是 P 问题还是 NP 问题仍然没有得到解决.
今后我们将针对有向图的同构判定问题开展研究, 期望得到一些有理论和实用价值的新结果.
作者简介
王卓
北京航空航天大学仪器科学与光电工程学院教授. 2013年获得美国伊利诺伊大学芝加哥分校电子与计算机工程系博士学位. 主要研究方向为基于数据的系统分析与控制方法和网络理论. 本文通信作者.E-mail: zhuowang@buaa.edu.cn
王成红
中国自动化学会常务委员会研究员. 1997年获博士学位. 主要研究方向为运筹学与控制论, 图论及其应用.E-mail: chenghwang@163.com
转载本文请联系原作者获取授权，同时请注明本文来自欧彦科学网博客。
链接地址：https://wap.sciencenet.cn/blog-3291369-1444046.html?mobile=1
收藏
