简单无向图的同构判定方法

王卓; 王成红

doi:10.16383/j.aas.c230025

简单无向图的同构判定方法

doi: 10.16383/j.aas.c230025

王卓^1,,
王成红^2,

1.
北京航空航天大学仪器科学与光电工程学院北京 100191
2.
国家自然科学基金委员会北京 100083

基金项目: 广东省重点领域研发计划(2021B0101410005), 国家自然科学基金(61673041)资助

详细信息

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

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

计量
- 文章访问数: 958
- HTML全文浏览量: 132
- PDF下载量: 193
- 被引次数: 0
出版历程
- 收稿日期: 2023-01-18
- 录用日期: 2023-07-22
- 网络出版日期: 2023-08-17
- 刊出日期: 2023-09-26

Isomorphism Determination Methods for Simple Undirected Graphs

WANG Zhuo^1
,,
WANG Cheng-Hong^2
,

1.
School of Instrumentation and Optoelectronic Engineering, Beihang University, Beijing 100191
2.
National Natural Science Foundation of China, Beijing 100083

Funds: Supported by Key Area Research and Development Program of Guangdong Province (2021B0101410005) and National Natural Science Foundation of China (61673041)

More Information

Author Bio:
WANG Zhuo　Professor at the School of Instrumentation and Optoelectronic Engineering, Beihang University. He received his Ph.D. degree in Electrical and Computer Engineering Department, University of Illinois at Chicago, USA in 2013. His research interest covers data-based system analysis and control methods, and network theory. Corresponding author of this paper

WANG Cheng-Hong　Research Fellow of National Natural Science Foundation of China. He received his Ph.D. degree in 1997. His research interest covers operational research and cybernetics, and graph theory and its applications

摘要

摘要: 给出了矩阵同构变换、简单无向图距离矩阵、距离矩阵列和向量以及图的距离谱的定义, 将基于邻接矩阵的同构判定条件推广到简单无向图距离矩阵. 针对简单无向连通图的同构判定问题: 给出了基于距离矩阵特征多项式的同构判定条件; 进一步, 为避免计算误差对判定结果的影响, 给出了基于距离矩阵的秩与列和向量的同构判定条件. 上述两个判定条件均是充要条件且均具有多项式时间复杂度.
- 简单无向图 /
- 同构判定条件 /
- 距离矩阵列和向量 /
- 图的距离谱 /
- 特征多项式
Abstract: This work gives the definitions of matrix isomorphic transformation, distance matrix of the simple undirected graph, column sum vector of the distance matrix, and distance spectrum of the graph, which extend the adjacency matrix-based isomorphism determination conditions to the distance matrix-based ones for simple undirected graphs. For the isomorphism determination problem of simple undirected connected graphs: One determination condition based on the characteristic polynomial of distance matrix is proposed; Further, another determination condition based on the rank and the column sum vector of distance matrix is proposed to avoid the influence of calculation error on the determination result. These two determination conditions are both necessary and sufficient conditions and both have polynomial time complexity.
- Simple undirected graphs /
- isomorphism determination conditions /
- column sum vector of distance matrix /
- distance spectrum of graph /
- characteristic polynomial

HTML全文

图 1 例1各对应图

Fig. 1 Corresponding figures of Example 1

下载: 全尺寸图片幻灯片

参考文献(20)

