计算机科学 ›› 2018, Vol. 45 ›› Issue (8): 300-305.doi: 10.11896/j.issn.1002-137X.2018.08.054
江顺亮, 葛芸, 唐祎玲, 徐少平, 叶发茂
JIANG Shun-liang, GE Yun, TANG Yi-ling XU, Shao-ping, YE Fa-mao
摘要: 借鉴高阶矩的方法,采用层序的计算框架,依据结点的连接距离和层序信息定义了20种结点不变量。这些结点不变量体现图整体的上下偏分布特性、整体不均匀性和整体平滑性,结点不变量中的每层结点度数平方之和反映了层内结点度数的分布情况。通过比较这些结点不变量的可区分结点数,发现每层结点度数平方之和明显改善了结点不变量的细分能力。把排序后的结点不变量组成一个矢量后作为图的不变量。计算结果表明,共有9种图不变量可以区分所有结点数N<25的非同构树和N<34的非同构同胚不可约树(没有度数为2的树),对于更多结点的树,还没有发现非同构树有相同图不变量的例子;把这些图不变量应用到非同构图(N<10),区分结果好于文献[8]中列出的22种图不变量的19种,而且文中9种图不变量的简并度不大,提高了随机图的同构测试性能。
中图分类号:
[1]SAVAGE N.Graph matching in theory and practice[J].Communications of the ACM,2016,59(7):12-14. [2]BABAI L.Graph Isomorphism in Quasipolynomial Time[OL].http://arxiv.org/abs/1512.03547. [3]MCKAY B D,PIPERNO A.Practical graph isomorphism,II[J].Journal of Symbolic Computation,2014,60(1):94-112[4]HOU A M.Theory Research and Algorithm Design On Halmiltonian Cycle and Graph Isomorphism Problems[D].Guangzhou:South China University of Technology,2013.(in Chinese)侯爱民.哈密顿环与图同构问题的理论研究及算法设计[D].广州:华南理工大学,2013. [5]PIEC S M,MALARZ K,KULAKOWSKI K,et al.How tocount trees[J].International Journal of Modern Physics C,2005,16(10):1527-1534. [6]ZOU X X,DAI Q.A Vertex Refinement Method for Graph Isomorphism[J].Journal of Software,2007,18(2):213-219.(in Chinese)邹潇湘,戴琼.图同构中的一类顶点细分方法[J].软件学报,2007,18(2):213-219. [7]GAMKRELIDZE A,VARAMASHVILI L,HOTZ G.New Invariants for the Graph Isomorphism Problem[J].Journal of Mathematical Sciences,2016,218(6):754-762. [8]DEHMER M,GRABNER M,MOWSHOWITZ A,et al.An efficient heuristic approach to detecting graph isomorphism based on combinations of highly discriminating invariants[J].Advances in Computational Mathematics,2013,39(2):311-325. [9]BUSS S R.Alogtime algorithms for tree isomorphism,comparison,and canonization[M]∥Computational Logic and Preef Theory.Springer Berlin Heidelberg,1997:18-33. [10]ZHANG B,TANG Y,WU J,et al.LD:A Polynomial Time Algorithm for Tree Isomorphism[J].Procedia Engineering,2011,15(8):2015-2020. [11]ZHANG N.Research the Longest Path Length Based On the Degree Sequence of Non-isomorphic Undirected Tree[D].Huhehot:Inner Mongolia Normal University,2013.(in Chinese)张楠.基于度序列的非同构无向树的最长路径长度的研究[D].呼和浩特:内蒙古师范大学,2013. [12]SCHMUCK N S,WAGNER S G,HUA W.Greedy trees,caterpillars,and Wiener-type graph invariants[J].Match Communications in Mathematical and in Computer Chemistry,2012,68(68):273-292. [13]LOHREY M,MANETH S,PETERNEK F.Compressed Tree Canonization[C]∥International Colloquium on Automata,Languages,and Programming.Springer Berlin Heidelberg,2015:337-349. [14]BRINKMANN G,COOLSAET K,GOEDGEBEUR J.House of Graphs:A database of interesting graphs[J].Discrete Applied Mathematics,2013,161(1/2):311-314. [15]BABAI L,ERDOS P,SELKOW S M.Random Graph Isomor-phism[J].Siam Journal on Computing,1980,9(3):628-635. |
[1] | 项英倬, 魏强, 游凌, 石浩. 一种求解子图同构问题的改进遗传算法 Improved Genetic Algorithm for Subgraph Isomorphism Problem 计算机科学, 2019, 46(6A): 98-101. |
[2] | 项英倬, 谭菊仙, 韩杰思, 石浩. 图匹配技术研究 Survey of Graph Matching Algorithms 计算机科学, 2018, 45(6): 27-31. https://doi.org/10.11896/j.issn.1002-137X.2018.06.004 |
[3] | 李丽萍,赵传荣,孔德仁,王芳. 基于图论的无监督区域遥感图像检索算法研究 Research on Unsupervised Regional Remote Sensing Image Retrieval Algorithm Based on Graph Theory 计算机科学, 2017, 44(7): 315-317. https://doi.org/10.11896/j.issn.1002-137X.2017.07.057 |
[4] | 马元魁,白晓亮. 三角网格模型体素特征分割 Voxel Features Segmentation of Triangular Mesh Models 计算机科学, 2015, 42(10): 13-15. |
[5] | 郭鑫,董坚峰,周清平. 自适应云端的大规模导出子图提取算法 Large Scale Induced Subgraphs Mining Algorithm on Self Adaptive Cloud 计算机科学, 2014, 41(6): 155-160. https://doi.org/10.11896/j.issn.1002-137X.2014.06.030 |
[6] | 张春英,张雪. 不确定属性图的子图同构及其判定算法 Uncertain Attribute Graph Sub-graph Isomorphism and its Determination Algorithm 计算机科学, 2013, 40(6): 242-246. |
[7] | 梁正平,谭佳加,程一群,马骁驰. 大型模型克隆检测技术研究 Research on Clone Detection for Large-scale Model 计算机科学, 2012, 39(4): 28-31. |
[8] | . 关于图同构复杂性的分析 计算机科学, 2006, 33(11): 219-221. |
[9] | . 改进的基于分解的子图同构算法 计算机科学, 2006, 33(1): 260-263. |
[10] | . 频繁子图挖掘算法综述 计算机科学, 2005, 32(10): 193-196. |
|