网络系统最小割集的一种矩阵分解

1、2007年 4月 第 30卷 第 2期 北 京 邮 电 大 学 学 报 Journal of Beijing University of Posts and Telecommunications Apr. 2007Vol. 30No. 2 文章编号 :100725321(2007 0220123204网络系统最小割集的一种矩阵分解 余良德 , 孙新利 , 彭亚会 (第二炮兵工程学院 103教研室 , 西安 710025 摘要 :为了寻求计算双终端网络系统最小割集更为简明的方法 , , 形成了广义联络矩阵 的概念 , 并基于此提出了一种矩阵分解算法 , . 同时 阐述了算法的理论原理及计算步骤

2、, 并给出了冗余节点 、 算例验证了本理论的正 确性和适应性 . 关 键 词 :网络可靠度 ; 最小割集 中图分类号 :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

3、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.

4、 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 收稿日期 :2006204220 作者简介 :余良德 (1981 , 男 , 博士生 , E 2mail :

5、yu -. 0 引 言 随着社会和科学技术的不断发展 , 网络化已经 成为一种趋势 , 例如输电网络 、 集成电路网络 、 交通 网络等 , 因此 , 网络可靠性的研究在分布式系统中的 作用与日俱增 1, 其计算方法已成为国内外研究热 点 , 并取得了许多研究成果 1210. 在众多算法中 , 网 络的最小路集起着十分重要的作用 , 其求法已有联 络矩阵 、 布尔行列式 、 深度优先搜索 2等许多有 效算法 . 然而 , 在一些复杂网络中 , 最小路集数目 繁多 , 导致计算量猛增 , 使其应用受到限制 ; 相反 , 其最小割集数目相对较少 , 这就使得最小割集的应 用成为必然 3. 例如对于

6、一个 2 100的网格网 络 , 它有 299个 最 小 路 集 , 而 仅 有 1万 个 最 小 割集 1, 3. 针对有向或无向网络 , 已有一些求最小割集的 算法 . 文献 1, 4提出了一种适用于有向网络的迭 代算法 ; 文献 3结合组合数学和布尔代数知识 , 对 网络中元件间布尔运算的结果进行组合 , 提出了一 种有序二叉决策图 (OBDD 算法 , 该算法能直接得 到网络最小割集的不交化形式 , 但计算过程比较复 杂 ; 文献 5提出了一种蒙特卡罗估计算法 , 该算法 的效率取决于对已知寿命分布网络元件的抽样方 法 ; 文献 7认为文献 10的算法最有效 , 该算法能 在线性时间内

7、求取单个最小割 , 但求最小割集的时 间复杂度仍很大 . 上述算法各有优点 , 但不具有普 遍适用性 , 对于求解一般意义的网络最小割集不是 十分有效 . 本文基于矩阵理论 , 通过扩展定义和规 定运算规则 , 提出一种计算双终端网络系统最小割 集的矩阵分解算法 , 最后用实例验证了该算法的有 效性及易于在计算机上实现的特点 . 1 算法原理 假设 G (N , E N 和边集合 E 组成的双终端网络 , e i (i 1, 2, , m 表示 E 中的 m 个边变量 , n i (i =1, 2, , n 表示 N 中的 n 个节 点变量 ; 规定 n 1为源点 s , n n 为汇点 t.

8、 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个割 , 如果不包含其 他割 , 则 E (X 就为

9、 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

10、, G 2 为 1个最小割 . 如果 G 2不连通 , 则 G 2中含有冗余节点 , 可将该冗余节 点合并到 G 1中 , 形成新的 、 连通的 G 1和 G 2. 这就 是寻求最小割集的基本出发点 . 2 广义联络矩阵分解算法 211 基本定义和运算规则 扩展传统联络矩阵的定义 , 定义广义联络矩阵 C =(c ij n n 为 c ij = e l n i 和 n j 之间有边 e l 直接相连 , i j , l =1, 2, , m 0n i 和 n j 之间没有边直接相连 , i j n k 节点标号 , i =j , k =1, 2, , n 式中 n e j =e i e j e

11、 i 0=e i 0 e j =e j 0 0=0 从传统意义上讲 , 除了源点 s 和汇点 t 外的任 一节点 , 如果仅与另一节点相连 , 则该节点是冗余 的 . 但在本算法中 , 根据模型原理 , 如果 G 2不连通 , 则 G 2中含有冗余节点 , 即如果 1个节点与 G 1相 邻 , 且只能通过 G 1到达 t , 则该节点是冗余的 ; 也即 在广义联络矩阵及其子矩阵中 , 如果矩阵中的某一 行元素除节点标记外 , 其余均为 0, 则该节点是冗余 的 . 如果矩阵中存在冗余节点 , 则该矩阵不产生最 小割 , 将冗余节点所在行和列的全部元素删除 , 并将 该节点添加到 S 中 , 形

12、成新的子矩阵 . 此外 , 由于算法是逐步构造子网络的过程 , 因 此 , 在广义联络矩阵分解的过程中可能会出现网络 子图同构 325. 如果 2个矩阵中 S 所对应的节点元 素一样 , 则它们所表示的子图是同构的 , 即这 2个矩 阵输出的最小割相同 . 为此 , 在算法过程中 , 对维数 相同的矩阵需要判断是否存在子图同构 , 以避免重 复运算 . 212 算法步骤 广义联络矩阵有效地描述了网络的拓扑结构 , 按照一定运算规则对其逐步分解能形成满足模型的 子网络 , 同时输出相应的最小割 . 步骤 1 根据网络的拓扑结构写出广义联络矩 阵 C , 在 C 中 c 11构成了节点子集 S 的

13、全部元素 , 合 并第 1行其他非 0元素 , 输出网络的 1个最小割 . 步骤 2 选取 C 第 1行中不为 0的非节点元 素 , 并标记每个元素的节点标号 . 如果第 1行中汇 点所在列的元素不为 0, 则不对其进行处理 . 因为该 元素不为 0意味着源点和汇点之间有边直接相连 , 如果对该边进行处理 , 则源点和汇点将出现在同一 421北 京 邮 电 大 学 学 报 第 30卷 个节点子集中 , 这显然与算法原理不符 . 事实上 , 如 果源点和汇点之间有边直接相连 , 则网络的任意一 个最小割均包含该边 . 步骤 3 任意选取一个符合第 2步条件的元 素 , 不妨设其节点标号为 n k

14、 , 即 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

15、对步骤 3所产生的子矩阵再重复步骤 2和步骤 3, 直到最后得到的矩阵是 1个二维矩阵为 止 , 即网络中只剩源点和汇点 . 该二维矩阵的第 1行第 2列元素构成 1个最小割 . 步骤 6 归并前几步产生的最小割 , 最终得到 原网络的最小割集 . 综上所述 , 广义联络矩阵分解算法能产生网络 的最小割集 . 该算法的本质是在一定运算规则下的 矩阵分解 , 易于在计算机上实现 . 衡量一个算法是 否有效的关键 , 除了其自身逻辑判断的正确性外 , 算 法要求的存储量和所需的运行时间也是十分重要的 2个尺度 , 这就是通常所说的算法的空间和时间复 杂度 . 根据算法原理和步骤可知 , 本文算法的

16、时间 复杂度为 O (m 、 空间复杂度为 O (n 2 , 为流出 源点的边数目 , 显然该算法为线形时间算法 , 这在很 大程 度 上 减 小 了 文 献 10算 法 的 时 间 复 杂 度 O (m +n c st (c st 为网络最小割的数目 . 一般而 言 , 网络的联络矩阵为稀疏矩阵 , 因而大型网络的联 络矩阵需要占用很大的内存空间 327, 为解决这个 问题 , 可以尝试用其他数据结构 , 如链表来存储联络 矩阵 . 3 算例分析 利用矩阵分解算法 , 求解图 1所示的网络最小 割集 . 依定义 , 网络的广义联络矩阵 C 为 图 1 含 5个节点 、 7条边的网络 s (n

17、 1 n 2n 3n 4t (n 5 C s (n 1 n n 4 t (n 5 s 0e 10 0300 0n 3e 4e 7 00e 5n 4e 6 0000t 由矩阵 C 的第 1行即可输出 1个最小割 e 1e 2. C 中第 1行不为 0的非节点元素有 e 1、 e 2, 与之 对应的节点标号分别为 n 2、 n 4, 分别按照算法步骤 3处理可得 C n 2 = s , n 2e 3e 10 0n 3e 4e 7 0e 5n 4e 6 000 C n 4 = s , n 4e 2e 5e 6 0n 2e 30 00n 3e 7 000 由 C n 2 和 C n 4 可分别输出最小

18、割 e 1 e 3、 e 2e 5e 6. 继续对 C n 2 和 C n 4 分解 , 可知 C n 2 n 4 和 C n 4 n 2 将出现同 构 , 分别得 C n 2 n 4 =C n 4 n 2 = s , n 2, n 4e 3e 5e 6 0n 3e 7 00t C n 2 n 3 = s , n 2, n 3e 1e 4e 7 0n 4e 6 00t C n 4 n 3 = s , n 3, n 4e 2e 6e 7 0n 20 00t 根据冗余节点的判断规则 , C n 4 n 3 中的 n 2为冗 余节点 , 故 C n 4 n 3 不输出最小割集 . 由 C n 2 n

19、 4 和 C n 2 n 3 分别输出最小割集 e 3e 5e 6、 e 1e 4e 7. 对 C n 2 n 4 合并节点 n 3、 C n 2 n 3 合并节点 n 4、 C n 3 n 4 521第 2期 余良德等 :网络系统最小割集的一种矩阵分解 合并节点 n 2, 将出现同构 , 结果为 C n 2 n 3 n 4 = s , n 2, n 3, n 4e 6e 7 0t 输出最小割 e 6e 7. 至此 , 矩阵分解完毕 , 最后得到网 络的最小割集为 e 1e 2、 e 1e 3、 e 6e 7、 e 2e 5e 6、 e 3e 5e 6、 e 1e 4e 7. 根据算法分析 ,

20、 运用本算法该算例至多在 m = 27=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

21、terminal pair network using OBDD C Proceedings of the 27th An 2 nual International Computer S oftware and Application Conference. Washington :IEEE Computer S ociety , 2003:3682373. 2 孙新利 , 陆长捷 . 工程可靠性教程 M .北京 :国防工 业出版社 , 2005:49258. Sun Xinli , Lu Changjie. Reliability engineering M . Beijing :Natio

22、nal Defense Industrial Press , 2005:49258. 3 Lin Hung 2Y au , Kuo Sy 2Y en , Y eh Fu 2Min. Minimal 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 Co

23、m 2 puter 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 2 Houston :Univ of Houston , 1993:2462250. 武小悦 . 复杂关联系统的可靠性建模与分析 D .长