具有点故障的超方体中经过指定路的无故障圈

本文研究了在含有故障点的维超立方体Qn中通过给定路的无故障圈问题,本文得到以下结果:设n≥3,2≤h相似文献   

点和边容错超立方体中经过指定边的无故障哈密尔圈

用归纳法证明了:当n≥3时,令F_v和F_e分别为故障点集和故障边集,记F=F_v+F_e,E_0是线性森林,若E_0E(Q_n)F_e,1≤|E_0|≤n-2,|F|n-([|E_0|/2]+1),则Q_n-F_v-F_e中有长2~n-2|F_v|的圈包含E_0.     

边故障5元n立方体的两条不交覆盖路

研究具有故障边的5元n立方体的两条不交路覆盖问题。用归纳假设法证明了:若Q5n的边故障集F中至多有2n-4条边,对于Q5n中任意四个顶点a,b,c,d,则Q5n-F存在两条顶点不交的覆盖路P1和P2,这里P1连接a和b,P2连接c和d.     

边故障3元n立方体中的一对二点不交路覆盖①

针对边故障Q■中一对二点不交路覆盖的问题,利用归纳假设法得到结论:当n≥2,边故障■时,在Q■中任取3个顶点x_0,y_1,y_2,则在Q■-F中有两条内部不交路P_1,P_2,使得V(P_1)∪V(P_2)=V(Q■),这里P_1连接x_0和y_1,P_2连接x_0和y_2,而且边故障■为最优上界.     

简单图中哈密尔顿圈的个数

给出了计算简单图中哈密尔顿圈个数的几个公式,并对简单图中哈密尔顿圈个数的上下界进行了讨论。     

赋权图过指定点的圈

设G是满足条件D1和D2的2-连通非Hamilton赋权图,证明了如下新结果：若G满足dw（x）＋dw（y）≥m（xy不属于E（G）,x≠y）,则通过图G的每个顶点存在权重大于或等于m的圈.该结果推广了非赋权图的已有结果.     

含有故障点的4元n方体中无故障路的嵌入

k元n方体是传输信息的一种重要网络.本文研究含有故障点的4元n方体,证明了当其故障点数f（≤n-1）时,对每个奇数l∈{2n-1,2n-3,…,4n-2f-1},任意两个相邻的非故障两点之间存在长度为l的无故障路.     

超立方体中过k个指定点的最短路径

利用超立方体的拓扑结构,基于其内部节点编码的特点,分析研究得到在n维超立方体Qn中任意两节点s、t之间经过k(kn)个指定点的最短路径算法.该算法共包括了十个步骤,在最坏的情况下执行2n~2+2n(n~2+2)次运算,算法的时间复杂度为O(n~3),属于多项式计算.     

容错变形超立方体的圈和路（英文）

考虑包含故障边的n(n≥3)维变形超立方体VQn,证明了:如果故障边数不超过n-2,那么VQn包含非故障边的Hamilton圈;如果故障边数不超过n-3,那么对任何两个不同顶点x和y,VQn包含非故障边的xy-Hamilton路.该证明方法采用归纳法.     

变形超立方体的圈和路嵌入(英文)

作为超立方体网络Qn的变形,n维变形超立方体VQn具有许多优于超立方体所具有的性质.这里证明了对任何整数l∈[4,2n],VQn中每条边被包含在长度为l的圈中除非l=5;对任何顶点对(x,y)和整数l∈[d,2n-1],其中,d为这两点之间的距离,VQn中存在长度为l的xy路除非当d=1时l=2,4.     

故障3-元n-立方体的哈密顿圈嵌入

哈密顿圈嵌入问题是研究互连网络并行计算中最重要问题之一.在文章中,我们考虑带故障点的3-元n-立方网络Qn3的哈密顿圈嵌入问题并得到如下结果.给定一个具有至多2n-2个故障点的集合F,对Qn3-F中任意边,除一种特殊情况外,Qn3-F中都有一个哈密顿圈包含这条边,即Qn3-F是几乎-边哈密顿的.     

