基于层序遍历的顶点不变量及其图不变量  

Vertex Invariants Based on Level-Order Traversal and Their Graph Invariants

作　　者：江顺亮[1] 唐祎玲[1] 葛芸[1] 徐少平[1] 叶发茂[1] JIANG Shunliang;TANG Yiling;GE Yun;XU Shaoping;YE Famao(Information Engineering School,Nanchang University,Nanchang Jiangxi 330031,China)

机构地区：[1]南昌大学信息工程学院,江西南昌330031

出　　处：《图学学报》2018年第3期424-431,共8页Journal of Graphics

基　　金：国家自然科学基金项目(61662044)

摘　　要：为了寻找更好性能的图不变量,利用层序遍历过程中的顶点数据经加权累加定义了15种顶点不变量,每一种顶点不变量排序后可以组成一种图不变量。层序遍历时将顶点度数分为同层度数、向前度数和向后度数,其中同层度数和向后度数包含回路数信息。依据对顶点的细分能力,挑选出3种顶点不变量,组成图不变量,其不同组合对于各种非同构连通图具有较好的区分性能,不仅对图顶点数N≤8的非同构图全部可以区分,而且将N=9的不可区分图数量从文献[9]的989种降到40种,且其简并度将趋近2,随机测试表明这些图不变量具有很好的区分度。In order to find graph invariants with higher performance,fifteen kinds of vertex invariants are defined by weighted accumulation with the help of vertex data in the process of level-order traversal.Every kind of vertex invariants are able to compose a graph invariant after being sorted.The vertex degree is divided into the internal degree,the forward degree,and the backward degree during the traversal,while the internal degree and the backward degree include the number of loops.Three kinds of vertex invariants are selected based on the refining performance,and then the graph invariants are generated.The combination of three kinds of graph invariants performs well in distinguishing a variety of non-isomorphic connected graphs.Not only all the non-isomorphic graphs with the number of vertexes N≤8 are distinguishable,but also the number of undistinguishable graphs with N=9 is reduced from 989 of literature[9]down to 40,with the degeneracies of these graph invariants approaching 2.Random tests shows that these graph invariants have good performances in differentiation.

关 键 词：图同构 顶点不变量 图不变量 不可区分图 简并度 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]