基于核的有向强连通图计算机随机生成算法

1

作者 顾滨兵 孙吉贵 +1 位作者 杨焕 田地 《吉林大学学报（信息科学版）》 CAS 2006年第5期507-511,共5页

针对图论算法研究和算法测试对随机生成有向强连通图的需求,在深入研究有向强连通图和极小有向强连通图的结构组成的基础上,提出了有向强连通图核的概念。参考有向连通图的随机生成算法,给出了一种有向强连通图的随机生成算法,并对该算... 针对图论算法研究和算法测试对随机生成有向强连通图的需求,在深入研究有向强连通图和极小有向强连通图的结构组成的基础上,提出了有向强连通图核的概念。参考有向连通图的随机生成算法,给出了一种有向强连通图的随机生成算法,并对该算法进行了测试。对具有上千个节点及上万条弧的强连通图的随机生成,采用该算法时间都在1 s以内,生成的结果能很好地应用于图论研究,以作为图论算法的随机测试用例。 展开更多

关键词 有向连通图 有向强连通图 有向强连通图的核 基础环 有向连通分支

在线阅读 下载PDF 职称材料

强连通图与其支撑树的关系 被引量：3

2

作者 翟晓燕 《广州大学学报（社会科学版）》 1993年第2X期67-72,共6页

本文通过对强连通图与有向树关系的研究,给出了一组有关有向图强连通的充要条件及有趣的结论,并提出了在网络图中寻找具有某种特殊性质的最短支撑树的计算方法。

关键词 有向图 支撑树 强连通图 充要条件 网络图 有向树 计算方法 结点 出树 必要性

在线阅读 下载PDF 职称材料

强连通图和本原图的度序列的充要条件

3

作者 翁伟明 《广东技术师范学院学报》 2009年第6期12-13,共2页

本文通过度序列分别给出一个图是强连通图和本原图的充要条件。

关键词 度序列 强连通图 本原图

在线阅读 下载PDF 职称材料

有向图的强连通性分析及判别算法 被引量：7

4

作者 刘晓利 秦奋涛 《计算机应用与软件》 CSCD 北大核心 2005年第4期138-139,共2页

文中用可达矩阵分析了有向图的强连通性,并给出了一种判别有向图为强连通图的新方法。

关键词 强连通性 有向图 判别算法 矩阵分析 强连通图

在线阅读 下载PDF 职称材料

一类有向支撑树与有向图的强连通性 被引量：2

5

作者 翟晓燕 《西安电子科技大学学报》 EI CAS CSCD 北大核心 1996年第S1期38-42,共5页

通过对具有一个枢纽点的支撑树与有向图的强连通性关系的研究.给出了一系列有关的充要条件和结论,并给出了在有向图中寻找具有一个枢纽点支撑树的方法.

关键词 强连通图 支撑出树 支撑入树 以一点为枢纽点的支撑树

在线阅读 下载PDF 职称材料

强竞赛图的强连通性

6

作者 王琦 刘晓姗 赵红銮 《计算机工程与应用》 CSCD 北大核心 2007年第6期40-41,共2页

D=(V,A)为一个有向图,其中,V为顶点集,A为弧集,A中的元素是有序对(u,v),称为弧。设u和v是有向图D的两个顶点,若从u到v存在一条有向路,则称顶点v是从u可达的,或称从u可达v。若有向图D中任何两个顶点是互相可达的,则称D为强连通图。若有向... D=(V,A)为一个有向图,其中,V为顶点集,A为弧集,A中的元素是有序对(u,v),称为弧。设u和v是有向图D的两个顶点,若从u到v存在一条有向路,则称顶点v是从u可达的,或称从u可达v。若有向图D中任何两个顶点是互相可达的,则称D为强连通图。若有向图T中任意两个顶点之间恰有一条弧,则称T为竞赛图。一个强连通的竞赛图T称为强竞赛图。论文研究顶点个数大于的强竞赛图T的性质,并利用该性质给出了Moon定理的另外一种证明。 展开更多

关键词 有向图 强连通图 竞赛图

在线阅读 下载PDF 职称材料

含有两个非临界点的强连通定向图的弧数(英文)

7

作者 林上为 李春芳 王世英 《运筹学学报》 CSCD 2011年第3期57-61,共5页

证明顶点数为n≥4，弧数为m≥（n-1/）＋3的强连通定向图D中存在两点u^＊、u^＊，使得D—u^＊和D-^＊都是强连通的，并用例子说明这里所给的关于弧数的下界是紧的．

关键词 有向图 强连通子图 临界点

在线阅读 下载PDF 职称材料

强连通竞赛图的圈分解(英文)

8

