关于笛卡尔乘积图边容错直径的研究

2012-05-26刘启云王金建

重庆工商大学学报（自然科学版） 2012年8期

刘启云，王金建，谢堃

(安徽大学数学科学学院，合肥 230601)

0 引言

大规模集成(VLSI)电路技术的出现，使人们能建造出非常庞大而复杂的互联网络.出于多方面考虑，下一代超级计算机系统将通过增加处理器的数目，而不是单靠利用更快的处理器来实现高速快捷的目的.建造超级计算机系统最困难的技术问题将是连接这些处理器的互联网络的设计，选择一个合适和理想的互联网络拓扑结构将变成一个迫切需要解决的问题.实践证明，图论是设计和分析互联网络的最基本且强有力的数学工具，因为互联网络的拓扑结构就是图.将网络中的处理器看成图中的顶点，各处理器之间的网络连线对应于图中连接相应顶点的边，此时，就可以通过分析图的结构来研究该网络.这样，网络的建构方法和可靠性，就可以看作是图的构造方法和可靠性.笛卡尔乘积是构建大型网络的重要方法，容错性是衡量网络效用性的重要标准，它们均可对应成图的相关特点和性质.

1 预备知识

介绍徐俊明［1］给出的图的基本定义和符号，这里只考虑简单无向图，即那些没有环和重边的无向图.

定义1 令图G=(V(G)，E(G))，其中V(G)，E(G)分别是图G的顶点集和边集.对任何u，v∈V(G)，若u，v之间有边，就说u和v是邻接的，并分别用NG(u)，dG(u)表示顶点u的邻点集合和邻点的数目，通常dG(u)称为u的度，图G顶点的最小度和最大度记作δ(G)和Δ(G)，分别定义为

定义2 设u0，u1，…，uk是G中的k+1个不同的顶点，若对所有的0≤i≤k-1，均有ui与ui+1邻接，记P=u0u1…uk，则P表示一条从u0到uk的路，其长度为k;距离dG(u，v)表示G中u到v最短路的长度，如果没有这样的路，就记dG(u，v)=∞.当u，v取遍所有的顶点，把dG(u，v)的最大值称为图G的直径，记作d(G).

定义3G的点连通度κ(G)，指的是G的最小点割的大小，也就是说，存在V(G)的一个大小为κ(G)的子集，使得G在删除这些点后变得不连通;相似地，边连通度λ(G)指的是G的最小边割的大小.

定义4 若κ(G)≥k，则说图G是k点连通的;若λ(G)≥t，则说图G是t边连通的.

网络的笛卡尔乘积设计在其拓扑结构上就是图的笛卡尔乘积，接着描述一下徐俊明［3］给出的笛卡尔乘积图构造方法及部分性质.

定义5 设G1=(V1，E1)和G2=(V2，E2)是两个无向图，G1和G2的笛卡尔乘积是无向图，记为G1×G2，其中V(G1×G2)=V1×V2，两个不同的顶点x1x2和y1y2(其中x1，y1∈V(G1)，x2，y2∈V(G2))相邻当且仅当或者x1=y1且x2y2∈E(G2)，或者x2=y2且x1y1∈E(G1)，G1和G2称为G1×G2的因子;若x1x2和y1y2邻接，就用(x1x2，y1y2)或者(y1y2，x1x2)表示这条边.

网络的容错性对应于它的图结构的点容错直径和边容错直径，徐俊明［3］也给出了相关的定义和结论.

定义6 对w点连通图G，它的(w-1)点容错直径定义为

定义7 设G是t边连通图，x，y∈V(G)，F⊆E(G)，＜t;G中从x到y的(t-1)边容错距离，记为D't(G;x，y)，定义为

显然，

G的(t-1)边容错直径，记为D't(G)，定义为

显然，

例如，对于无向圈Cn(n≥3)，有D'2(Cn)=n-1.

显然，对任何t边连通图G，有

对边容错直径的研究已经有了一些结果，比如，Plesnik［4］就证明了:对任何无向图G，有D'2(G)≤2d(G)，而且这个上界是最好的，即存在一个2边连通无向图G，使得D'2(G)=2d(G).但是，总的来说确定一般图的边容错直径是相当困难的，还有许多问题期待着被解决.

对于κ(G)和λ(G)，有个重要的结论，是由Whitney［2］得到的，在图论的研究中经常被使用到.

引理1 对于任意图G，κ(G)≤λ(G)≤δ(G).

引理2 由笛卡尔乘积图的定义，容易得到它的一些基本性质.

(a)v(G1×G2)=v(G1)v(G2).

(b)对任何xy∈V(G1×G2)，其中x∈V(G1)且y∈V(G2)(xy)=dG1(x)+dG2(y);特别地，如果G1和G2分别是r1正则和r2正则的，则G1×G2是r1+r2正则的.

(c)对任何y∈V(G2)，G1≅G1×{y}⊆G1×G2;对任何x∈V(G1)，G2≅{x}×G2⊆G1×G2.

