高珊

（湖北大学数学与统计学学院，湖北 武汉 430062）

图的很多参数，如连通度和直径，在图论和组合数学本身十分重要，而且由于与通信网络的容错性和传输延迟密切关联而被广泛研究.当前，随着超大规模集成电路技术和光纤材料科学的发展，针对大规模并行处理和图论算法的需要，一些学者致力于研究图的宽直径，力求设计出稀疏、均匀且具有尽可能小的直径和尽可能大的连通度的网络，以提高互连网络的可靠性、容错性，减小网络的通信延迟，并取得了一些较好的研究结果.笔者研究匹配组合网络G(G0,G1;M)的宽直径，并根据该网络的结构性质，用点不交的最短路径方法得到G(G0,G1;M)的宽直径的上界估计式.

1 定义及预备定理

采用Bondy和Murty[1]中的术语和记号，并且只考虑简单无向图.我们用G=(V,E)表示一个图，令u∈V(G)，NG(u)和dG(u)分别表示点u的邻域和度.图G中两点u和v的距离dG(u,v)，定义为G的最短(u,v)-路的长度，如果没有这样的路存在，则令dG(u,v)=∞.图G的直径d(G)定义为G中任意两点之间的最大距离.如果图G不是完全图Kn，那么G的连通度κ(G)定义为G中所有点分离集的最小顶点数，否则κ(Kn)=n-1.如果κ(G)≥k，那么G称为k-连通的.

若一个图G是k-连通的，则由Menger定理可知，对G中任何不同两顶点u和v，G中存在k条点不交的(u，v)-路.

令G为ω-连通的，且0＜k≤ω.图G的宽直径及相关的概念定义如下：

定义1[2]对G中任何不同两顶点u和v，图G中从u到v的宽度为k的距离，简称k-距离，记为dk(G;u,v)，定义为最小整数d.换句话说，dk(G;u,v)是一个最小正整数d使得G中至少存在k条内点不交且长不超过d的(u,v)路.

定义2[2]图G的宽度为k的直径，简称k-直径，记为dk(G)，定义为dk(G)=max{dk(G;u,v):∀u,v∈V(G)},

显然，d1(G)就是G的直径d(G)，而且有d(G)=d1(G)≤d2(G)≤…≤dω-1(G)≤dω(G).

宽直径的概念最先是由Hsu[3]，Hsu和Lyuu[4]，Hsu和Luczak[5]，Flandrin和Li[6]提出的.宽直径是度量互联网络容错性的重要参数，也是图论的重要研究方向.一些图的宽直径，例如笛卡尔乘积图等已被研究[1，3，6-9].

对一般图G，给出dk(G)的值是困难的，因为这是NP完备问题.目前，只得到了一些dk(G)的上下界的估计式和一些著名的图（结构简单）的宽直径.

下面我们也需要给出网络传输延迟和容错性的另一种类型的度量参数——Rabin数.

定义3设G是ω(≥ 1)连通图，图G的ω-Rabin数，记为rω(G)，定义为最小数r，使得对G的任何ω+1个顶点x,y1,…,yω，G中存在ω条内点不交且长度不超过r的(x,yi)路，i=1,2,…,ω.即G中存在扇Fω(x,Y)，使得每条路的长度至多为r，其中Y={y1,…,yω} .

显然，如果1≤ω≤κ(G)，则rω(G)有确定的值，且d(G)=r1(G)≤r2(G)≤…≤rω-1(G)≤rω(G).

2 匹配组合网络G(G0,G1;M )

令r和n都是正整数，且r≥3.令G0和G1是两个图，且|V(G0)|=|V(G1)|=n.图G(G0,G1;M)的 顶 点 集 定 义 为V(G0)⋃V(G1)，边集为E(G0)⋃E(G1)⋃M，其中M是G0和G1顶点间的一个任意完美匹配（见图1）.则G(G0,G1;M)是一个顶点数为2n，边数为|E(G0)|+|E(G1)|+n，具有完美匹配的图.例如，若G0=G1=Qk，则存在M使得G(G0,G1;M)=Qk+1；或者若G0=G1=CQk，则存在M使得G(G0,G1;M)=CQk+1，这里Qk表示k-维超立方体(hypercube)，CQk表示k-维交叉超立方体(crossed hypercube).

图1 G0和G1顶点间的匹配图

许多著名的网络，例如超立方体、螺旋立方体、星图等等，能通过连接两个低维的网络扩展为高维的网络，下面的匹配组合网络就是这样的扩展例子[7-8].

图G的一个完美匹配就是边的集合M，满足没有两条边是有公共顶点的，并且G中的每个顶点都在M中.显然，如果图G有完美匹配，那么图G的阶一定是偶数.

本文中将讨论分析匹配组合网络G(G0,G1;M)的宽直径.为了方便，下面用u→Pk v表示从u到v的路Pk，u→v表示边uv.

3 网络G(G 0,G1;M )的宽直径

