引用本文

王卓, 王成红. 简单无向图的同构判定方法. 自动化学报, 2023, 49(9): 1878−1888 doi: 10.16383/j.aas.c230025

Wang Zhuo, Wang Cheng-Hong. Isomorphism determination methods for simple undirected graphs. Acta Automatica Sinica, 2023, 49(9): 1878−1888 doi: 10.16383/j.aas.c230025

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c230025

关键词

简单无向图，同构判定条件，距离矩阵列和向量，图的距离谱，特征多项式 

摘要

给出了矩阵同构变换、简单无向图距离矩阵、距离矩阵列和向量以及图的距离谱的定义, 将基于邻接矩阵的同构判定条件推广到简单无向图距离矩阵. 针对简单无向连通图的同构判定问题: 给出了基于距离矩阵特征多项式的同构判定条件; 进一步, 为避免计算误差对判定结果的影响, 给出了基于距离矩阵的秩与列和向量的同构判定条件. 上述两个判定条件均是充要条件且均具有多项式时间复杂度.

文章导读

图的同构判定在化学分析、计算机科学、人工智能以及智能决策与控制等领域有着广泛的应用[1-3]. 上世纪前半叶, 与图同构相关的问题主要围绕图的邻接矩阵及其性质、邻接矩阵(拉普拉斯矩阵)特征值及其应用展开[4], 取得了若干重要的理论成果和一大批应用成果.

上世纪70年代, Karp、Garey和Johnson等认为图的同构判定问题是少数几个既不能归类为$ P $, 也不能归类为$ NP $的问题[1, 3]. 自此之后, 该问题成为理论计算机领域的公开问题并受到广泛重视.

1982年, Luks使用有限群等数学工具给出了一个当时最好的两图同构判定算法, 该算法的时间复杂度是$\exp ( {\text{O}}({\sqrt {n\log n} } ) )$ ($ n $为图的顶点数)[5-6]. 此后40年来, 图的同构判定问题引起了众多学者的关注, 几百篇这方面的文章得以在不同的学术期刊上发表[1]. 2015年, Babai在Luks算法的基础上, 利用群作用下轨道间的局部关系和群的正则分解技术, 给出了两图同构判定问题的拟多项式算法, 该算法的时间复杂度是$\exp({{{( {\log n} )}}}^{\rm{O(1)}} )$[5]. 上述算法的目的在于给出同构判定问题的复杂度上界, 并不能直接用于具体图的同构判定[5]. Babai的工作虽然是一个重要进展, 但图的同构判定问题是否在多项式时间内可解仍然悬而未决[1].

图的同构判定问题的另一研究路径是设计可执行的具体判定算法, 大致可以分为传统判定算法和非传统判定算法两种情况. 传统判定算法有两类: 1) 针对一些特殊图(如树和极大外平面图等)[7-8]的同构判定算法(如Ullman算法、Schmidt算法、Falkenhainer算法和Messmer算法等)[9]. 这些算法主要使用“搜索、标号和回溯”技术且被证明具有多项式时间复杂度; 2) 针对一般简单图的判定算法, 如一些放在因特网上用于测试两图是否同构的程序(如Nauty、Saucy、Bliss、Conauto和Traces等)[3, 5]. 这些程序运行速度很快, 但算法的时间复杂度分析和正确性证明却没有公开报道. 非传统判定算法也有两类: 1) 基于遗传算法、神经网络和粒子群算法等的智能同构判定算法. 这些算法将图的同构判定问题转化为一类优化求解问题, 但其判定结果并不完全可靠. 2) 基于生物(DNA)计算[9]和量子计算的判定算法. 这类算法虽然高效, 但实现比较困难而且也不能回答图的同构判定是P还是NP问题.

