边故障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.

点故障3-ary n立方体中两条无故障点不交路

研究了含有故障点的Q3n中两条顶点不交的无故障路问题,得到以下结论:当n≥2,设FV(Q3n),若|F|≤2n-4,令x1,y1,x2,y2是Q3n-F中任意四个顶点,则在Q3n-F中存在两条顶点不交的路P1和P2,使得V(P1)∪V(P2)=V(Q3n-F),这里P1连接x1和y1,P2连接x2和y2.

K_n-e图中的路因子

G是一个Kn-e图,e∈E(Kn),设σ2(G)表示不相邻顶点度和的最小值.令|V(G)|=n=Σi=1kai,并且σ2(G)≥n+k-1.证明对于图G中任意的k个顶点v1,v2,…vk,存在点不相交的路P1,P2,…Pk,使得对于1≤i≤k,都有|V(Pi)|=ai,并且vi是Pi的一个端点.

2-连通图中点不交路的划分问题

给定一个阶为n的2-连通图G=(V;E)及一个正整数k,考虑在邻域并条件下G被分成k条点不交路的问题,得到下面的结果,对G中任何四个独立点x1,x2,y1,y2∈V,满足|NG(x1)∪NG(x2)|+|NG(y1)∪NG(y2)|n-k,则G能被分划分k条点不交的路.

K_n-M图中的路因子

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

5元n立方体中指定三条点不交覆盖路

k元n立方体被视为将来候选网络结构之一,它有很多优良性质和参数,被用作度量路由选择,能直接影响网络通信的稳定性和传输时效.本文研究了5元n立方体中一对三条点不交覆盖路问题,运用数学归纳法可得,当n≥2时,在Q_(n)^(5)中任意取四个顶点x,y_(1),y_(2),y_(3),则在Q_(n)^(5)中存在三条内部顶点不交的覆盖路P1=(x,…,y_(1)),P2=(x,…,y_(2)),P3=(x,…,y_(3)).

点故障增广立方体中2条点不交覆盖路

大型互联网系统在运行中某些元件或连线发生故障难以避免,故障的发生对网络的稳定性和数据传输时效性会产生影响.因此,研究网络容错性的参数尤为重要.研究了增广立方体在点容错条件下嵌入2条无故障点不交路覆盖问题.运用假设归纳法得到:当n≥4,增广立方体AQ_(n)中的点故障集F满足|F|≤2n-8时,若在AQ-F中任取个顶点x_(0),x_(1),y_(0),y_(1),则在AQ_(n)-F中存在2条内部点不交路P0=(x_(0),…y_(0)),P1=(x_(1),…y_(1)),使得V(P_(0))∪V(P_(1))=V(AQ_(n)-F).

边故障超立方体中两条无故障点不交路

文中用归纳假设法证明了结论:当n≥3时,令超立方体中的边故障集∣F∣≤n-3,设x1,x2,y1,y2是Qn中4个顶点,使得距离d(x1,y1)和距离d(x2,y2)都是奇数,则在Qn-F中存在两条路P1和P2,使得V(P1)∩V(P2)=φ,V(P1)∪V(P2)=V(Qn),这里P1连接x1和y1,P2连接x 2和y 2,而且边故障集∣F∣=n-3(n≥3)是最佳上界.

交叉立方体内顶点不交叉路径长度的研究

Efe提出的交叉立方体(crossedcube)是超立方体(hypercube)的一种变型,其某些性质优于超立方体,比如其直径几乎是超立方体的一半.在高性能的并行计算机系统中,信息是通过若干条结点互不交叉的路径并行传输,并且网络中的结点和链路出错是不可避免的,因此这些路径的长度将直接影响并行计算的性能.本文对交叉立方体的内顶点互不交叉路径进行了研究,证明了以下结论:在n维交叉立方体CQn中任意两顶点u,v间存在n条内顶点互不交叉的路径,使得(1)最短路的长度=u和v之间的距离,(2)所有路中的最长路径长度≤u和v的距离+4.这说明交叉立方体互连网络具有很好的并行通信性能和容错性能.

