| 基于核的有向强连通图计算机随机生成算法 |
| |
| 引用本文： | 顾滨兵,孙吉贵,杨焕,田地.基于核的有向强连通图计算机随机生成算法[J].吉林大学学报(信息科学版),2006,24(5):507-511. |
| |
| 作者姓名： | 顾滨兵 孙吉贵 杨焕 田地 |
| |
| 作者单位： | 吉林大学计算机科学与技术学院,长春,130012;吉林大学符号计算与知识工程教育部重点实验室,长春,130012;吉林大学计算机科学与技术学院,长春,130012;吉林大学符号计算与知识工程教育部重点实验室,长春,130012;吉林大学计算机科学与技术学院,长春,130012;吉林大学符号计算与知识工程教育部重点实验室,长春,130012;吉林大学计算机科学与技术学院,长春,130012;吉林大学符号计算与知识工程教育部重点实验室,长春,130012 |
| |
| 基金项目： | 国家自然科学基金资助项目(60473003)，吉林省科技发展计划基金资助项目(20040526) |
| |
| 摘 要： | 针对图论算法研究和算法测试对随机生成有向强连通图的需求,在深入研究有向强连通图和极小有向强连通图的结构组成的基础上,提出了有向强连通图核的概念。参考有向连通图的随机生成算法,给出了一种有向强连通图的随机生成算法,并对该算法进行了测试。对具有上千个节点及上万条弧的强连通图的随机生成,采用该算法时间都在1 s以内,生成的结果能很好地应用于图论研究,以作为图论算法的随机测试用例。
|
| 关 键 词： | 有向连通图 有向强连通图 有向强连通图的核 基础环 有向连通分支 |
| 文章编号： | 1671-5896(2006)05-0507-05 |
| 修稿时间： | 2005年12月15日 |
New Algorithm for Generating Strongly Connected Graphs |
| |
| GU Bin-bing,SUN Ji-gui,YANG Huan,TIAN Di.New Algorithm for Generating Strongly Connected Graphs[J].Journal of Jilin University:Information Sci Ed,2006,24(5):507-511. |
| |
| Authors: | GU Bin-bing SUN Ji-gui YANG Huan TIAN Di |
| |
| Abstract: | Aiming at demands of generating strongly connected graphs in lots of algorithms research and algorithms test of graph theory,we bring forward a new algorithm.The Article analyse the structure of strongly connected graph and mi nimal strongly connected graph,and bring forward a new concept of the kernal of strongly connected graph.After the algorithm is putted forward basing on the a lgorithm for generating directed connected graphs,it is tested.It has high eff iciency,and a strongly connected graph with thousands nodes and ten thousands e dges can be generated by this algorithm in one second.Those random strongly con nected graphs generated by this algorithm are best applied in graph theory resea rch and algorithms test. |
| |
| Keywords: | directed connected graph strongly connected graph kernel of strongly connected graph basic loop directed connected branch |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
