基于图论的潜通路分块分析方法

梁 因 马齐爽 徐 萍

(北京航空航天大学 自动化科学与电气工程学院，北京100191)

潜通路分析［1］揭示的是电路中非器件失效而由于潜通路的存在所引起的系统功能异常.近几年来，国内外对于潜通路及潜通路分析的理论研究已经基本趋于成熟，现有的潜通路分析方法已经能够解决大量电气系统网络的潜通路分析问题.提高潜通路分析的智能化、自动化是目前研究的一个趋势［2－3］.

潜通路问题的产生是系统复杂性和设计人员有限的把握能力之间矛盾斗争的结果［4］，进行潜通路分析时同样面临着电路系统过于复杂，而难以直观把握这个问题.尤其是要将其与计算机技术相结合实现智能化、自动化的潜通路分析时，电路信息存储在邻接矩阵中，随着电路系统规模的扩大，整体进行分析不仅会使分析时间增加，而且分析过程需要占据很大的存储空间.因此本文提出了对大型复杂电路系统分块分析的方法，将大型复杂电气系统网络进行分块处理，对每一个子网络模块分别进行分析，再将每一个子网络模块等效成简单的模型对整体电路进行分析，从而简化分析过程的模型，提高潜通路分析自动化水平.

1 电路系统自动分块算法

1.1 电路网络分块理论

用电路的邻接矩阵模型［5］对电路网络进行分块处理，设电路系统图G为一个具有n个节点的无向连通图.对大型电气网络分块等价于找到其模型的邻接矩阵的点割集，使电路能够分成两个子网络模块.采用点切割的方法进行分块，可视为将分块点分成了两个相同节点，中间用导线连接，划分模块时将导线切割，可以保证电路中所有元件都将位于模块中，便于子网络模块的等效.

例如对电路网络分块处理如图1所示.

图1 电气网络分块示意图

由图1可知，子网络模块中的节点包括两部分.

1)各个子网络独立占有的内部结点集:

2)分块点集:Q=［7］，该图为单分块点.

分块后的各子网络之间除了分块点是联系两个模块的部分外，其他电路子网络模块独自占有的节点间不存在直接的联系.如果在电路系统模型的邻接矩阵中去掉这些分块点，再进行合理的排序，分块对角阵的形式如下:

1.2 电路网络分块算法

电路系统分块的算法采用类似于复杂网络中社区发现的基于Laplace矩阵的谱平分法［6］.当把社区结构看成是网络的一个划分时，社区发现在于寻找网络固有的自然划分，而不是按指定条件进行划分.同样，在潜通路分块分析中，对于电路系统网络模型的分块是希望能够根据电路的拓扑结构形成自然划分.

在对电路系统分块前要先去掉电源点、地点以及它们与其他元件的连接关系，这样电路网络中的割点就会更加容易被辨别出来，而且并不影响对电路网络拓扑的分析.

图G为 n阶无向简单连通图［7］，其 Laplace矩阵的 n 个特征值为 λ1，λ2，…，λn，x1，x2，…，xn分别为对应特征向量，若λ1≥λ2≥…≥λn，则有 λi＞ 0，i=1，2，…，n－1，λn=0，且xn=［1，1，1，…，1］为特征值 λn=0对应的特征向量.对称矩阵的任意两个特征值所对应的特征向量都相互正交，所以 xi⊥xn，i=1，2，…，n －1.则 ∀i≤n－1，都应该∃j∈(1，n－1)使 xi=［y1，y2…，yj，yj+1，…，yn］，其中，∀k≤j，yk＜ 0 ，且 ∀k ＞ j，yk＞0.存在特征值λi→0，使其对应特征向量xi中的元素yj→0，且其对应的节点将电路网络图分成两部分，该特征向量中正数元素即yk＞0对应的节点属于一个子图，另外的负数元素即yk＜0对应的节点属于另一个子图［8］.

根据次小特征值λn－1对应的特征向量xn－1=［y1，y2，…，yn］中元素的绝对值大小来选择分块点，步骤如下:

1)对xn－1中元素按绝对值大小重新排序得x′n－1，对邻接矩阵按相应顺序重新排序得 C′n，对应的电路网络节点位置向量为U.

2)若|yk|=minx′n－1=min［|y1|，|y2|，…，|yn|］，则先选yk对应的节点uk为分块点，判断在邻接矩阵C′n中去掉uk对应的行和列是否出现分块对角阵.若出现，则该点就是电路系统的单分块点，给出分块情况即可.

