基于顶点粒的强连通分量挖掘算法

强连通分量问题的实质是将有向图分解为一组互不相交的极大强连通子图.每个子图中的任一顶点到其它顶点都是可达的,既是其它顶点的祖先,又是后代.利用宽度优先搜索(BFS)可得到目标有向图中任一顶点的祖先顶点集与后代顶点集,两个集合的交集即为包含当前顶点的强连通分量.首先,基于BFS的强连通分量挖掘方法(BSCC)的效率取决于BFS被调用次数,因此,引入了3种启发式信息来减少BFS调用次数.对强连通分量进行深入分析,发现了顶点间的两种相关性.满足任一相关性的两个顶点不会分属两个有价值强连通分量.根据这两种相关性提出了一种顶点粒化策略,可构建每个顶点所对应的顶点粒,继而提出了基于顶点粒的强连通分量挖掘算法(GSCC),优化了BSCC算法中顶点调用BFS的方式,提高了强连通分量挖掘效率.实验结果表明,相比BSCC算法和线性复杂度的Tarjan算法,GSCC算法具有更好的性能.

星图的强连通度

大量数据的处理和复杂问题的解决对多处理器系统的性能要求越来越高,许多多处理器系统都将 互连网络作为底层拓扑结构。 互连网络决定了多处理器系统的性能,在处理器和它们之间通信链 路可能发生故障的系统中,考虑网络的容错性是非常重要的。 传统的点连通性只针对处理器故障, 边连接性只针对通信链路故障的问题。 在此背景下,提出了网络的强连通性,它允许处理器和通 信链路同时故障。 在互连网络的设计中,最基本的考虑因素之一是网络的连通性。 n维星图Sn作为 互连网络的一种有利的拓扑结构,具有许多优良的性质。 因此我们给出了Sn的强连通性以及强自 然连通性。

极小强连通块的平均连通度

令D=(V(D),A(D))是一个n阶有向图.如果有向图D是强连通的并且它的底图没有割点,那么称D是一个强连通块.如果D是一个强连通块,但对于任意的a 2A(D),都有D−a不是一个强连通块,那么称D是一个极小强连通块.对于任意两个点u,v∈V(D),κD(u,v)表示从u到v的局部连通度,是D中内部不交的(u,v)-有向路的最大条数.D的平均连通度定义为¯κ(D)=1 n(n−1)[∑(u,v)∈V(D)×V(D)κD(u,v)].借助度序列和耳朵分解的方法,给出了给定阶数的极小强连通块平均连通度的上界,并且猜测其严格小于3/2.

R-强连通和局部R-强连通的一些性质

连通性是拓扑空间的基本性质,R-强连通性比连通性要强,它具有一些良好的性质。利用乘积空间与和空间研究了R-强连通空间以及局部R-强连通空间,得到了乘积空间sεsⅡX_s是R-强连通空间与和空间aεAX_a是局部R-强连通空间的充分必要条件。

强连通空间和局部强连通空间的一些补充性质

文章补充了强连通空间和局部强连通空间的一些基本性质并证明了局部强连通空间和连续映射构成的范畴LSCon是topological construct.

有向图的强连通性分析及判别算法

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

L-fuzzy拓扑空间中的强连通性

在L-fuzzy拓扑空间中引入了强连通的概念,证明了强连通的一些基本性质,并研究了强连通分支和乘积拓扑空间的强连通性,得到了一些好的结果.

局部R-强连通性

Levine在 [1]中给出了L -强连通性 ,作者给出了条件较弱的R -强连通性 .本文主要是利用R -强连通性来研究局部R

拓扑空间中的R强连通

Ｌｅｖｉｎｅ 在［１］ 中给出了Ｌ 强连通。Ｌ强连通比一般的连通要强。Ｒ 强连通是介于Ｌ 强连通和连通之间的一种连通，它具有一些良好的性质。

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

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

环网的强连通度与最佳强连通性

本文得到了环网Ｄ（ｎ；ｓ）（ｓ＝（ｓ１，Ｓ２，．．．，ｓｍ｝）的强连通度的求法及构造强连通度Ｋ（Ｄ）≥ω（≤ｍ）的环网Ｄ（ｎ；ｓ）的方法。

有向循环图的强连通分支数以及强连通度的界

本文应用代数方法，讨论了有向循环图的强连通分支数的几种表达，以及强连通的有向循环图的强连通度的界。

时延和能耗均衡的强连通支配集构造算法

针对无线传感器网络中链路的非对称性,提出时延约束的强连通支配树(SDTT,strongly connected dominating tree with bounded transmission delay)问题,给出在有向图上构建传输时延和能量消耗均衡的强连通支配集的强连通支配树(SCDT,distributed strongly connected dominating tree)算法。首先在单位圆图(UDG)模型的基础上构建极大独立集(MIS),然后在具有双向权值的有向图上基于最小支撑树和最短路径树实现分布式SCDT算法,同时满足时延和能耗均衡的约束条件要求。理论算例分析和仿真结果表明提出的算法能有效地解决SDTT问题,构造联合约束的强连通支配集,形成时延和能耗均衡的虚拟骨干。

极小强连通本原有向图的本原指数集

本文的主要结果为:(1)当一个n阶极小强连通本原有向图至少含三个不同圈长时,有γ(D)≤[1/2(n^2-6n+14)](当n≥14时)。(2)e(n)≥[1/2(n^2-6n+16)],即从6到[1/2(n^2-6n+14)]的所有正整数都是某个n阶极小强连通本原有向图的本原指数。(3)给出了n阶极小强连通本原有向图的本原指数集NE_n的明确表达式。

一种强连通判定算法

提出一种新的强连通判定算法,使得在判定过程中的两次搜索可同时进行,便于并行运算。

二部竞赛图强连通的条件及其应用

对二部竞赛图的一个结论进行了改进 ,获得了二部竞赛图强连通的充要条件 ,并且研究了一类包含最小数目强连通

关于循环有向图的强连通度

本文定义的循环有向图D(n;S)在分布式环形计算机互连网络设计中被广泛运用。本文证明了D(n;S)的强连通度k>2/3|S|。

模糊自动机的强连通性及群自动机

为了更好地研究模糊自动机的结构和性质,采用代数的方法,在传统的模糊有限状态自动机的基础上,通过定义状态集合为代数群的自动机,讨论了这一类自动机的连通性和正则性,这丰富了模糊自动机理论.

一类有向支撑树与有向图的强连通性

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

有向循环图强连通度的下界

为简便计,本文采用文[1]中的定义和符号,而未说明的概念或符号引自[3].本文仅讨论有限、简单有向图. 有向图D=(V,A)称为强连通的,如果对D的任两顶点u与v,在D中同时存在(u,v)—有向路和(v,u)—有向路,C(?)V称为D的点割集,如果D—C非强连通或是单点.D的所含点数最少的点割集称为最小点割集,其阶数定义为D的强连通度,记为k(D)或k. 循环有向图D(n,S)