2.845

2023影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

复杂无向图的同构判定方法

王卓 王成红

王卓, 王成红. 复杂无向图的同构判定方法. 自动化学报, 2024, 50(6): 1143−1150 doi: 10.16383/j.aas.c230612
引用本文: 王卓, 王成红. 复杂无向图的同构判定方法. 自动化学报, 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
Citation: 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

复杂无向图的同构判定方法

doi: 10.16383/j.aas.c230612
基金项目: 广东省重点领域研发计划(2021B0101410005), 国家自然科学基金(61673041)资助
详细信息
    作者简介:

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

    王成红:中国自动化学会常务委员会研究员. 1997年获博士学位. 主要研究方向为运筹学与控制论, 图论及其应用.E-mail: chenghwang@163.com

Isomorphism Determination Methods for Complex Undirected Graphs

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 Fellow researcher of the Council of Chinese Association of Automation. He received his Ph.D. degree in 1997. His research interest covers operational research and cybernetics, and graph theory and its applications

  • 摘要: 针对一般复杂无向图的同构判定问题, 给出了基于邻接矩阵之和的特征多项式判定条件; 针对复杂无向连通图的同构判定问题, 给出了基于距离矩阵特征多项式和邻接矩阵特征多项式的同构判定条件, 将该条件用于复杂无向不连通图的各个连通子图, 就可解决复杂无向不连通图的同构判定问题. 上述两个判定条件均是充要条件且当复杂无向图退化为简单无向图时仍然适用.
  • 图  1  例1中的各对应图

    Fig.  1  Corresponding figures of Example 1

  • [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: 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, Second Edition. New Jersey: Pearson Education, Inc., 2018.
    [5] 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
    [6] Babai L. Graph isomorphism in quasipolynomial time. Computer Science, arXiv preprint arXiv: 1512.03547v2, 2016.
    [7] Beyer T, Jones W, Nitche S. Linear algorithms for isomorphism of maximal outer planar graph. Journal of the Association for Computing Machinery, 1979, 26(4): 603−610 doi: 10.1145/322154.322155
    [8] Buss S R. A logtime algorithm for tree isomorphism, comparison and canonization. In: Proceedings of the 5th Kurt Code Colloquium on Computational Logic and Proof Theory. Vienna, Austria: 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] 王卓, 王成红. 简单无向图的同构判定方法. 自动化学报, 2023, 49(9): 1878−1888

    Wang Zhuo, Wang Cheng-Hong. Isomorphism determination methods for simple undirected graphs. Acta Automatica Sinica, 2023, 49(9): 1878−1888
    [11] 王朝瑞. 图论, 第2版. 北京: 北京理工大学出版社, 1997.

    Wang Chao-Rui. Graph Theory, Second Edition. Beijing: Beijing Institute of Technology Press, 1997.
    [12] 王树禾. 图论. 北京: 科学出版社, 2004.

    Wang Shu-He. Graph Theory. Beijing: Science Press, 2004.
    [13] 殷剑宏, 吴开亚. 图论及其算法. 合肥: 中国科学技术大学出版社, 2003.

    Yin Jian-Hong, Wu Kai-Ya. Graph Theory and Its Algorithms. Hefei: Press of University of Science and Technology of China, 2003.
    [14] 樊恽, 钱吉林, 岑嘉评, 刘恒, 穆汉林. 代数学辞典. 武汉: 华中师范大学出版社, 1994.

    Fan Yun, Qian Ji-Lin, Cen Jia-Ping, Liu Heng, Mu Han-Lin. Algebraic Dictionary. Wuhan: Central China Normal University Press, 1994.
    [15] 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
    [16] 刘春凤, 常锦才, 杨爱民, 龚佃选, 阎少宏. 数值计算方法. 北京: 高等教育出版社, 2016.

    Liu Chun-Feng, Chang Jin-Cai, Yang Ai-Min, Gong Dian-Xuan, Yan Shao-Hong. Numerical Methods. Beijing: Higher Education Press, 2016.
    [17] 王明辉, 王广彬, 张闻. 应用数值分析. 北京: 化学工业出版社, 2015.

    Wang Ming-Hui, Wang Guang-Bin, Zhang Wen. Applied Numerical Analysis. Beijing: Chemical Industry Press, 2015.
    [18] 王松桂, 吴密霞, 贾忠贞. 矩阵不等式, 第2版. 北京: 科学出版社, 2006.

    Wang Song-Gui, Wu Mi-Xia, Jia Zhong-Zhen. Matrix Inequalities, Second Edition. Beijing: Science Press, 2006
  • 加载中
图(1)
计量
  • 文章访问数:  228
  • HTML全文浏览量:  84
  • PDF下载量:  79
  • 被引次数: 0
出版历程
  • 收稿日期:  2023-10-03
  • 录用日期:  2024-03-15
  • 网络出版日期:  2024-05-29
  • 刊出日期:  2024-06-27

目录

    /

    返回文章
    返回