3)若不出现分块对角阵的形式，则增加一个x′n－1中绝对值次小的元素对应的结点做分块点，再进行判断，直到出现分块对角阵把电路网络分成两个子网络模块为止.

该算法每次将电路网络分成两块，如果电路规模过大，可以分别对子网络进一步分块，直到得到满意的规模为止.

2 分块后的子网络模块等效

电路网络分块的结果为各个子网络模块所包含的点的编号以及其邻接矩阵.运用现有的潜通路分析方法和工具，对各子网络模块分别进行潜通路分析.再将子网络模块等效成一些更简单的模型，完成对整个电路网络的潜通路分析.

2.1 子网络模块等效模型的类型

子网络模块等效就是将每个子网络模块当作一个特殊器件来处理.根据对电路元件等效的方法对子网络进行等效.由电路系统网络模型的建立方法［2］可知，电路网络结点包括电路节点和电路元件，电路元件又包括受控类元件、可变状态元件和固定状态元件.由于子网络模块可能包含各类基本电气元件，将其分为3种情况.

用组成器件的结点和结点间的连接关系矩阵表示该特殊器件.在子网络模块的等效过程中直接用一个结点描述其电气特性，而关键分析子网络模块对外的连接端点与其连接关系.如3端网络的结点等效模型为图2所示.

图2 3端网络结点等效模型

多端子网络模块等效时其模型取决于端点间的组合情况，n端网络等效模型共有种可能的情况，具体情况由其内部的电气元件的组合状态决定.设3端网络的N1和N2为开关，N3为电阻，等效模型有4种情况如图3所示.

图3 3端网络的等效模型情况

2.2 子网络模块等效模型的判断方法

选择合适的子网络模块的等效模型，先要对子网络模块的内部元件状态进行分析，主要是可控类元件和可变状态元件.将其状态组合加入到子网络模块的邻接矩阵中，对新的邻接矩阵进行分析，找到合适的等效模型.子网络模块的等效采用经典算法——图的深度优先搜索(DFS，Depth－First Search)［9］.

运用深度优先搜索，以其中一个对外连接的端点为起点，另外一个对外连接端点为终点，如果能找到一条两个端点间的路径，则等效时子网络模块通过这两个端点有对外的连接关系;否则，没有连接关系［10］.若是多端网络，则多次使用深度优先搜索进行判断即可.判断过程如图4所示.

图4 深度优先搜索流程图

3 潜通路分块分析方法

对电路系统网络分块以及对子网络模块等效之后，关键是运用现有的潜通路分析方法和软件对简化后的电路系统进行潜通路分析.如果子网络模块有m个可控类元件和可变状态元件，进行子网络模块等效时，需要分析的组合状态的个数至少为2m.为了简化分析，选择一种先对假设等效模型进行潜通路分析，再根据出现潜通路的情况去分析组合状态的方法，只需要分析出现潜通路时的组合状态即可.具体分析步骤如下:

1)判断子网络模块是几端网络，从而判断其等效的结点个数;

2)对子网络模块的结点模型进行连接关系的组合，将所有的组合情况简化等效并进行潜通路分析;

3)根据潜通路分析的结果，判断出现潜通路情况时各个子网络模块的等效模型，用图的深度优先搜索算法搜索路径，分析此时子网络模块内部元件的组合状态.

4 潜通路分块分析案例

以图5为例来简述对于电路系统潜通路分块分析的步骤.本文只阐述对电路系统的分块过程以及分块后子网络模块的等效过程.图5是一个简单的两电源供电电路系统.

图5 潜通路分块分析示例电路图

4.1 电路系统分块

根据图论的知识将其用图论中的模型图表示，对电路网络模型进行处理，去掉电源和地节点以及它们与其他元件的连接关系.如图6所示去掉虚线框中电源和地的节点以及连接关系.

图6 电路网络模型示意图

该图形处理后的邻接矩阵是一个18×18的对称矩阵:

对该邻接矩阵用基于Laplace矩阵的谱平分法进行分块，自动返回的分块结果为:Vcut表示分块点集，该图具有两个分块点9和18.V1和P1分别代表第1个子网络所包含的节点及其邻接矩阵，其编号对应实际电路系统图中的元件;V2和P2分别代表第2个子网络的邻接矩阵和节点.

4.2 子网络模块等效

子网络模块等效时先分析其内部的电气元件的类型.以P2子网络模块为例进行分析，其等效模型为1个3端网络，用1个点P2表示其内部结构，用3个外结点表示其与外部的连接关系，其结点等效模型如图2所示，其中U1=N1，U2=N2，U3=N3，P2=S3.

