您的位置：首页 > 论文页面
生成有向图中全部初级有向回路的扩展
发表时间：2012-01-15 浏览量：2327 下载量：990
| 全部作者： | 夏济仁，张杰 |
| 作者单位： | 北京邮电大学信息光子学与光通信研究院 |
| 摘 要： | 对生成有向图中全部简单回路的算法进行扩展。采用分治法对图划分子图，再对子图中顶点进行收缩，求出部分节点间的通路，利用割集中若存在回路，则割集中必有方向不同的边的性质，将子图合并，求出有向图中所有回路。 |
| 关 键 词： | 图论；有向图；简单有向回路；L-邻接矩阵 |
| Title： | An extension of finding all elementary circuits in a directed graph |
| Author： | XIA Jiren, ZHANG Jie |
| Organization： | Institute of Information Photonics and Optical Communications, Beijing University of Posts and Telecommunications |
| 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 excluding edge nodes, path 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： | graph theory; directed graph; elementary directed circuits; L-adjacent matrix |
| 发表期数： | 2012年1月第1期 |
| 引用格式： | 夏济仁，张杰. 生成有向图中全部初级有向回路的扩展[J]. 中国科技论文在线精品论文，2012，5（1）：1-5. |
0
评论数 0请您登录
暂无评论
下载全文
多维论文