提出了一种基于已有图同构判定算法——电路模拟法的改进方法，并将其应用到同构混合开关拓扑的辨识中. 首先介绍混合开关拓扑的数学描述方法，给出混合开关拓扑的邻接矩阵表示及其相应的含权无向图表示，由此将同构混合开关拓扑的辨识问题转换为与其对应的含权无向图的同构判定问题，继而采用所提出的改进电路模拟法加以判定. 在同样环境下对改进的电路模拟法及另一种混合开关拓扑同构判定方法——特征值判定法进行测试比对，测试结果表明该方法在处理同构混合开关拓扑辨识问题上是有效的，并且在判定速度和节点匹配能力上有较大的优势.
This paper presents a new method for graph isomorphism identification and applies it to the identification of isomorphic hybrid switching topology. A mathematical model of hybrid switching topology is first introduced. The adjacency matrix and undirected-weighted graph description of the hybrid switching
topology are presented according to the mathematical model. In this case, the problem of identifying isomorphic hybrid switching topology is transformed into isomorphism determination of the corresponding undirectedweighted graphs. An optimized version of the circuit simulation method previously presented by the authors is proposed to solve the graph isomorphism determination problem. With a small modification, the optimized circuit simulation method can solve the problem of graph isomorphism determination more efficiently. Tests of the proposed method and another method called the eigenvalue algorithm are applied in the identification of isomorphic hybrid switching topology. The results show that the optimized circuit simulation method is valid and has advantages in both identification efficiency and ability of matching corresponding vertices of the isomorphic hybrid switching topology.
[1] 石勇，杨旭，何群，王兆安. 同构混合开关拓扑的辨识[J]. 中国电机工程学报，2003, 23(11): 116-121.
SHI Y, YANG X, HE Q, WANG Z. Identification of hybrid switching topology[J]. Proceedings of the Chinese society for electrical engineering, 2003, 23(11): 116-121. (in Chinese)
[2] 丁华锋，黄真. 平面机构统一拓扑描述模型的建立及同构判别[J]. 机械工程学报，2009, 45(3): 99-103.
DING H, HUANG Z. Uniform topological representation model of planar mechanisms and isomorphism identification[J]. Journal of Mechanical Engineering, 2009, 45(3): 99-103.
(in Chinese)
[3] 丁玲，路懿. 运动链拓扑图的特征数组表示及同构判断[J]. 机械工程学报，2010, 46(7): 63-67.
DING L, LU Y. Character arrays representation and isomorphism identification of kinematic chain topology graphs[J]. Journal of Mechanical Engineering, 2010, 46(7): 63-67. (in Chinese)
[4] GOLOVIN A, HENRICK K. Chemical Substructure Search in SQL[J]. Journal of chemical information and modeling, 2009, 49(1): 22-27.
[5] CHEN K, GUO C, WU H, YUAN J, FENG Z, CHEN Y, LU S, WU W. Generic and automatic address configuration for data center networks [C]// Proceedings of the ACM SIGCOMM 2010 Conference. New Delhi, India, 2010: 39-50.
[6] SHANG H, LI F, TANG X, WOO P Y. A New Algorithm for isomorphism determination of undirected graphs-circuit simulation method[J]. Circuits, Systems, and Signal Processing, 2011, 30(5): 1115-1130.
[7] LI F, SHANG H, WOO P Y. Determination of isomorphism and its applications for arbitrary graphs based on circuit simulation[J]. Circuits, Systems, and Signal Processing, 2008, 27(5): 749-761.
[8] SHANG H, LI J, CAI Q, DONG W. An optimized algorithm for the identification of isomorphic undirected graphs [C]// Proceedings of 2011 International Conference on Modelling, Identification and Control, ICMIC 2011, Shanghai, 2011: 351-356.
[9] 李锋，李晓艳. 图的同构判定算法：关联度序列法及其应用[J]. 复旦学报：自然科学版，2001, 40(3): 318-325.
LI F, LI X. Isomorphism testing algorithm for graphs: incidence degree sequence method and applications [J]. Journal of Fudan University: Science Edition, 2001, 40(3)：318-325. (in Chinese)
[10] 李锋，商慧亮. 有向图的同构判定算法:出入度序列法[J]. 应用科学学报，2002, 20(3): 258-262.
LI F, SHANG H. An isomorphism testing algorithm for directed graphs: the in-degree and out-degree sequence method[J]. Journal of Applied Science, 2002, 20(3): 258-262. (in Chinese)
[11] 南晋华，齐欢. 图同构问题的决策神经网络模型[J]. 计算机学报，2010, 33(2): 300-304.
NAN J, QI H. The decision-making neural networks model for solving the graph isomorphism problem[J]. Chinese Journal of Computers, 2010, 33(2): 300-304. (in Chinese)
[12] PORUMBEL D C. Isomorphism testing via polynomial-time graph extensions[J]. Journal of Mathematical Modeling and Algorithms, 2010, 10(2): 119-143.
[13] ZAHIDI U A. Spectral solution for detecting isomorphic graphs with nondegenerate eigenvalues[C]// 11th IEEE International Multitopic Conference, INMIC2007. Lahore, Pakistan, 2007: 1-4.
[14] QIU M, HU H, JIANG Q, HU H. A new approach of graph isomorphism detection based on decision tree[C]//2nd International Workshop on Education Technology and Computer Science, ETCS 2010, Wuhan, Hubei, 2010: 32-35.
[15] ZHANG B, TANG Y, WU J, HUANG L. A unique vertex deleting algorithm for graph isomorphism [C]//2011 International Symposium on Image and Data Fusion, 2011, Tengchong, Yunnan, 2011: 1-4.
[16] 徐俊明. 图论及其应用 [M]. 安徽：中国科学技术大学出版社，1998:16.
[17] A. Meister. Numerik linearer Gleichungssysteme[M]. 2nd ed. Germany: View
