生成有向图中全部初级有向回路的扩展#

生成有向图中全部初级有向回路的扩展# 中国科技论文在线 生成有向图中全部初级有向回路的扩展 夏济仁，张杰 (北京邮电大学信息光子学与光通信研究院，北京 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 基本概念 v1, v2 ,..., vn 中无重复字符组成的长度小于等于 n ， 1的字符串(仅首位字符 由定义 1 可相同)构成的集合成为 L 集合[3]。 定义 2 设 M , {mi | i , 1, 2,..., r}, N , {n j | j , 1, 2,..., s}分别为由 r 个字符串和 s 个 字符串构成的向量，mi , m j L 。则 M 与 N 的连接积 P , M N 中元素仍然属于一个 L 集 基金项目:973 (2010CB328204)，国家 863 计划(2008AA01A329，2006AA01Z244)，国家自然科 学基金(60772022，60932004) 作者简介:夏济仁(1984-),男,硕士研究生,主要研究方向:下一代光网络. E-mail: loop.t@foxmail.com -1- 中国科技论文在线 合[3]。 定义 3 以 L 集合为元素的矩阵 M , (mij )n,m 称为 L 矩阵，其中 mij 表示矩阵中第 i 行， 第 j 列交点处元素[3] [4]。 定义 4 设 M , (mij )m,k , N , (nij )k ,n 都是 L 矩阵，则 M 与 N 的连接积 Q , M N 也 是 L 矩阵[3]，其中 Q , (qij )m,n , k , ? (m n qij ir rj ) (1 , i , m,1 , j , n) r ,1 定义 5 设图 G , (V , E) 为具有 n 个定点的简单有向图，则称 n 阶 L 矩阵 M , (mij )m,n 其中 , 0 (vi , v j ) E(G) mij , , (vi , v j ) E(G) ;viv j 为图 G 的 L 邻接矩阵[3]。 定义 6 定义图 G , (V , E) 的边矩阵为 E , (eij )n,n ，其中 eij , (vi , v j ) 简记为 viv j . 可见矩阵 E 中的元素是集合 L 的子集。 T ,..., e ,..., e 记 E 中第 i 个列向量 Eci , [e1i , e2i ki ni ] (1 , k , n, k , i) ， E 中第 i 个行向量 Er , [ei1, ei 2 ,..., eik ,..., ein ] (1 , k , n, k , i) ，W , Eci Er 为矩阵 E 对应的通路矩阵。可见 i i 对应标量 i ，通路矩阵中的元素描述了经过定点 vi 的所有长度不超过 2 的通路。 2 算法 2.1 单个子图情况下 步骤 1:形成图 G , (V , E) 的 L 邻接矩阵 E , (eij )n,n ，记做 E (k ), k , 1; 步骤 2:对 E 同时进行相同的初等行变换与初等列变换，将子图的边界节点变换到矩阵的右 下角，计算通路矩阵W (k ) , Eci (k ) Eri (k ) ; 步骤 3:修改边矩阵: k , k ， 1; E(k ， 1) , E (k ) ， W (k ); 转至步骤 2; 步骤 4: E (n 1) 对角线上元素即为所求环路，结束。 2.2 多个子图情况下，不妨讨论只有两个子图的情形 1. 用任意割集，将图划分为两个子图:Vs ,Vt 。分别对Vs ,Vt 使用上述方法得子图内环 路，组成环路集合 M1 ; -2- 中国科技论文在线 2. 求子图间边界节点的连通路径:收缩除边界节点外其他节点，得到边界节点之间的 通路; 3. 令 L 集合 A , {aij | aij , viv j , vi Vs , v j Vt } L 集合 B , {buv | buv , vu vv , vv Vs , vu Vt } 计算 P , A B 。将 2 中结果带入 P 中组成回路集合 M 2 ，与 M1 合并得网络环路集合 M , M 1 ? M 2 。 3 实例 图 1 有向图 G Fig.1 Directed Graph G 设{v1, v2 , v3 , v4 , v5} Vs ,{v6 , v7 , v8 , v9 , v10 , v11, v12} Vt 。 分别计算Vs ,Vt 中环路: 0 0 , 0 0 v1v5 , ,v v 0 0 0 , 2 1 0 ,, 0 0 , v3v4 Es (1) , ,v3v1 v3v2 , , 0 4v3 v, 0 0 0 , v5v4 v5v3 ,, 0 0 0 ,, , 0 0 v1v5 , 0 0 , ,v v 0 0 0 v2vv5 , 2 1 1 , 0 v3v4 v3v1v5 , v3v2v1v5 , Es (4) , ,v3v1 vv2 3 , , v4v3 v4vv4 3 , 0 0 v4v3v1v5 , v4v3v2v1v5 , v5v3 v5v4 v5v3v1v5 , v5v3v2v1v5 , v5v4v3v1v5 , v5v4v3v2v1v5 , ,, 0 0 , 得环路: v4v3v4 , v5v3v1v5 , v5v3v2v1v5 , v5v4v3v1v5 , v5v4v3v2v1v5 同理， 对原始边矩阵同时进行初等行与初等列变换，见边界节点对应行与列挪动到矩阵后方， 得 -3- 中国科技论文在线 0 0 , 0 0 , v9v11 9v7 9v6 vv , 0 0 0 0 0 10v12 v, 0 ,, 0 0 0 0 0 , 0 11v8 , v, , 0 0 0 v12v11 v12v7 v Et (1) , ,v12 9 0 , , 0 0 0 0 0 0 0 , , , 0 0 0 0 v7v6 , 0 0 , 0 0 0 0 , 0 v8v10 0 ,, , 0 0 , 0 0 , v9v11 v9v6 v9v7 , , 0 0 0 0 0 0 v10v12 , , 0 0 0 0 0 , 0 v11v8 , , , 0 0 v12v11, v12v9v11 v12v9v6 v12v7 , v12v9v7 Et (6) , ,v12v9 v12v11v8 , v12v9v11v8 , , 0 0 0 0 0 0 0 , , , 0 0 00v7v6 0 , , 0 0 , 0 v8v10v12v11v8 , v8v10v12v9v11v8 , v8v10 v8v10v12 v8v10v12v7 , v8v10v12v9v7 v8v10v12vv6 , 9 , 得环路: v8v10v12v11v8 , v8v10v12v9v11v8 于是 M1 , {v4v3v4 , v5v3v1v5 , v5v3v2v1v5 , v5v4v3v1v5 , v5v4v3v2v1v5}? {v8v10v12v11v8 , v8v10v12v9v11v8} 计算边界节点间通路: 在 Es (1) 基础上依次收缩节点 v1, v2 , v3 得矩阵: , v4vv4 v4v1v5 , v4v3v1v5 , v4v3v2v1v5 , 3 ,v5v4 , v5v3v4 v5v3v1v5 , v5v3v2v1v5 , v5v4v1v5 , v5v4v3v1v5 , v5v4v3v2v1v5 , , , 得Vs 边界节点 v4 , v5 间通路 Path(v4v5 ) , v4v1v5 , v4v3v1v5 , v4v3v2v1v5 Path(v5v4 ) , v5v4 , v5v3v4 在 Et (1) 基础上分别收缩节点 v9 , v10 , v11, v12 得: 0 , 0 0 , , , 0 0 v7v6 , , v8v10v12v7 , v8v10v12v9v7 v8v10v12v11v8 , v8v10v12v9v11v8 , ,v8v10v12vv6 , 9 , 计算 v6 , v7 , v8 间通路 收缩节点 v6 ，得 Path(v8v7 ) , {v8v10v12v7 , v8v10v12v9v7} 收缩节点 v7 ，得 Path(v8v6 ) , {v8v10v12v9v6 , v8v10v12v7v6 , v8v10v12v9v7v6} 收缩节点 v8 ，得 Path(v7v6 ) , v7v6 计算割集关联环路 A , {v4v7 , v4v8}, B , {v7v5 , v6v5} -4- 中国科技论文在线 M 2 , A B , {v4v7v5 , v4v7 v6v5 , v4v8 v7v5 , v4v8 v6v5} v4v7v5 , v4v7v5{v5v4 , v5v3v4} , {v4v7v5v4 , v4v7v5v3v4} v4v7 v6v5 , v4v7v6v5{v5v4 , v5v3v4} , {v4v7v6v5v4 , v4v7v6v5v3v4} v4v8 v7v5 , v4v8{v8v10v12v7 , v8v10v12v9v7}v7v5 , {v4v8v10v12v7v5 , v4v8v10v12v9v7v5}{v5v4 , v5v3v4} v4v8v10v12v7v5v4 , v4v8v10v12v7v5v3v4 , v4v8v10v12v9v7v5v4 , v4v8v10v12v9v7v5v3v4} , { v4v8 v6v5 , {v4v8v10v12v9v6v5 , v4v8v10v12v7v6v5 , v4v8v10v12v9v7v6v5}{v5v4 , v5v3v4} , {v4v8v10v12v9v6v5v4 , v4v8v10v12v9v6v5v3v4 , v4v8v10v12vvvv4 , 7 6 5 v4v8v10v12v7v6v5v3v4 , v4v8v10v12v9v7v6v5v4 , v4v8v10v12v9v7v6v5v3v4} 由步骤 2 查找 v7v6 , v5v4 , v8v7 , v8v6 间路径，得 Path(v7v6 ) , {v7v6} Path(v5v4 ) , {v5v4 , v5v3v4} Path(v8v7 ) , {v8v10v12v7 , v8v10v12v9v7} Path(v8v6 ) , {v8v10v12v9v6 , v8v10v12v7v6 , v8v10v12v9v7v6} 带入 A B 得 M 2 , {v4v7v5{v5v4 , v5v3v4}, v4v7v6v5{v5v4 , v5v3v4}, v4v8{v8v10v12v7 , v8v10v12v9v7}v7v5{v5v4 , v5v3v4}, v4v8{v8v10v12v9v6 , v8v10v12v7v6 , v8v10v12v9v7v6}v6v5{v5v4 , v5v3v4}} , {{v4v7v5v4 , v4v7v5v3v4},{v4v7v6v5v4 , v4v7v6v5v3v4}, {v4v8v10v12v7v5v4 , v4v8v10v12v7v5v3v4 , v4v8v10v12v9v7v5v4 , v4v8v10v12v9v7v5v3v4}, {v4v8v10v12v9v6v5v4 , v4v8v10v12v9v6v5v4 , v4v8v10v12v7v6v5v4 , v4vv10v12vv6v5v3v4 , v4v8v10v12v9v7v6v5v4 , v4v8v10v12v9v7v6v5v3v4}} 8 7 得所有环路: M , M 1 ? M 2 , {v4v3v4 , v4v7v5v4 , v4v7v5v3v4 , v4v7v6v5v4 , v4v7v6v5v3v4 , v4v8v10v12v7v5v4 , v4v8v10v12v7v5v3v4 , v4v8v10v12v7v6v5v4 , v4v8v10v12v7v6v5v3v4 , v4v8v10v12v9v6v5v4 , v4v8v10v12v9v6v5v3v4 , v4v8v10v12v9v7v5v4 , v4v8v10v12vvvvv4 9 7 5 3 v4v8v10v12v9v7v6v5v4 , v4v8v10v12v9v7v6v5v3v4 , v5v3v1v5 , v5v3v2v1v5 , v5v4v3v1v5 , v5v4v3v2v1v5 v8v10v12v11v8 , v8v10v12v9v11v8} 4 结论 算法运用子图的概念对网络进行分治，将求解图中所有节点间通路的计算减少为只计算 割集中边所对应节点的通路，并继承文献[1]中算法的优点，利用收缩节点的方法计算特定 节点间路径。算法思路清晰，原理简单。 -5- 中国科技论文在线 [参考文献] (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 -6-