引用本文

王卓, 王成红. 有向图同构判定方法. 自动化学报, 2025, 51(9): 2001−2010 doi: 10.16383/j.aas.c240789

Wang Zhuo, Wang Cheng-Hong. Isomorphism determination methods for directed graphs. Acta Automatica Sinica, 2025, 51(9): 2001−2010 doi: 10.16383/j.aas.c240789

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

关键词

有向图，顶点度集，距离谱，距离和集，同构性判据

摘要

基于有向图的邻接矩阵和距离矩阵, 提出有向图顶点度集、距离谱与距离和集的定义, 将基于邻接矩阵的同构判定条件推广到简单有向图的距离矩阵. 在此基础上, 给出两个简单有向图的同构性判据, 这两个判据均可判定任意两个简单有向图是否同构; 给出复杂有向图的同构性判据, 该判据可判定任意两个复杂有向图是否同构. 上述三个判据均是充要条件且均具有多项式时间复杂度.

文章导读

图的同构判定在有机化学、计算机科学和人工智能(机器学习中常需判定两个决策树是否同构)等领域有着重要的应用[1−3]. 20世纪前半叶, 与图同构相关的问题主要围绕无向图邻接矩阵的特征值及其应用展开[4], 取得若干重要的理论和应用成果. 20世纪70年代, Edmonds-Karp和Johnson等算法认为图的同构判定问题是少数几个既不能归类为P也不能归类为NP的问题[1, 3]. 此后, 该问题成为理论计算机领域的公开问题并受到广泛重视.

近年来, 几百篇图的同构判定方面的文章得以在不同的学术期刊上发表[1, 5−6]. 2015年, Babai在Luks算法[5]的基础上, 给出两图同构判定问题的拟多项式算法(时间复杂度是exp((logn)O(1))[6], n为图的顶点数). 上述成果多用于估计同构判定问题的复杂度上界, 并不能直接用于具体图的同构判定.

图的同构判定问题的另一研究路径是设计可执行的判定算法, 大致可以分为传统和非传统两类判定算法. 传统判定算法有两类: 1)针对一些特殊图(树和极大外平面图)[7−8]的同构判定算法(如Ullman算法和Schmidt算法等[9]); 2)针对一般简单图的同构判定算法, 如一些放在因特网上用于测试两图是否同构的程序(如Nauty算法和Saucy算法等[3, 6]). 这些程序运行速度非常快但算法的正确性证明没有公布, 故其判定结果的正确性不能保证[10]. 非传统判定算法也有两类: 1)基于遗传算法和神经网络的判定算法; 2)基于DNA计算[9]和量子计算的判定算法. 文献[10−11]是近年来传统判定算法方面的重要进展. 文献[10]将基于邻接矩阵的同构判定条件推广到简单无向图的距离矩阵, 给出几个适合一般简单无向图的同构性判据. 这些判据均是充要条件且均具有多项式时间复杂度. 简单无向图的同构关系可由其距离矩阵的同构关系确定, 但复杂无向图却不能. 针对任意复杂无向图的同构判定问题, 文献[11]给出基于邻接矩阵之和的特征多项式判据. 该判据是充要条件且具有多项式时间复杂度. 此外, 当复杂无向图退化为简单无向图时, 上述判据仍然适用. 文献[11]解决了无向图的同构判定问题, 且间接地证明了无向图的同构判定问题是P问题.

现实社会中的能源、交通和信息等网络化系统都可抽象为有向图. 有向图的同构判定研究比无向图的同构判定研究具有更大的理论和应用价值. 有向图远比无向图复杂且鲜有成果报道, 故有向图的同构判定研究也更具挑战性. 本文系统研究有向图的同构判定问题: 给出两个简单有向图的同构性判据, 这两个判据均可在多项式时间内判定任意两个简单有向图是否同构; 给出复杂有向图的同构性判据, 该判据可在多项式时间内判定任意两个复杂有向图是否同构.

凡与图结构相关的分类、聚类、识别和学习等问题都与图的同构判定有关. 现实社会中的能源、交通以及信息等网络都可抽象为有向图. 此外, 近年来兴起的时序网络 (如供应链和区块链等)[18]亦可抽象为有向图; 将有向图的同构判定方法与其他网络参数估计方法相结合, 可以更好地描述和评估时序网络的动态演化特性, 并可为相关调控与决策提供依据. 不言而喻, 有向图的同构判定研究相比无向图的同构判定研究, 不仅具有更大的理论和应用价值, 而且具有更大的挑战性.

本文的主要思路和贡献可概括为如下几个方面: 1) 借鉴文献[10]的研究思路, 将基于邻接矩阵的同构判定条件推广至简单有向图距离矩阵(定理3), 阐明简单有向图邻接矩阵同构与距离矩阵同构的等价性. 2) 给出有向图的顶点度集、距离谱与距离和集等定义, 并据此给出两个有向图同构的三个必要条件(定理1、定理2和定理4). 这些条件和相关结论表明, 有向图的基础图、顶点度集与距离谱是有向图的主要结构特征, 且这些特征关于矩阵同构变换具有不变性. 3) 在1)和2)的基础上, 给出两个简单有向图的同构性判据(定理5和定理6). 这两个判据均可在多项式时间内判定任意两个简单有向图是否同构. 4) 在1) ~ 3)的基础上, 给出复杂有向图的同构性判据(定理7). 该判据同样可在多项式时间内判定任意两个复杂有向图是否同构. 此外, 本文间接地证明了有向图的同构判定问题是P问题.

今后, 我们希望将无向图的同构性判据(文献[10−11]中的结果)和有向图的同构性判据(本文结果)开发成高效计算软件, 为相关理论研究和实际应用提供工具支撑.

作者简介

王卓

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

王成红

中国自动化学会理事会研究员. 1997年获得博士学位. 主要研究方向为运筹学与控制论, 图论及其应用.E-mail: wangch@mail.nsfc.gov.cn