为了简单起见，下面我们把G(G0,G1;M)，V(G0)，V(G1)分别简记为G,V0,V1.对任意的点u∈V(G)=V0⋃V1，即u∈Vi(i=0,1) ，用uˉ∈V1-i表示与u相邻的顶点.显然，有uuˉ∈M.

定理3.1令G0和G1是两个顶点数相同的连通图，且κ(G0)=κ(G1)=ω，那么κ(G)≥ω+1.

定理3.1的证明由Menger-Whitney判定准则，我们只需在G中构造ω+1条内点不交的(u,v)-路R1,…,Rω,Rω+1.对于图G的任意两点u和v，不妨假设u∈V0.我们考虑两种情形.情形1v∈V0.

因为G0是ω-连通的，故由Menger定理可知，G0中存在ω条内点不交的( )u,v- 路P1,P2,…,Pω.另一方面，G1中存在一条(),ˉ- 路 Q.令

则R1,…,Rω,Rω+1是G中内点不交的路.

情形2v∈V1.

令U⊆Vi{u} ，V⊆V1-i{v}，其中U={u1,u2,…,uω} ，V={v1,v2,…,vω} .因为G0和G1是ω- 连通的，Gi中存在(U,u)- 扇Fω(U,u)={W1,W2,…,Wω} ，其中Wk的长度最多为rω(Gi)；G1-i中存在 (V,v)-扇Fω(V,v)={T1,T2,…,Tω} ，其中Tk的长度最多为rω(G1-i).

如果v=ˉ，那么我们选择U，V使得vvk∈E(G1-i) ，vk=，其中k=1,2,…,ω.令

否则，我们选择U，V使得其中k=1,2,…,ω-1.令

易验证，上述情形中构造的路R1,…,Rω,Rω+1是G中内点不交的路.证毕.

推论3.2令G0和G1是顶点数相同的两个图，G=G(G0,G1;M).如果κ(G0)=κ(G1)=δ(G0)=δ(G1)=ω，那么

推论3.2的证明由定理3.1，有κ(G)≥ω+1.由Whitney不等式，可以得到

因此，κ(G)=ω+1.证毕.

定理3.3令G0和G1是顶点数相同的两个图，G=G(G0,G1;M).如果κ(G0)=κ(G1)=δ(G0)=δ(G1)=ω，其中i=0,1，那么dω+1(G)≤max{2 +rω(G0),2+rω(G1),dω(G0),dω(G1) }.

定 理3.3的 证 明由 推 论3.2，G是(ω+1)- 连 通 的.因 此dω+1(G)有 确 定 的 值.令d=和v是G中不同两个顶点.下面，我们只需在G中构造(ω+1)条长度不超过d的内点不交的(u,v)-路.

情形1u,v∈Vi(i∈{0 ,1}).

图2 G0，G1关系示意图

因为Gi是ω-连通的，由Menger定理，Gi中存在ω条内点不交的(u,v)-路P1,P2,…,Pω，使得Pk(1 ≤k≤ω)的最大长度为dω(Gi).令Q是G1-i中最短(uˉ ,vˉ)- 路(参见图 2)，

则由rω(Gi)≥d(Gi)可知，

情形2u∈Vi，v∈V1-i.

令

则

如果v≠uˉ，那么G1-i中存在一条最短路假设v1在Q上.令则因为Gi是ω- 连通的，Gi中存在 (U,u)-扇Fω(U,u)=其中Wk的长度最多为rω(Gi) ，参数关系见图3（b）.

则由rω(Gi)≥d(Gi)可知，

证毕.

本文中主要讨论了匹配组合网络的宽直径.匹配组合网络是著名的互连网络，给出了组合匹配网络G( )G0,G1;M的宽直径的上界，为度量该网络的性能提供了重要的依据.

图3 G0，G1匹配组合网络图

[1]Bondy JA，Murty USR.Graph theorywith applications[M].London:Macmillan，1976.

[2]徐俊明.组合网络理论[M].北京：科学出版社，2007：241.

[3]Hsu DH.On container width and length in graphs，groups，and networks[J].IEICE Trans Fundam，1994，E77A:668-680.

[4]Hsu D H，Lyuu Y D.A graph-theotetical study of transmission delay and fault tolerance[C].In Proc of 4thISMM International Confrenceon Paralleland Distributed Computingand systems，1994.

[5]Hsu DH，Luczak T.Noteon thek-diameterofk-regulark-connected graphs[J].DiscreteMath，1994，132:291-296.

[6]Flandrin E，LiH.Mengerian properties，Hamiltonicity and claw-free graph[J].Networks，1994，24:660-678.

[7]Chen Y，Jimmy JM.Tan Restricted connectivity for three familiesof interconnection networks[J].Appl Math Comput，2007，188:1848-1855.

[8]Chen Y，Jimmy J，Tan M，etal.Super-connectivity and super-edge-connectivity for some interconnection networks[J].Appl Math Comput，2003，140:245-254.

[9]BanicˇI，Žerovnik J.Wide diameter of Cartesian graph bundles[J].Discrete Math，2010，310:1697-1701.