本文的主要思路和贡献是: 1) 给出了矩阵同构变换和简单无向图距离矩阵的定义, 将基于邻接矩阵的同构判定条件推广到简单无向图距离矩阵. 2) 针对简单无向连通图的同构判定问题, 给出了基于距离矩阵特征多项式的同构判定条件. 因用数值方法求解特征多项式会产生计算误差, 故该判定条件仅适合中小规模简单无向连通图的同构判定[10-11]. 3) 为避免计算误差对判定结果的影响, 给出了简单无向连通图距离矩阵列和向量与图的距离谱的定义, 并进而给出了基于距离矩阵的秩与列和向量的同构判定条件. 该判定条件不产生计算误差, 因而适合大规模简单无向连通图的同构判定. 上述两个判定条件均是充要条件且均具有多项式时间复杂度, 将这些条件用于简单无向不连通图的各个连通子图, 就可解决简单无向不连通图的同构判定问题.

图 1  例1各对应图

图的同构关系是一种等价关系. 图论在自然科学和社会科学的诸多领域中有着广泛的应用, 凡与图的结构相关的分类、聚类、识别与学习等问题均与图的同构判定问题有关. 时至今日, 图的同构判定问题仍然具有重要的理论和应用价值.

本文给出了简单无向图距离矩阵的定义, 将基于邻接矩阵的同构判定条件推广到简单无向图距离矩阵. 由简单无向连通图的距离矩阵很容易求得该图的直径(求图的直径是图论中的难题[13])、半径和离心率等[4], 而这些整体性结构参数不可能由邻接矩阵得到. 此外, 距离矩阵是素矩阵而邻接矩阵一般不是素矩阵. 正是利用了这些邻接矩阵所没有的整体结构性质, 本文给出了基于距离矩阵特征多项式的同构判定条件(定理3). 距离矩阵特征多项式不同于邻接矩阵特征多项式, 邻接矩阵特征多项式相等仅是两个简单无向连通图同构的必要条件. 就无向树而言, 随着顶点数趋于无穷大, 几乎没有树可被它的邻接矩阵特征值唯一确定[4]. 为避免特征多项式计算误差对判定结果的影响, 本文率先给出了简单无向连通图距离矩阵列和向量与图的距离谱的定义, 并进一步给出了基于距离矩阵的秩与列和向量的同构判定条件(定理5). 该条件易于验证且不产生计算误差, 故更适合大规模简单无向连通图的同构判定. 定理3和定理5均是充要条件且均具有多项式时间复杂度. 针对无向树的同构判定问题, 本文还给出了基于距离谱的判定条件(推论4). 容易理解, 将定理3特别是定理5用于简单无向不连通图的各个连通子图或将推论4用于无向森林的各个无向树, 就可解决任意简单无向不连通图的同构判定问题. 最后, 本文用一些典型例图说明了定理3、定理5、推论4及其他相关结论的使用方法, 其中部分例图(如Wagner图和Petersen图)曾被多位学者深入研究或引用过.

本文的主要创新点和贡献可概括为: 1)给出了简单无向图的同构判定条件, 这些条件均具有多项式时间复杂度, 间接地证明了简单无向图的同构判定问题是$ P $问题; 2) 不同于现有的图上操作算法(搜索−标号−回溯算法), 本文所给的同构判定条件均是数学方程式, 不仅便于分析和应用而且便于计算机编程; 3) 因简单无向图是一大类常见的图且无向树和极大无向外平面图均是简单无向图的真子集, 故本文的主要结果是现有工作的一个重要进展. 需要说明的是, 虽然本文在简单无向图的同构判定问题上有较大进展, 但一般(任意)无向或有向图的同构判定是$ P $还是$ NP $问题仍然没有得到解决.

今后, 我们将针对简单有向强连通图的同构判定问题开展研究, 期望得到一些有理论和实用价值的新结果.

作者简介

王卓

北京航空航天大学仪器科学与光电工程学院教授. 2013年获得美国伊利诺伊大学芝加哥分校电子与计算机工程系博士学位. 主要研究方向为基于数据的系统分析与控制方法, 网络理论. 本文通信作者.E-mail: zhuowang@buaa.edu.cn

王成红

国家自然科学基金委员会研究员. 1997年获博士学位. 主要研究方向为运筹学与控制论, 图论及其应用. E-mail: chenghwang@163.com