边故障3-aryn立方体中两条无故障点不交路

文中用归纳假设法证明了结论:当n≥2,FE(Qn3),∣F∣≤2 n-4,令x1,y1,x2,y 2是Qn 3中任意四个顶点,则在Qn 3-F中存在两条顶点不交的路P1和P2,使得V(P1)∪V(P2)=V(Q n3),这里P1连接x1和y1,P 2连接x 2和y 2.     

k-连通图中存在哈密尔顿圈的一个隐度条件

文中给出了强基本独立集的概念,并证明了如下定理:设G是一个具有n个顶点的k-连通图,其中k≥2.如果对任意一个具有k个顶点的强基本独立集S,都有max{d1(x)|x∈S}≥n/2,则G是哈密尔顿图.此定理推广了已有的几个有关图中哈密尔顿圈存在性的定理.     

图中具有指定性质的独立4-圈

主要给出了图G恰好含有s个K3和k-s个K4的最小度条件即:设G是一个简单图,s,k是两个正整数且s k,其中G的顶点个数n≥3s+4(k-s)+3,如果G中任意两个不相邻顶点的最小度之和σ2(G)≥4n-3s-8/|2|或者最小度δ(G)≥3n+2k-s-2/4,则G包含k个顶点不相交的圈C1,C2…Ck,并且Ci=K3其中1≤i≤s,Cj=K4其中sj≤k.     

条件故障下3-元n-立方体的容错分析

研究了条件边故障下3-元n-立方体中较大连通分支点的数目,进而证明了3-元n-立方体是(4n－6)-条件边故障强Menger边连通的。最后通过一个反例说明该结果是最优的。     

n维超立方体Q_n中边不交的生成树

边不交生成树的研究在互连网络并行广播通讯中具有重要的理论意义和应用价值。设Γ(Qn)为超立方体Qn中以vo为根节点的全体边不交生成树的集合,本文主要讨论|Γ(Qn)|的上界和下界,得到下列结果:(1)|Γ(Qn)|≤n·2n-12n-1,(2)当n≥4时,|Γ(Qn)|≥2。这些结果为设计超立方体互连网络中并行广播路由算法提供了理论依据。     

无指定相交圈的非负特征图的列表点荫度

对于图的任一顶点集的划分,并使每个划分的导出子图均为无圈图的最小的划分基数称为图的顶点荫度.对于图G的每个顶点给定一个列表基数至少为k的颜色集合,对于图的任一染色,若每个顶点的颜色均选择与其关联的颜色集,使得每种颜色类的导出子图是一个无圈图的最小的基数k称为图的列表点荫度.证明了每个无6圈和相交i,j-圈(i,j∈{3,4})的非负特征图的列表顶点荫度为2,即为4列表可选色.     

无爪图中具有指定长度的路因子

在无爪图G中,设σ2(G)表示不相邻顶点度和的最小值. 令|V(G)|=n=∑ki=1ai,ai6,1ik,并且σ2(G)n+k-1,证明了对于图G中任意的k个顶点v1,v2,…vk, 都存在点不相交的路P1,P2,…Pk,使得对于1ik,都有|V(Pi)|=ai并且vi是路Pi的一个端点.     

k-连通无爪图中存在哈密尔顿圈的一个隐度条件

文中给出了强基本独立集的概念,并证明了如下定理:设G是一个具有n个顶点的k-连通无爪图,其中k≥2.如果对任意一个具有k个顶点的强基本独立集S,都有max{d2(x)|x∈S}≥n 2,则G是哈密尔顿图.此定理在无爪图的条件下推广了已有的几个有关图中哈密尔顿圈存在性的定理.     

二部图中含指定顶点的独立4-圈

G的一个子图集合称为相互独立的或顶点不相交的,如果它们中的任何两个子图在G中没有公共顶点。对于二部图,给出了k个含指定顶点的独立4-圈的最小度条件。