(d)由G1×G2的定义，如果P=(x1，v1，v2，…，vm，y1)是G1中一条(x1，y1)路，则对任何b∈V(G2)，(x1b，v1b，v2b，…，vmb，y1b)记为Pb，是G1×G2中从顶点x1b到顶点y1b的路;同样地，如果W=(x2，u1，u2，…，ul，y2)是G2中一条(x2，y2)路，则对任何a∈V(G1)，(ax2，au1，au2，…，aul，ay2)记为aW，是G1×G2中从顶点ax2到顶点ay2的路;记G1b=G1×{b}，aG2={a}×G2，显然有Pb⊆G1b≅G1，aW⊆aG2≅G2，故Pb与aW是边不交.

在提出主要结论之前，引入下面的主要引理，它是由Chiue和Shieh［7］得到的.

引理3 若λ1，λ2，λ分别是G1，G2和G的边连通度，其中图G是G1与G2的笛卡尔乘积图，则有λ≥λ1+λ2.

2 主要结论

笛卡尔乘积图点容错直径和边容错直径的探讨并没有很长时间，再加上点容错直径和边容错直径的研究难度很大，所以这方面的结论不是太多.但是，经过不断的努力，仍取得了一些可喜的成果.像关于笛卡尔乘积图的点容错直径，Xu 等［5］证明了:设Gi是ki点连通无向图，ki≥1，i=1，2，则(G1×G2)≤Dk1(G1)+Dk2(G2)+1;Chiue和Shieh［5］研究了多个图笛卡尔乘积的点容错直径，并得到了一个更广泛的结果，这里不再详细地说明.而现在对笛卡尔乘积图边容错直径的讨论似乎还不是太多，似乎是由于删除边与删除点产生的效果有很大不同造成的，但有时两者的证明思想或许可以相互借鉴.此处尝试修改和简化Xu等［5］的方法来对笛卡尔乘积图的边容错直径进行讨论，并得到了一个相关的结论.

根据笛卡尔乘积图、边容错直径的部分性质和引理1-3，将得到下面的结果.

定理1 设Gi是ti边连通无向图，ti≥1，i=1，2，则(G1×G2)≤D't1(G1)+D't2(G2)+1.

证明令G=G1×G2，t=t1+t2，设 λ1，λ2，λ 分别是图G1，G2和G的边连通度，显然有 λ1≥t1，λ2≥t2，且由引理 1 可得 λ≥λ1+λ2≥t1+t2=t，因此，D't(G)是确定的.令 δi= δ(Gi)，i=1，2，则 δ1≥t1，δ2≥t2.再令F⊂E(G)，‖F‖=t-1，x和y是G-F中不同的两个顶点.由于F是边的集合，显然V(G-F)=V(G).为了证明定理1，只需要在G-F中构造具有要求长度的xy路S(x，y).

设x=x1x2，y=y1y2，其中x1，y1∈V(G1)，x2，y2∈V(G2)，并设P(x1，y1)是G1中最短(x1，y1)路，Q(x2，y2)是G2中最短(x2，y2)路.

情形1x2=y2.

由于x，y是不同的两个顶点，故有x1≠y1且x，y∈V(G1x2).

显然，H1，H2，…，Hδ2均是G的子图，且两两边不交.因为≥t1，所以H1，H2，…，Hδ2中至少有一个，比如说是H1与F不交(否则‖F‖≥t1+δ2≥t2+t1，这与‖F‖=t-1相矛盾).于是，S:x1x2→x1b1是G-F中长度不超过d(G1)+2的xy路.

综上所述，D't(G)≤max{(G1)，2+d(G1)}.

情形2x1=y1.

由于x，y是不同的两个顶点，故有x2≠y2且x，y∈x1G2.

接着使用与情形1中类似的方法，很容易得出，D't(G)≤max{(G2)，2+d(G2)}.

情形3x2≠y2且x1≠y1.

易知，T1，T2，…都是图G的子图，且两两边不交.因为≤t2-1，所以其中至少有一个，不妨说是T1与F不交.于是，S:x1x2→x1b1是G-F中长度不超过1+d(G1)+(G2)的xy路.

由前面边容错直径的性质，可以得到d(G1)=D'1(G1)≤D'2(G1)≤…≤(G1)与d(G2)=D'1(G2)≤D'2(G2)≤…≤(G2)，利用这两个不等式可以对(a)(b)和(c)结果进行适当的放缩汇总，进而有D't(G1×G2)≤(G1)+(G2)+1.定理1得证.

可以通过考察一些实例来验证定理1.先看图G=C4×C4，其中C4是顶点为{1，2，3，4}的无向圈，如图1.

经过计算，发现取F={(11，12)，(11，14)，(11，41)}(图 1 中虚线部分)，则D'4(C4×C4)的值就是顶点 11和43在G-F中的距离.在图1中用黑线部分标示出了顶点11到43的一条最短路，容易看出它的值是5，因此，5=D'4(C4×C4)≤D'2(C4)+D'2(C4)+1=7.

再看图G=P2×P2=C4，其中P2是长为1的路，如图2.