其可能的等效模型有5种，针对其内部电气元件类型进行具体分析，结点1和结点9为开关元件，属于受控类元件，其余元件都属于固定状态元件.因此，P2等效为一个受控类的特殊器件.把该模块中开关元件的组合状态加入到邻接矩阵中.它包含了2个开关，其组合状态有4种，U1U3=00，U1U3=01，U1U3=10，U1U3=11.

将其内部开关的组合状态依次加入到邻接矩阵P2中进行分析，例如将开关组合U1U3=00加入邻接矩阵，可得新的邻接矩阵为

用深度优先搜索判断，可知其返回结果都为0，即此种开关组合状态下，该子网络模块没有通过任何端点连接到电路系统中，所以此时的等效模型为图3a所示.依次对开关的其它组合状态进行等效模型判断，其结果如图3所示.

相同的方法分析可得子网络模块P1的等效模型.将这些组合状态分别运用到简化的电路系统模型中进行潜通路分析即可，对于潜通路分析的步骤这里不再详细阐述.

5 结论

本文针对现有潜通路分析算法在进行大型电路系统潜通路分析时面临的占用过多的存储空间以及计算时间过长等问题，改进算法对大拓扑电路采用分块分析的方法.本文采用的潜通路分块分析方法简化了分析模型，提高了分析的速度，减少了分析算法所需的存储空间以及分析过程的人工参与，节省了分析所用的资源，从而促进了潜通路分析的自动化水平的提高，具有很大的实用价值.

References)

［1］ 邹涛，马齐爽.基于网络流仿真的潜通路分析方法［J］.北京航空航天大学学报，2012，38(4):546－550 Zou Tao，Ma Qishuang.Method based on network flow simulation for sneak circuit analysis［J］.Journal of Beijing University of Aeronautics and Astronautics，2012，38(4):546 － 550(in Chinese)

［2］ Zou Tao，Ma Qishuang.Research of sneak circuit analysis using network flow simulation［C］//Proceedings of IEEE 2012 Prognostics and System Health Management Conference，PHM－2012.Washington:IEEE Computer Society，2012:1 －5

［3］ 徐萍，马齐爽，邹涛.开关电路潜通路分析的一种方法［J］.北京航空航天大学学报，2011，37(3):360－363 Xu Ping，Ma Qishuang，Zou Tao.One sneak circuit analysis method for the switch circuit［J］.Journal of Beijing University of Aeronautics and Astronautics，2011，37(3):360 － 363(in Chinese)

［4］ Zou Tao，Ma Qishuang.The research of sneak circuit analysis based on artificial neural network［C］//Proceedings of the 7th International Conference on“Mathematical Methods in Reliability”:Theory，Methods，Applications.Beijing:Beijing Institute of Technology Press，2011:634 －638

［5］ 徐俊明.图论及其应用［M］.2版.合肥:中国科学技术大学出版社，2004:24－27 Xu Junming.Graph theory and its application［M］.2nd ed.Hefei:University of Science and Technology of China Press，2004:24－27(in Chinese)

［6］ 谢福鼎，张磊，嵇敏，等.一种基于谱平分法的社团划分算法［J］.计算机科学，2009，36(11):186 －188 Xie Fuding，Zhang Lei，Ji Min，et al.Community partitioning algorithm based on spectral bisection method［J］.Computer Science，2009，36(11):186 －188(in Chinese)

［7］ 张娜.复杂网络社区结构划分算法研究［D］.大连:大连理工大学，2009 Zhang Na.Partitioning methods for community structure in complex networks［D］.Dalian:Dalian University of Technology，2009(in Chinese)

［8］ 梁浩.图的拉普拉斯矩阵和临界群［D］.合肥:中国科学技术大学，2009 Liang Hao.Laplacian matrix and critical group of a graph［D］.Hefei:University of Science and Technology of China，2009(in Chinese)

［9］ 周泰.图的深度优先遍历算法及运用［J］.电脑编程技巧与维护，2011，17(16):93 －94 Zhou Tai.The DFS for graph and its application［J］.Computer Programming Skills＆ Maintenance，2011，17(16):93 － 94(in Chinese)

［10］ 杜恒，龚茜茹.图的深度优先遍历的C语言实现［J］.九江职业技术学院学报，2004，4(2):26－28 Du Heng，Gong Qianru.The C language of depth－first ergodicity of graph［J］.Journal of Jiujiang Vocational ＆ Technical College，2004，4(2):26 －28(in Chinese)