作者 束金龙 李皓 《运筹学学报》 CSCD 北大核心 2004年第1期53-61,共9页

设T为n阶强连通竞赛图.本文通过详细刻画不能进行圈分解的强连通竞赛 图的特征,证明了满足maX{δ+,δ-}>5k-5和k>2的强连通竞赛图T,能够分解为k 个圈.

关键词 强连通竞赛图 圈分解 传递竞赛图 hamiltonian圈

在线阅读 下载PDF 职称材料

4-强连通竞赛图中外弧泛圈点的研究

9

作者 张新鸿 李瑞娟 《太原科技大学学报》 2008年第1期43-45,共3页

外弧泛圈点问题是图论研究中一个比较热门的问题,文章在某些限制条件下研究了4-强连通竞赛图的外弧泛圈点问题。文中使用路收缩等方法证明并给出了4-强连通竞赛图中存在3个外弧泛圈点的一个充分条件,而且给出了一些相关的结论。

关键词 4-强连通竞赛图 外孤泛圈点 外度 内度 路收缩

在线阅读 下载PDF 职称材料

有向图的增强——一个适合以问题求解为导向教学的例子 被引量：2

10

作者 李晓明 《计算机教育》 2019年第2期1-4,共4页

过去几年,在北大有一门通选课,叫'社会科学中的计算思维方法'。每次上课的时候,我总会给出一个小小的有向图的例子,让同学们观察,看最少添加几条边,可以让那个图变成强连通的,这个看起来像是一个趣味数学游戏的活动常常会引起... 过去几年,在北大有一门通选课,叫'社会科学中的计算思维方法'。每次上课的时候,我总会给出一个小小的有向图的例子,让同学们观察,看最少添加几条边,可以让那个图变成强连通的,这个看起来像是一个趣味数学游戏的活动常常会引起学生们的积极参与。由于例子很小,大家通常在两三分钟里就能给出正确的结果。然后,我就留下这个游戏推广到一般的问题让有兴趣的同学思考。 展开更多

关键词 有向图 强连通图 DAG 强连通分量 完全二部图 问题求解

在线阅读 下载PDF 职称材料

有向图的连通性与支撑树 被引量：3

11

作者 翟晓燕 《大学数学》 1996年第2期85-88,共4页

本文通过对有向图连通性的研究，在文章［１］的基础上进一步揭示了支撑树与单侧连通及弱连通图之间的关系，给出了一系列有关的结论，并将其归纳表示为图表的形式．

关键词 支撑树 有向图 连通性 竞赛图 强连通图 充要条 有向网络图 结点 知识工程 模糊系统

在线阅读 下载PDF 职称材料

强4-连通图的可收缩边

12

作者 董宁 莫芬梅 陈碧楠 《广西师范学院学报（自然科学版）》 2017年第4期30-35,共6页

该文主要研究强4—连通图G上的可去边的数目,证明了强4-连通图G的任何一个生成树T上至少有3条可收缩边.进一步证明了除了一个特殊图外强4-连通的任意最长圈C上至少有5条可收缩边.有例子表明该文的结果是最好可能的.

关键词 强4-连通图 生成树 最长圈 可收缩边

在线阅读 下载PDF 职称材料

基于强连通分量的个性化的网页排名高效算法 被引量：3

13

作者 杨红果 申德荣 +2 位作者 寇月 聂铁铮 于戈 《计算机学报》 EI CSCD 北大核心 2017年第3期584-600,共17页

个性化的网页排名(PPR)是一种常用的图结点排名方法.随着图的规模变得越来越大,如何快速地计算出PPR逐渐成为大家研究的关注热点.该文的最终目的即是为了提高PPR的计算效率.现有的各种优化算法可大体分为分布式算法和串行算法,其主要思... 个性化的网页排名(PPR)是一种常用的图结点排名方法.随着图的规模变得越来越大,如何快速地计算出PPR逐渐成为大家研究的关注热点.该文的最终目的即是为了提高PPR的计算效率.现有的各种优化算法可大体分为分布式算法和串行算法,其主要思路均是通过将大图上的计算分割到多个小子图上进行计算,但不同分块间的数据通信量往往很大而且通信次数频繁.该文提出的基于强连通分量的算法可有效解决此类问题.其主要计算过程为,首先快速将大量与计算无关的结点和边剪切掉,其次通过某种策略将在大图上的计算转化到多个强连通分量子图上计算,使得各分量子图之间的数据传递只需一次即可完成.该文基于强连通分量算法,不仅减少了分布式算法子图间的通信量,而且降低了串行算法的磁盘读写I/O频率,同时还保证了算法的准确度几乎不受损失.实验结果表明该文提出的算法可显著提高PPR的计算效率. 展开更多