边故障增广立方体中两条无故障点不交路

文中研究了增广立方体两条点不交路问题,用归纳假设法证明了结论:当n≥3时,令增广立方体A_n中的边故障集|F|_2n-6,设x_0,x_1,y_0,y_1是A_n中任意4个顶点,则在A_n-F中有两条点不交路P_0和P_1,使得V(P_0)∪V(P_1)=V(A_n),其中P_0连接x_0和y_0,P_1连接x_1和y_1.

增广立方体中的一对三条点不交路

文中采用数学归纳法证明了增广立方体中存在一对三条点内部不交路的多路问题,获得了以下成果:当n≥2时,在增广立方体AQn中随意取4个端点x,y1,y2,y3,则在增广立方体AQn中有三条内部不相交路P1,P2,P3,使得V(P1)∪V(P2)∪V(P3)=V(AQn),这里P1连接x和y1,P2连接x和y2,P3连接x和y3.

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

针对边故障Q3n中一对二点不交路覆盖的问题,利用归纳假设法得到结论:当n2,边故障|F|≤2n-3时,在Q3n中任取3个顶点x0,y1,y2,则在Q3n-F中有两条内部不交路P1,P2,使得V(P1)∪V(P2)=V(Q3n),这里P1连接x0和y1,P2连接x0和y2,而且边故障|F|≤2n-3为最优上界.

边容错3元n立方体的两条等长不交覆盖路

研究了在边故障条件下3元n立方体中两条等长不交覆盖路问题.利用数学归纳法得到以下结论:当n≥2,边故障集|F|≤n-2时,在Q_(n)^(3)中任意三个顶点x,y_(1),y_(2),则在Q_(n)^(3)-F中存在两条内部顶点不交的等长覆盖路P_(1)=(x,…y_(1_)和P_(2)=(x,…y_(2)).

独立路径问题的算法设计

根据网络中可供选择的路由数目,提出独立路径的一个新问题,即求网络中最多同时存在多少条相互独立的路径。同时,针对选择最优路由,研究求权值和最小的K(K>1,K为整数)条独立路径的问题,发现和证明独立路径与网络流的关系,并采用网络流方法设计简单算法。应用结果表明,该算法的复杂度较小,可用于解决网络通信中的多径路由问题。

度和与图中具有给定阶数的点不交的路(英文)

设G是一个n阶图,n=∑i=1kni,其中,ni≥2(i=1,2,…,k)是整数.我们利用 度和给出图G中存在n1,n2,…,nk阶点不交路的充分条件.

边故障超方中距离为偶长的两条顶点不交无故障路

本文得到如下结果:当n≥4时,超立方体Qn中的边故障集F≤n-3,设x1,y1,x 2,y 2是Qn中任意四个顶点,使得x1和y1属于Qn的一部,x2和y2属于Qn的另一部,则在Qn-F中存在两条顶点不交路P1和P2,这里P1连接x1和y1,P2连接x 2和y2,且V(P1)∪V(P2)=V(Qn),且故障边数n-3是紧的.

mP_n的顶点被多重色集合可区别的一般边染色

简单图G的一个一般边染色是指若干种颜色关于图G的所有边的一个分配,不要求相邻的边被分配不同的颜色。设f是G的使用了k种颜色的一般边染色,若对u,v∈V(G),u≠v,都有与u关联的边的颜色构成的多重集合异于与v关联的边的颜色构成的多重集合,那么称f是使用了k种颜色的顶点被多重色集合可区别的一般边染色。对G进行顶点被多重色集合可区别的一般边染色所需的颜色的最少数目记为c(G),并且称c(G)为图G的顶点被多重色集合可区别的一般边色数。讨论了m个Pn的点不交的并m Pn的顶点被多重色集合可区别的一般边色数。