[1]	. Grohe M, Schweitzer P. The graph isomorphism problem. Communications of the ACM, 2020, 63(11): 128-134 doi: 10.1145/3372123
[2]	. McKay B D, Piperno A. Practical graph isomorphism, Ⅱ. Journal of Symbolic Computation, 2014, 60(0): 94-112
[3]	Rosen K H [著], 徐六通, 杨娟, 吴斌 [译]. 离散数学及其应用. 北京: 机械工业出版社, 2016. Rosen K H [Author], Xu Liu-Tong, Yang Juan, Wu Bin [Translator]. Discrete Mathematics and Its Applications. Beijing: China Machine Press, 2016.
[4]	West D B. Introduction to Graph Theory, 2nd Edition. Pearson Education, Inc., 2018.
[5]	Babai L. Graph isomorphism in quasipolynomial time. arXiv preprint arXiv: 1512.03547v2 [cs. Ds], 2016.
[6]	. Luks E M. Isomorphism of graphs of bounded valance can be tested in polynomial time. Journal of Computer and System Sciences, 1982, 25(1): 42-65 doi: 10.1016/0022-0000(82)90009-5
[7]	. Beyer T, Jones W, Mitchell S. Linear algorithms for isomorphism of maximal outerplanar graphs. Journal of the ACM, 1979, 26(4): 603-610 doi: 10.1145/322154.322155
[8]	Buss S R. Alogtime algorithms for tree isomorphism, comparison, and canonization. In: Proceedings of the 5th Kurt Cödel Colloquium on Computational Logic and Proof Theory. Berlin, Germany: Springer-Verlag, 1997. 18−33
[9]	. Liu G W, Yin Z X, Xu J, Dong Y F. Algorithm of graph isomorphism with three dimensional DNA graph structures. Progress in Natural Science, 2005, 15(2): 181-184 doi: 10.1080/10020070512331341960
[10]	刘春凤, 常锦才, 杨爱民, 龚佃选, 阎少宏. 数值计算方法. 北京: 高等教育出版社, 2016. Liu Chun-Feng, Chang Jin-Cai, Yang Ai-Min, Gong Dian-Xuan, Yan Shao-Hong. Numerical Methods. Beijing: Higher Education Press, 2016.
[11]	王明辉, 王广彬, 张闻. 应用数值分析. 北京: 化学工业出版社, 2015. Wang Ming-Hui, Wang Guang-Bin, Zhang Wen. Applied Numerical Analysis. Beijing: Chemical Industry Press, 2015.
[12]	王朝瑞. 图论, 第2版. 北京: 北京理工大学出版社, 1997. Wang Chao-Rui. Graph Theory, 2nd Edition. Beijing: Beijing Institute of Technology Press, 1997.
[13]	王树禾. 图论. 北京: 科学出版社, 2004. Wang Shu-He. Graph Theory. Beijing: Science Press, 2004.
[14]	殷剑宏, 吴开亚. 图论及其算法. 合肥: 中国科学技术大学出版社, 2003. Yin Jian-Hong, Wu Kai-Ya. Graph Theory and Its Algorithms. Hefei: Press of University of Science and Technology of China, 2003.
[15]	樊恽, 钱吉林, 岑嘉评, 刘恒, 穆汉林. 代数学辞典. 武汉: 华中师范大学出版社, 1994. Fan Yun, Qian Ji-Lin, Cen Jia-Ping, Liu Heng, Mu Han-Lin. Algebraic Dictionary. Wuhan: Central China Normal University Press, 1994.
[16]	. Mowshowitz A. The characteristic polynomial of a graph. Journal of Combinatorial Theory, Series B, 1972, 12(2): 177-193 doi: 10.1016/0095-8956(72)90023-8
[17]	陈景良, 陈向晖. 特殊矩阵. 北京: 清华大学出版社, 2001. Chen Jing-Liang, Chen Xiang-Hui. Special Matrices. Beijing: Tsinghua University Press, 2001.
[18]	王松桂, 贾忠贞. 矩阵论中的不等式. 合肥: 安徽教育出版社, 1994. Wang Song-Gui, Jia Zhong-Zhen. Inequalities in Matrix Theory. Hefei: Anhui Education Publishing House, 1994.
[19]	吴廷增. 同谱图的构造. 山东大学学报(理学版), 2011, 46(6): 60-63 . Wu Ting-Zeng. Construction of cospectral graphs. Journal of Shandong University (Natural Science), 2011, 46(6): 60-63
[20]	Diestel R [著], 于青林 [译]. 图论, 第5版. 北京: 科学出版社, 2020. Diestel R [Author], Yu Qing-Lin [Translator]. Graph Theory, 5th Edition. Beijing: Science Press, 2020.