关键词 个性化的网页排名 分布式算法 串行算法 强连通子图 通信量 I/O频率

在线阅读 下载PDF 职称材料

求强分图图的算法 被引量：1

14

作者 朱鳌鑫 《计算机工程与设计》 CSCD 北大核心 1997年第2期57-64,共8页

由于如文献［１］和［２］等的实际需要，对基于ＤＦＳ技术的求强分图算法进行扩充、改进，使之更完整。

关键词 图论 算法 强连通分图 深度优先搜索 向量化

在线阅读 下载PDF 职称材料

基于扩展ORD图的类间集成测试顺序改进算法 被引量：2

15

作者 高海昌 冯博琴 +1 位作者 李远杰 曾明 《小型微型计算机系统》 CSCD 北大核心 2007年第4期725-728,共4页

在UML类图的基础上,将传统对象关系图(ORD)模型进行了扩展,并对它们进行了形式化的定义.提出了一种基于扩展ORD图的类间集成测试顺序改进算法,通过递归调用改进的Kosaraj鉴别强连通分量的算法来确定SCCs.本算法与Tai和Traon的两种算法比... 在UML类图的基础上,将传统对象关系图(ORD)模型进行了扩展,并对它们进行了形式化的定义.提出了一种基于扩展ORD图的类间集成测试顺序改进算法,通过递归调用改进的Kosaraj鉴别强连通分量的算法来确定SCCs.本算法与Tai和Traon的两种算法比较,需要的测试桩最少,效率最高.理论分析和初步的实验证明这种方法是可行和有效的. 展开更多

关键词 面向对象测试 类间集成 对象关系图 强连通图 权重计算

在线阅读 下载PDF 职称材料

严格有向图Hamilton路的研究 被引量：2

16

作者 胡红萍 杨正民 王建中 《华北工学院学报》 2003年第4期248-252,共5页

　利用图论的基本方法及其思想,结合相关定义、定理提出了两个严格有向图含有向Hamilton路的两个充分条件,即D为具有n(≥2)个顶点的严格强连通有向图:1)如果对任意具有共同的内邻点或者具有共同的外邻点的非邻接顶点对{x,y},都有d(x)+d... 　利用图论的基本方法及其思想,结合相关定义、定理提出了两个严格有向图含有向Hamilton路的两个充分条件,即D为具有n(≥2)个顶点的严格强连通有向图:1)如果对任意具有共同的内邻点或者具有共同的外邻点的非邻接顶点对{x,y},都有d(x)+d(y)≥2n+1,且min{d+(x)+d-(y),d-(x)+d+(y)}=n-2,则有向图D含有向Hamilton路;2)如果对任意具有共同内邻点或者具有共同的外邻点的非邻接顶点对{x,y},都有d(x)+d(y)≥(5/2)n-5,则有向图D含有向Hamilton路. 展开更多

关键词 HAMILTON路 严格有向图 图论 强连通图

在线阅读 下载PDF 职称材料

围长为2的本原有向图的最小顶点指数集 被引量：3

17

作者 陈小亘 《中山大学学报（自然科学版）》 CAS CSCD 北大核心 2000年第5期114-116,共3页

研究一类本原有向图的最小顶点指数集 ,证明了n(≥ 3)阶围长为 2的本原有向图的最小顶点指数集En是 :若n是奇数 ,则En ={ 2 ,3,… ,2n - 3} ;若n是偶数 ,则En={ 2 ,3,… ,2n- 4 } .

关键词 围长 本原有向图 强连通图 最小项点指数集

在线阅读 下载PDF 职称材料

围长为2的n阶本原有向图的Lewin指数集

18

作者 庄晓琼 《海南大学学报（自然科学版）》 CAS 2003年第4期300-303,共4页

分析了围长为2的n阶本原有向图的l(G)的上界及相应的指数集,并讨论了极端情形.

关键词 本原有向图 Lewin指数 指数集 强连通图

在线阅读 下载PDF 职称材料

判断方阵可约性的图论方法

19

作者 付尚朴 《大理学院学报（综合版）》 CAS 2004年第3期83-84,共2页

关键词 方阵可约性 判定方法 图论 强连通图 回路

在线阅读 下载PDF 职称材料

特定的竞赛图是哈密顿图

20

作者 曾建初 《贵州大学学报（自然科学版）》 2004年第2期124-126,共3页

证明了命题“竞赛图D =(V ,E) ,顶点的个数 V =n为奇数 ,对 v∈V ,d+(v) =d-(v) =n - 12 竞赛图是哈密顿图。

关键词 竞赛图 双向(强)连通图 哈密顿图

在线阅读 下载PDF 职称材料