改进电路模拟法的应用——同构混合开关拓扑辨识

doi:10.3969/j.issn.0255-8297.2014.02.013

应用科学学报 ›› 2014, Vol. 32 ›› Issue (2): 199-208.doi: 10.3969/j.issn.0255-8297.2014.02.013

改进电路模拟法的应用——同构混合开关拓扑辨识

商慧亮1，刘洋1，柳志栋1，董文杰2，李锋1

1. 复旦大学电子工程系，上海200433
2. 东方电子有限公司，山东烟台264000

收稿日期:2011-11-17 修回日期:2012-10-14 出版日期:2014-03-25 发布日期:2012-10-14
作者简介:商慧亮，讲师，博士，研究方向：电路理论、故障诊断、网络图论、混沌理论、数字滤波器理论等，E-mail: shanghl@fudan.edu.cn；李锋，教授，博导，研究方向：电路理论、故障诊断、网络图论、混沌理论、数字滤波器理论等，E-mail:lifeng.fudan@gmail.com
基金资助:
国家自然科学基金(No.61301028) ; 上海市自然科学基金(No.13ZR1402900)；教育部博士点基金(No.20120071120016)资助

Application of Optimized Circuit Simulation—Identification of Isomorphic Hybrid Switching

1. Department of Electronic Engineering, Fudan University, Shanghai 200433, China
2. East Electron Limited Company, Yantai 264000, Shandong Province, China

Received:2011-11-17 Revised:2012-10-14 Online:2014-03-25 Published:2012-10-14

摘要/Abstract

摘要： 提出了一种基于已有图同构判定算法——电路模拟法的改进方法，并将其应用到同构混合开关拓扑的辨识中. 首先介绍混合开关拓扑的数学描述方法，给出混合开关拓扑的邻接矩阵表示及其相应的含权无向图表示，由此将同构混合开关拓扑的辨识问题转换为与其对应的含权无向图的同构判定问题，继而采用所提出的改进电路模拟法加以判定. 在同样环境下对改进的电路模拟法及另一种混合开关拓扑同构判定方法——特征值判定法进行测试比对，测试结果表明该方法在处理同构混合开关拓扑辨识问题上是有效的，并且在判定速度和节点匹配能力上有较大的优势.

关键词: 开关拓扑, 同构, 电路模拟法, 特征值法

Abstract: 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.

Key words: switching topology, isomorphism, circuit simulation method, eigenvalue algorithm

中图分类号:

TN711.6
TM13

商慧亮1，刘洋1，柳志栋1，董文杰2，李锋1. 改进电路模拟法的应用——同构混合开关拓扑辨识[J]. 应用科学学报, 2014, 32(2): 199-208.

SHANG Hui-liang1, LIU Yang1, LIU Zhi-dong1, DONG Wen-jie2, LI Feng1. Application of Optimized Circuit Simulation—Identification of Isomorphic Hybrid Switching[J]. Journal of Applied Sciences, 2014, 32(2): 199-208.

参考文献

[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

改进电路模拟法的应用——同构混合开关拓扑辨识

Application of Optimized Circuit Simulation—Identification of Isomorphic Hybrid Switching

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价