2007年4月
第30卷第2期
北京邮电大学学报
Journal
of Beijing University of Posts and Telecommunications
Apr. 2007Vol. 30No. 2
文章编号:100725321(2007) 0220123204
网络系统最小割集的一种矩阵分解
余良德, 孙新利, 彭亚会
(第二炮兵工程学院103教研室, 西安710025)
摘要:为了寻求计算双终端网络系统最小割集更为简明的方法, , 形成了广义联络矩阵的概念, 并基于此提出了一种矩阵分解算法, . 同时阐述了算法的理论原理及计算步骤, 并给出了冗余节点、算例验证了本理论的正确性和适应性.
关 键 词:网络可靠度; 最小割集中图分类号:TP20211A Matrix Decomposition Algorithm for Enumerating
All Minimal Cut 2Set of a N et work
YU Liang 2de , SUN Xin 2li , PEN G Ya 2hui
(103Department , The Second Artillery Engineering College , Xi ’an 710025, China )
Abstract :The definition of adjacent matrix was extended in order to effectively enumerate all minimal cut 2set of a terminal network. And a matrix decomposition algorithm was then proposed. The algo 2rithm is based on recursive matrix decomposition and reduction. The theoretical rationale and opera 2tional rules are given. The judgment principles and reduction rules about redundant nodes and isomorphic graphs are presented. The examples given show correctness and applicability of the algorithm.
K ey w ords :network reliability ; minimal cut 2set ; adjacent matrix
0 引 言
随着社会和科学技术的不断发展, 网络化已经成为一种趋势, 例如输电网络、集成电路网络、交通网络等, 因此, 网络可靠性的研究在分布式系统中的作用与日俱增[1], 其计算方法已成为国内外研究热点, 并取得了许多研究成果[1210]. 在众多算法中, 网络的最小路集起着十分重要的作用, 其求法已有联络矩阵、布尔行列式、深度优先搜索[2]等许多有效算法. 然而, 在一些复杂网络中, 最小路集数目
繁多, 导致计算量猛增, 使其应用受到限制; 相反, 其最小割集数目相对较少, 这就使得最小割集的应用成为必然[3]. 例如对于一个2×100的网格网络, 它有299个最小路集, 而仅有1万个最小割集[1, 3].
针对有向或无向网络, 已有一些求最小割集的算法. 文献[1, 4]提出了一种适用于有向网络的迭代算法; 文献[3]结合组合数学和布尔代数知识, 对网络中元件间布尔运算的结果进行组合, 提出了一
种有序二叉决策图(OBDD ) 算法, 该算法能直接得
收稿日期:2006204220
) , 男, 博士生, E 2mail :yu -ld1024@sina.com. 作者简介:余良德(1981—
124北京邮电大学学报 第30卷
到网络最小割集的不交化形式, 但计算过程比较复
杂; 文献[5]提出了一种蒙特卡罗估计算法, 该算法的效率取决于对已知寿命分布网络元件的抽样方法; 文献[7]认为文献[10]的算法最有效, 该算法能在线性时间内求取单个最小割, 但求最小割集的时间复杂度仍很大. 上述算法各有优点, 但不具有普遍适用性, 对于求解一般意义的网络最小割集不是十分有效. 本文基于矩阵理论, 通过扩展定义和规定运算规则, 提出一种计算双终端网络系统最小割集的矩阵分解算法, 最后用实例验证了该算法的有效性及易于在计算机上实现的特点.
C =(c ij )
n n
为
n i 和n j 之间有边e l 直接相连,
e l
c ij =
n k
i ≠j , l =1, 2, …, m n i 和n j 之间没有边直接相连, i ≠j 节点标号,
i =j , k =1, 2, …, n
式中n e j =e i e j e i 0=e i
1 算法原理
假设G (N , E ) N 和边集合E 组成的双终端网络, e i (i 1, 2, …, m ) 表示E 中的
m 个边变量, n i (i =1, 2, …, n ) 表示N 中的n 个节
0 e j =e j 0 0=0
点变量; 规定n 1为源点s , n n 为汇点t. X 表示N 的子集, E (X ) 表示E 的子集且与X 相对应, 则X 和E (X ) 构成了G (N , E ) 的1个子网络G (X , E (X ) ) , 简记为G. 如果存在1条从节点n i 指向节点n j 的有向边e i =〈n i , n j 〉, e i ∈E (无向边可用1对平行、方向相反的有向边替换) , 使n i ∈X 且n j ∈/X , 则称n j 与G 相邻. 如果E (X ) 中所有边的失效导致网络中源点s 和汇点t 不连通, 则E
(X ) 构成了网络G (N , E ) 的1个割, 如果不包含其
从传统意义上讲, 除了源点s 和汇点t 外的任
一节点, 如果仅与另一节点相连, 则该节点是冗余的. 但在本算法中, 根据模型原理, 如果G 2不连通, 则G 2中含有冗余节点, 即如果1个节点与G 1相邻, 且只能通过G 1到达t , 则该节点是冗余的; 也即在广义联络矩阵及其子矩阵中, 如果矩阵中的某一行元素除节点标记外, 其余均为0, 则该节点是冗余的. 如果矩阵中存在冗余节点, 则该矩阵不产生最小割, 将冗余节点所在行和列的全部元素删除, 并将该节点添加到S 中, 形成新的子矩阵.
此外, 由于算法是逐步构造子网络的过程, 因此, 在广义联络矩阵分解的过程中可能会出现网络子图同构[325]. 如果2个矩阵中S 所对应的节点元素一样, 则它们所表示的子图是同构的, 即这2个矩阵输出的最小割相同. 为此, 在算法过程中, 对维数相同的矩阵需要判断是否存在子图同构, 以避免重复运算. 212 算法步骤
他割, 则E (X ) 就为1个最小割.
假设S 和T 为N 的2个不相交子集, 且s ∈S 、
t ∈T. 定义E (S , T ) 为连接S 和T 的所有边, 如
果E (S , T ) 中所有边均失效, 则s 和t 处于不连通状态, 从而E (S , T ) 构成了原网络的1个割, 如果
不包含其他割, 则E (S , T ) 就为1个最小割. 此外, 由于网络中与s 相连的所有边组成了1个最小割, 因此, 如果能找到G (N , E ) 的2个连通子网络G 1和G 2, 使s ∈G 1、t ∈G 2, 且任何一个与G 1相邻的节点都在G 2中, 则E (G 1, G 2) 为1个最小割. 如果
G 2不连通, 则G 2中含有冗余节点, 可将该冗余节
点合并到G 1中, 形成新的、连通的G 1和G 2. 这就是寻求最小割集的基本出发点.
2 广义联络矩阵分解算法
211 基本定义和运算规则
扩展传统联络矩阵的定义, 定义广义联络矩阵
广义联络矩阵有效地描述了网络的拓扑结构,
按照一定运算规则对其逐步分解能形成满足模型的子网络, 同时输出相应的最小割.
步骤1 根据网络的拓扑结构写出广义联络矩阵C , 在C 中
c 11构成了节点子集S 的全部元素, 合并第1行其他非0元素, 输出网络的1个最小割.
步骤2 选取C 第1行中不为0的非节点元素, 并标记每个元素的节点标号. 如果第1行中汇点所在列的元素不为0, 则不对其进行处理. 因为该元素不为0意味着源点和汇点之间有边直接相连, 如果对该边进行处理, 则源点和汇点将出现在同一
第2期 余良德等:网络系统最小割集的一种矩阵分解125
个节点子集中, 这显然与算法原理不符. 事实上, 如果源点和汇点之间有边直接相连, 则网络的任意一个最小割均包含该边.
步骤3 任意选取一个符合第2步条件的元素, 不妨设其节点标号为n k , 即c ii =n k (i ≠1) , 将
c ii 合并到c 11中; 同时将第i 行中其余元素与第1行
相应元素进行 运算, 运算结果保存在第1行相应位置, 然后删除第i 行和第j 列的所有元素, 则原来的n ×n 矩阵成为(n -1) ×(n -1) 矩阵C n k (C n k 表示合并节点n k 后所形成的子矩阵) . 判断C n k 中是否有冗余节点, 如果有, 则删除该节点, 并转步骤6; 如果没有, 则合并矩阵C n k 第1元素, 输出原网络的1.
步骤4 对步骤20元素分别按照步骤3的方法进行处理.
步骤5 对步骤3所产生的子矩阵再重复步骤2和步骤3, 直到最后得到的矩阵是1个二维矩阵为止, 即网络中只剩源点和汇点. 该二维矩阵的第1行第2列元素构成1个最小割.
步骤6 归并前几步产生的最小割, 最终得到原网络的最小割集.
综上所述, 广义联络矩阵分解算法能产生网络的最小割集. 该算法的本质是在一定运算规则下的矩阵分解, 易于在计算机上实现. 衡量一个算法是否有效的关键, 除了其自身逻辑判断的正确性外, 算法要求的存储量和所需的运行时间也是十分重要的2个尺度, 这就是通常所说的算法的空间和时间复杂度. 根据算法原理和步骤可知, 本文算法的时间复杂度为O (αm ) 、空间复杂度为O (n 2) , α为流出源点的边数目, 显然该算法为线形时间算法, 这在很大程度上减小了文献[10]算法的时间复杂度O ((m +n ) c st ) (c st 为网络最小割的数目) . 一般而言, 网络的联络矩阵为稀疏矩阵, 因而大型网络的联络矩阵需要占用很大的内存空间[327], 为解决这个问题, 可以尝试用其他数据结构, 如链表来存储联络矩阵.
图1 含5个节点、7条边的网络
s (n 1) n 2s (n 1) n C n 4
s
n 3n 4t (n 5) e 1
3n 3e 5
00
e 7e 6t
00
e 4n 4
000
t (n 5) 000
由矩阵C 的第1行即可输出1个最小割e 1e 2.
C 中第1行不为0的非节点元素有e 1、e 2, 与之
对应的节点标号分别为n 2、
n 4, 分别按照算法步骤3处理可得
s , n 2
C n 2=
e 3n 3e 5
e 1e 4n 4
e 7e 6e 6
000
s , n 4
e 2n 2
e 5e 3n 3
C n 4=
000
e 700
由C n 2和C n 4可分别输出最小割e 1
e 3、e 2e 5e 6. 继续对C n 2和C n 4分解, 可知C n 2n 4和C n 4n 2将出现同构, 分别得
s , n 2, n 4
C n 2n 4=C n 4n 2=
e 3e 5n 3
e 6e 7t e 7e 6t e 6e 7
00
e 1e 4n 4
s , n 2, n 3
C n 2n 3=
00
s , n 3, n 4
e 2n 2
C n 4n 3=
00
t
3 算例分析
利用矩阵分解算法, 求解图1所示的网络最小割集.
依定义, 网络的广义联络矩阵C
为
根据冗余节点的判断规则, C n 4n 3中的n 2为冗余节点, 故
C n 4n 3不输出最小割集. 由C n 2n 4和C n 2n 3分别输出最小割集e 3e 5e 6、e 1e 4e 7.
对C n 2n 4合并节点n 3、C n 2n 3合并节点n 4、C n 3n 4
126北京邮电大学学报 第30卷
[3] Lin Hung 2Y au , Kuo Sy 2Y en , Y eh Fu 2Min. Minimal
合并节点n 2, 将出现同构, 结果为
C n 2n 3n 4=
s , n 2, n 3, n 4
e 6e 7t
cut 2set enumeration and network reliability evaluation by recursive merge and BDD [C ]∥Proceedings of the Eighth IEEE International Symposium on Computers and Communication (ISCC ’03) . Washington :IEEE Com 2puter S ociety , 2003:134121346.
[4] Shier D R , Whited D E. Iterative algorithms for genera 2
ting minimal cut 2set in directed graphs [J].Networks , 1986, 16(4) :1332147.
[5] Lin J , Monte Carlo simulation to
system reliability [C ]∥Reliability and Maintainability Sym 2Houston :Univ of Houston , 1993:2462250. ] 武小悦. 复杂关联系统的可靠性建模与分析[D ].长
输出最小割e 6e 7. 至此, 矩阵分解完毕, 最后得到网
络的最小割集为e 1e 2、e 1e 3、e 6e 7、e 2e 5e 6、e 3e 5e 6、
e 1e 4e 7.
根据算法分析, 运用本算法该算例至多在αm =2×7=14步内收敛, 而文献[10]算法要在(m +n ) c st =(5+7) ×6=72步内才能收敛, 这说明了本算法的有效性.
4 结束语
, 络矩阵, . 在定义了广义联络矩阵运算规则的基础上提出了一种求网络最小割集的矩阵分解算法, 算法规则的含义直观明确, 易于编程实现, 并至多可以在αm 步内收敛. 参考文献:
[1] Chang Yung 2Ruei , Lin Hung 2Y an , Chen Ing 2Y i. A cut
based algorithm for reliability analysis of terminal pair network using OBDD [C]∥Proceedings of the 27th An 2nual International Computer S oftware and Application Conference.
Washington :
IEEE Computer
S ociety ,
2003:3682373.
[2] 孙新利, 陆长捷. 工程可靠性教程[M ].北京:国防工
沙:国防科学技术大学信息系统与管理学院, 2000.
Wu Xiaoyue. Reliability modeling and analysis of complex correlative system [D].Changsha :School of Information System &Management , National Univ of Defense Tech 2nology , 2000.
[7] Shier D R. Network reliability and algebraic structure
[M ].Oxford :Clarendon Press , 1991:62271.
[8] Behr A , Camarinopoulos L , Pampoukis G. Domination
of k 2out 2of 2n systems[J].IEEE Transaction on Reliabi 2lity , 1995, 44(4) :7052707.
[9]
Martelli H. A G aussian elimination algorithm for the
enumeration of cut sets in a graph[J].Journal of ACM , 1976, 23(3) :58273.
[10] Tsukiyama S , Shirakawa I , Ozaki H , et al. An algo 2
rithm to enumerate all cut 2set of a graph in linear time per cut [J].Journal of the ACM , 1980, 27(4) :6192632.
业出版社, 2005:49258.
Sun Xinli , Lu Changjie. Reliability engineering [M ].Beijing :National Defense Industrial Press , 2005:49258.