生成有向图中全部初级有向回路的扩展 精灵论文

生成有向图中全部初级有向回路的扩展 精灵论文 生成有向图中全部初级有向回路的扩展 夏济仁，张杰 (北京邮电大学信息光子学与光通信研究院，北京 100876) 摘要:本文对生成有向图中全部简单回路的算法进行扩展，算法的主要思想是采用分治法对 图划分子图，再对子图中定点进行收缩，求出部分节点间的通路，利用割集中若存在回路， 则割集中必有方向不同的边的性质，将子图合并，求出有向图中所有回路。 关键词: 有向图;简单有向回路;L-邻接矩阵 中图分类号:O157.6 An extension of finding all elementary circuits in a directed graph Jiren Xia, Jie Zhang (Key Laboratory of Information Photonics and Optical Communications (Beijing University of Posts and Telecommunications), Ministry of Education, Beijing 100876) Abstract: An Extension of creating all elementary circuits in a directed graph is proposed. The main idea is to partition a directed graph into small subgraphs, and remove vertices respectively from the subgraphs one by one and to find out elementary circuits. When subgraph is shrunk to a point, a subset of all elementary circuits is found. By the form of removing vertices exclude edge nodes, paths between two specific vertices is found. Using the direction information of the cut set between two subgraphs and paths between specific vertices, the all elementary circuits in graph are obtained. Key words: directed graph; elementary directed circuits; L-adjacent matrix 0 引言 在计算机科学、电网络的机辅分析设计以及规划等领域中，经常需用到图的理论解决问 [1]，需要求出图的全部回路。例如在面向对象软件的集成测试中，为了确定类的测试次序， 需要求出类图的全部回路，寻找一条关联多个回路的边，打破这条边，将类图从网状结构转 变为树状结构，得到类的测试次序，从而确保测试成本最低。再者，如在对电网络的规划设 计中，要避免同步时钟环路的形成。对于图的回路研究由来已久，但很多是针对无向图的， [1] [2]无向图中回路的生成算法不能简单地应用鱼有向图中。 本文扩展了文献[1]中求全部简单回路的方法，引入子图的概念，避免文献[3]中计算所 有节点间通路，利用分治法降低了求解大型复杂网络中简单回路算法的时空复杂度。 1 基本概念 定义 1 由 v, v,..., v中无重复字符组成的长度小于等于 n ， 1的字符串(仅首位字符 1 2 n [3]可相同)构成的集合成为 L 集合。 定义 2 设 M , {m| i , 1, 2, ..., r}, N , {n | j , 1, 2,..., s} 分别为由 r 个字符串和 s 个 i j 字符串构成的向量，m, m L 。则 M 与 N 的连接积 P , M N 中元素仍然属于一个 L 集 i j 基金项目:973 (2010CB328204)，国家 863 计划(2008AA01A329，2006AA01Z244)，国家自然科 学基金(60772022，60932004) 作者简介:夏济仁(1984-),男,硕士研究生,主要研究方向:下一代光网络. E-mail: loop.t@foxmail.com [3] 合。 定义 3 以 L 集合为元素的矩阵 M , (m)称为 L 矩阵，其中 m示矩阵中第i 行， ij n,m ij [3] [4]第 j 列交点处元素。 定义 4 设 M , (m), N , (n)都是 L 矩阵，则 M 与 N 的连接积 Q , M N 也 ij mk ij k n ,, [3]是 L 矩阵，其中 Q , (q), ij m,n k q, ? (m n) (1 , i , m,1 , j , n) ij ir rj r ,1 定义 5 设图 G , (V , E) 为具有 n 个定点的简单有向图，则称 n 阶 L 矩阵 M , (m) ij m,n 其中 , v ) E(G)0 (v, i j m, ,ij (v , v ) E(G)vv i j i j; [3] 为图 G 的 L 邻接矩阵。 定义 6 定义图 G , (V , E) 的边矩阵为 E , (e)，其中 ij nn , e, (v, v ) 简记为 vv . j ij i i j 可见矩阵 E 中的元素是集合 L 的子集。 T 记 E 中第 i 个列向量 E, [e, e,..., e,..., e] (1 , k , n, k , i) ， E 中第 i 个行向量 c 1i 2i ki ni i ,..., eE , [e , e ,..., e] (1 , k , n, k , i) ，W , E E 为矩阵 E 对应的通路矩阵。可见ri i ik in1 2 cr i i i对应标量 i ，通路矩阵中的元素描述了经过定点 v的所有长度不超过 2 的通路。 i 2 算法 2.1 单个子图情况下 步骤 1:形成图 G , (V , E) 的 L 邻接矩阵 E , (e)，记做 E (k ), k , 1; ij nn , 步骤 2:对 E 同时进行相同的初等行变换与初等列变换，将子图的边界节点变换到矩阵的右 (k ) ; 下角，计算通路矩阵W (k ) , E(k ) Ec r i i 步骤 3:修改边矩阵: k , k ， 1; E(k ， 1) , E (k ) ， W (k ); 转至步骤 2; 步骤 4: E (n 1) 对角线上元素即为所求环路，结束。 2.2 多个子图情况下，不妨讨论只有两个子图的情形 1. 用任意割集，将图划分为两个子图:V,V。分别对V,V使用上述方法得子图内环 s t s t 路，组成环路集合 M; 1 2. 求子图间边界节点的连通路径:收缩除边界节点外其他节点，得到边界节点之间的 通路; 3. 令 L 集合 A , {a| a, vv , v V, v V} ij ij i j i s j t L 集合 B , {b| b, vv, v V, v V} uv uv u v v s u t 计算 P , A B 。将 2 中结果带入 P 中组成回路集合 M ，与 M合并得网络环路集合 2 1 M , M? M 。 1 2 3 实例 图 1 有向图 G Fig.1 Directed Graph G , v, v, v, v} V,{v, v, v, v, v, v, v} V。 设{v1 2 3 4 5 s 6 7 8 9 10 11 12 t 分别计算V,V中环路: s t vv0 0 0 0 ,, 15 , ,vv0 0 0 0 2 1 ,, ,,E(1) , vvvv0 vv0 s 313234 , ,0 00 0 vv 4 3 , , 0 0 vvvv0 5354 0 0 0 0 vv , ,15 , ,vv0 0 0 vvv21 215 ,, ,,E(4) , vvvv0vvvvv, vvvvs 3132 34315 3215 , ,0 0vvvv, vvvvvvvvvv 4315 43215 43434 , , ,,vvvv 0 0vvvv, vvvvv, vvvvv, vvvvvv , 53545315 53215 54315 543215 , 得环路: vvv, vvvv, vvvvv, vvvvv, vvvvvv 434 5315 53215 54 315 543215 同理， 对原始边矩阵同时进行初等行与初等列变换，见边界节点对应行与列挪动到矩阵后方， 得 v0 0 0 vvv vv 0 , ,911 9697 , ,0 0 0 0 0 0vv10 12 , , , ,0 0 0 0 0 0vv 118 , ,E(1) , vv0 0 vv0 0 vv t 129 121112 7 ,, , , 0 0 0 0 0 0 0 , ,vv0 0 0 00 0 , ,7 6 , ,0 vv0 0 0 0 0 , 810, vv0 vvvv0 0 0 , ,9119 69 7 , ,0 0 00 0 0 vv 10 12 , , , ,0 0 0 0 0 0vv118 , ,E(6) , vv0 vv, vvv0vvvvv, vvvvvv, vvvv t 12 9 12 11 129 11 129612 7 12 9 712 118 12 9 118 ,, , , 0 0 0 0 0 0 0 , ,0 0 0 0vv0 0 , 7 6 ,, 0 vvvvvvvvvvvv, vvvvv0 vvvvvvv, vvvvvv 8 10810 12 810 12 9 6 810 12 7 810 1297 810 12 118 810 12 9 118 , v, v得环路: vvvvvvvvv 81012 118 810129118 于是 M, {vvv, vvvv, vvvvv, vvvvv, vvvvvv} ?{vvvvv, vvvvvv} 1 434 5315 53215 54315 543215 81012118 810 12 9 118 计算边界节点间通路: 在 E(1) 基础上依次收缩节点 v, v, v得矩阵: s 1 2 3 vvvvv vvv, vvvv, vv v, ,434415 4315 4 32 15 , ,vv, vvvvvvv, vvvvv, vvvv, vvvvv, vvvvvv 54 5345315 532 15 5415 54 315 543215 ,,得V边界节点 v, v间通路 s 4 5 Path(vv) , vvv, vvvv, vvvvv 45 4 15 4315 4 3215 Path(vv) , vv, vvv 54 54 534 在 E(1) 基础上分别收缩节点 v, v, v, v得: t 9 10 11 12 0 0 0 , , , ,vv0 0 7 6 , ,,vvvvvvvvv, vvvvvvvvvv, vvvvvv ,810 1296810127 810 129781012118 810129118 计算 v, v, v间通路 6 7 8 收缩节点 v，得 Path(vv) , {vvvv, vvvvv} 6 87 810127 81012 9 7 收缩节点 v，得 Path(vv) , {vvvvv, vvvvv, vvvvvv} 7 86 81012 9 6 810 127 6 81012 9 7 6 收缩节点 v，得 Path(vv) , vv 8 7 6 7 6 计算割集关联环路 A , {vv, vv}, B , {vv, vv} 4 7 4 8 7 5 65 M , A B , {vvv, vv vv, vv vv, vv vv} 2 47 5 4 7 65 48 7 5 4 8 6 5 vvv, vvv{vv, vvv} , {vvvv, vvvvv} 4 7 54 7 554 534 4 7 54 4 7 534 vv vv, vvvv{vv, vvv} , {vvvvv, vvvvvv} 4 7 65 4 7 6 554 534 47 654 4 7 6 534 vv vv, vv{vvvv, vvvvv}vv, {vvvvvv, vvvvvvv}{vv, vvv} 4 8 7 5 48810 12 7 810 12 97 7 5 4 810 12 7 5 4 810 12 9 7 5 54 534 , {vvvvvvv, vvvvvvvv, vvvvvvvv, vvvvvvvvv}4 810 12 7 54 4 810 12 7 534 4810129 7 54 4 810129 7 534 vv vv, {vvvvvvv, vvvvvvv, vvvvvvvv}{vv, vvv} 4 8 65 4810129 6 5 4810127 65 4810129 7 6 5 54 534 vvvvvvvvv, {vvvvvv, vvvv, vvvvvv,4 810 12 96 54 48101296 534 4810 12 7 6 54 vvvvvvvvv, vvvvvvvvv, vvvvvvvvvv}4 810 12 7 6 534 4 810 12 97 654 4 810129 7 6 534 由步骤 2 查找 vv, vv, vv, vv间路径，得 7 6 54 87 86 Path(vv) , {vv} 7 6 7 6 Path(vv) , {vv, vvv} 54 54 534 Path(vv) , {vvvv, vvvvv} 87 810127 81012 9 7 Path(vv) , {vvvvv, vvvvv, vvvvvv} 86 81012 9 6 810 127 6 81012 9 7 6 带入 A B 得 M , {vvv{vv, vvv}, vvvv{vv, vvv}, 2 4 7 554 534 4 7 6 554 534 vv{vvvv, vvvvv}vv{vv, vvv}, 48810127 8101297 7 554 534 vv{vvvvv, vvvvv, vvvvvv}vv{vv, vvv}} 48810129 6 810 127 6 81012 9 7 6 6554 534 , {{vvvv, vvvvv},{vvvvv, vvvvvv}, 47 54 47 534 4 7 654 4 7 6534 {vvvvvvv, vvvvvvvv, vvvvvvvv, vvvvvvvvv},481012 7 54 4 810127 534 48101297 54 481012 9 7 534 {vvvvvvvv, vvvvvvvv, vvvvvvvv,481012 9 6 54 4 810129654 4810 127 654 vvvvvvvvv, vvvvvvvvv, vvvvvvvvvv}} 481012 7 6 534 4810 1297 654 48101297 6534 得所有环路: M , M? M 1 2 , {vvv, vvvv, vvvvv, vvvvv, 434 47 54 47 534 47 654 vvvvvv, vvvvvvv, vvvvvvvv,47 6534 481012 7 54 4 81012 7 5 34 vvvvvvvv, vvvvvvvvv, 481012 7 6 54 481012 7 6 534 vvvvvvvv, vvvvvvvvv, 481012 9 6 54 481012 9 6 534 vvvvvvvv, vvvvvvvvv481012 9 7 54 481012 9 7 534 vvvvvvvvv, vvvvvvvvvv, 481012 9 7 6 54 481012 9 7 6 534 vvvv, vvvvv, vvvvv, vvvvvv5315 53215 54 315 543215 vvvvv, vvvvvv}81012118 81012 9 118 4 结论 算法运用子图的概念对网络进行分治，将求解图中所有节点间通路的计算减少为只计算 割集中边所对应节点的通路，并继承文献[1]中算法的优点，利用收缩节点的方法计算特定 节点间路径。算法思路清晰，原理简单。 [参考文献] (References) [1] 王玉英，陈平，苏旸. 生成有向图中全部简单回路的一种新算法，2008，36(4)，12~15 [2] James C T. An efficient search algorithm to find the elementary circuits of graph[J]. Communications of the ACM，1970，13(12):273~276 [3] 毕双艳，郭金海，齐明. 有向图中初级有向回路的求解算法及实例[J]. 长春邮电学院学报，1999，17(2): 41~45 [4] 郭俊杰，伊崇信，毕双艳. 哈密顿回路存在性判定及输出算法[J]. 吉林大学自然科学报，1998(2):5~8[5] 刘耀年. 从有向图的通路矩阵生成有向图的全部有向回路的一个算法[J]. 电工技术学报，1992(2):58~60 [6] 温天，司玉娟，于枫. 从有向图的关联矩阵寻找其全部有向回路的计辅算法[J]. 电工技术学报， 1989(3):31~36