2-Hamming图的强Menger边连通容错性

设G是连通图.若G的任一对顶点u,v之间有min{d(u),d(v)}条边不交的路,则称连通图G为强Menger边连通的.设G是强Menger边连通图,m是非负整数,若对任意满足|F|≤m的边子集F,G-F都是强Menger边连通图,则称G是m-边容错强Menger边连通图.证明了2-Hamming图H(n,k,2)是(4n-2)-边容错强Menger边连通的,其中n≥2,k≥5.

轮图的边容错强Menger边连通性

连通性是评估互连网络可靠度和容错性的一个非常重要的参数。若对于连通图G中的任意两个顶点x,y,它们之间有min{degG(x),degG(y)}条边不相交的路,则连通图G是强Menger边连通的。若对于任意的边集Fe⊆E(G)且▏Fe▏≤m,G-Fe仍保持强Menger边连通性,则图G是m-边容错强Menger边连通的。若对于任意的边集Fe⊆E(G)且▏Fe▏≤m和δ(G-Fe)≥2,G-Fe仍保持强Menger边连通性,则图G是m-条件边容错强Menger边连通的。在这篇文章中,我们证明CWn(n≥4)是(2n-4)-边容错强Menger边连通的。此外,我们给出例子来说明我们保持强Menger边连通性的有关故障边的数量是最大值,即是最优的。

条件故障下k-元n-立方体的强Menger边连通度

为了更好地度量网络的容错性,运用数学归纳法和反证法,讨论了条件故障下k-元n-立方体的强Menger边连通度问题。证明了当k≥4,n≥2时,k-元n-立方体是(6n-8)-条件边故障容错强Menger边连通的;当k=3,n≥2时,3-元n-立方体是(4n-6)-条件边故障容错强Menger边连通的。最后举了一个反例证明该结论是最优的。通过对这个问题的讨论和证明,可以补充Qiao等关于超立方体(2-元n-立方体)的条件容错强Menger边连通度的结果,同时进一步改进了翟登鑫对这个问题的研究结果。

k元n立方体的条件容错强Menger边连通性

研究了k元n立方体的强Menger边连通度,并证明了k元n立方体Q■(n≥2,k≥3)是3n-3条件容错强Menger边连通的.

基于强乘积运算下图的广义和连通度指标上下界

对于图G,令E(G)表示G的边集,令V(G)表示G的点集,d_(G)(v)表示v的度。对于边e=uv,定义广义和连通度指标χ_(α)(e)=(d_(G)(u)+d_(G)(v))^(α),其中α为任一实数。本文先介绍了图的S,R,Q,T四种运算,然后给出了四种运算下的强乘积,并利用最大度最小度确定了其四种图的广义和连通度指标的上下界。

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

强连通分量问题的实质是将有向图分解为一组互不相交的极大强连通子图.每个子图中的任一顶点到其它顶点都是可达的,既是其它顶点的祖先,又是后代.利用宽度优先搜索(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.

条件容错的平衡超立方体的强Menger连通性

平衡超立方体是计算机系统里常用的一个拓扑结构。本文证明了:当n≥4时,至多有2n-2个容错点集F的n维平衡超立方体BH n是强Menger连通的;当n≥2时,至多有2n-4(2n-2)个容错点集(边集)F的n维平衡超立方体BHn是条件容错的强Menger连通(边连通)的。

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

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

强乘积图的连通度和边连通度(英文)

研究了两个图G1和G2的强乘积图G1■G2的连通度和边连通度.这里证明了λ(G1■G2)=min{λ1(n2+2m2),λ2(n1+2m1),δ1+δ2+δ1δ2},如果G1和G2都是连通的;还证明了κ(G1■G2)=min{δ1n2,δ2n1,δ1+δ2+δ1δ2},如果G1和G2都是极大连通的.其中,ni,mi,λi和δi分别表示Gi(i=1,2)的阶数、边数、边连通度和最小度.

强乘积图的连通度(英文)

用iκ>0和iδ表示图Gi(i=1,2)的连通度和最小度,给出了无向图强乘积的连通度一个下界:κ(G1G2)≥min{1κ(1+2δ),2κ(1+1δ)}.

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

针对无线传感器网络中链路的非对称性,提出时延约束的强连通支配树(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的明确表达式。

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

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

弧连通锥凸向量优化问题强有效解的最优性条件

当目标函数和约束函数都是弧连通锥凸时,借助方向导数,利用择一性定理给出了约束向量优化问题取得强有效解的必要条件。利用强有效点的标量化定理给出了向量优化问题取得强有效解的Kuhn-Tucker最优性充分条件。

一种强连通判定算法

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

对称强向量拟均衡问题解集的稳定性及本质连通区的存在性

研究对称强向量拟均衡问题解集的稳定性。在约束集值映射满足一定连续性与目标映射是锥-真拟凸的条件下证明了对称强向量拟均衡问题构成的空间M中,大多数(在Baire分类意义下)对称强向量拟均衡问题的解集是稳定的,并证明了M中的每个对称强向量拟均衡问题的解集至少存在一个本质连通区。

局部R-强连通性

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

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

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