非连通图与多通量图的理想最短图

非连通图与多通量图的理想最短图

在这项工作中，讨论的图（v，e）是一个简单的无向图，假设v.v（g）是图g的中心组，e=e（g）是图g的边组，kn，p是图。G1∨G2为图G1与G2的联图,其顶点集合V(G1∨G2)=V(G1)∪V(G2),边集合E(G1∨G2)=E(G1)∪E(G2)∪F,其中F={xy:x∈G1,y∈G2}联图P1∨Cn称为轮,记作Wn,其中P1的顶点称为Wn的中心。Wn,m是由轮Wn与Wm的中心顶点合并后构成的连通图。[a]表示不超过实数a的最大整数。在图的优美性的研究成果中,多数是关于连通图优美性的研究,近年来,人们开始关注非连通图优美性问题并取得不少关于此条件下的优美性的结论见文。1利用cnk-等数字图进行认定本文对与轮形图相关的非连通并图的优美性进行了研究,推广了文中的结论,得到非连通图Wm∪Kn,p,Wm,2m+1∪Kn,p,W2p+2+i∪G(i)p,Wm,2m+1∪St(n)和Wm,2m+1∪(C3∨¯Κn)是优美图。本文涉及的主要概念是优美图的定义。设图G=(V,E),k为正整数,如果存在一个单射f:V→{0,1,⋯,|E|+k-1},使得对所有的边uv∈E,由f′(uv)=|f(u)-f(v)|导出一个双射f′:E→{k,k+1,⋯,|E|+k-1},则称图G是k-优美图,f是G的一个k-优美标号。1-优美图也称优美图,1-优美标号也称优美标号。下面三个结果是要用到或要推广的定理:定理A对∀n∈N,n≥3,轮形图Wn是优美图。定理B对任意正整数数n,图W2n+5∪(C3∨¯Κn)是优美图。定理C设m,n为任意自然数,当n≥3,m≥s=[n2]时,图Wn∪St(m)优美图。2,2p+4本文中约定a,b分别表示序列x1,x2,…,xm奇数项和偶数项的最大脚标。s=[m2],即m为偶数时,s=m2,m为奇数时,s=m-12。定理1设任意自然数n≥1,p≥1,当m=2p+3,2p+4时,图Wm∪Kn,p是优美图。证明设V(Wm)={x0;x1,x2,…,xm},V(Kn,P)={v1,v2,…,vn;u1,u2,…,up},E=E(Wm∪Kn,p),则|E|=2m+np。定义图Wm∪Kn,p的顶点标号f为:f(x0)=0‚f(x1)=2m+np-s‚f(xi)=s+i-12,(i=3,5,⋯,2p+3)‚f(xi)=2m+np+1-i2,(i=2,4,6,⋯,b);f(ui)=i,(i=1,2,⋯,p)‚f(vn)=s‚f(vi)=s+(i+1)p+2,(i=1,2,⋯,n-1)下面证明标号f是图Wm∪Kn,p的优美标号。1酶法计算参数(i)由于序列0=f(x0),f(u1),f(u2),⋯,f(up),f(vn),f(x3),f(x5),⋯,f(x2p+3),f(v1),f(v2),⋯,f(vn-1),f(x1),f(x2p+2),f(x2p),⋯,f(x4),f(x2)=2m+np是严格递增的,故映射f是单射。(ii)对所有的边uv∈E,设f′(uv)=|f(u)-f(v)|,则f′(x0x1)=2m+(n-1)p-1,f′(x1x2)=p+1,f′(x0xi)={p+i+12,(i=3,5,⋯,2p+3)2m+np+1-i2,(i=2,4,⋯,2p+2);f′(uivn)=p+1-i,(i=1,2,…,p),f′(uivj)=(j+2)p+3-i,(i=1,2,…,p;j=1,2,…,n-1);f′(xixi+1)=2m+(n-1)p-i,(i=2,3,…,2p+2),f′(x1x2)=p+1,f′(x1x2p+3)=m+(n-1)p因此,序列1=f′(upvn),f′(up-1vn),⋯,f′(u1vn),f′(x1x2),f′(x0x3),f′(x0x5),⋯,f′(x0x2p+3),f′(v1up),f′(v1up-1),⋯,f′(v1u1),f′(v2up),f′(v2up-1),⋯,f′(v2u1),⋯,f′(vn-1up),f′(vn-1up-1),⋯,f′(vn-1u1),f′(x1x2p+3),f′(x2p+2x2p+3),f′(x2p+1x2p+2),⋯,f′(x2x3),f′(x0x1),f′(x0x2p+2),f′(x0x2p),⋯,f(x0x4),f′(x0x2)=2m+np是严格递增的,映射f′:E→{1,2,…,2m+np}是双射。2任意图的模糊综合算法(i)由于序列0=f(x0),f(u1),f(u2),⋯,f(up),f(vn),f(x3),f(x5),⋯,f(x2p+3),f(v1),f(v2),⋯,f(vn-1),f(x1),f(x2p+4),f(x2p+2),⋯,f(x4),f(x2)=2m+np是严格递增的,故映射f是单射。(ii)对所有的边uv∈E,由f′(uv)=|f(u)-f(v)|,有f′(x0x1)=2m+(n-1)p-2‚f′(x1x2)=p+2,f′(x0xi)={p+1+i+12,(i=3,5,⋯,2p+3)2m+np+1-i2,(i=2,4,⋯,2p+4);f′(uivn)=p+2-i,(i=1,2,⋯,p),f′(uivj)=(j+2)p+4-i‚(i=1,2,⋯,p;j=1,2,⋯,n-1);f′(xixi+1)=2m+(n-1)p-1-i,(i=2,3,⋯,2p+3),f′(x1x2)=p+2‚f′(x1x2p+4)=1因此,序列1=f(x1x2p+4),f′(upvn),f′(up-1vn),⋯,f′(u1vn),f′(x1x2),f′(x0x3),f′(x0x5),⋯,f′(x0x2p+3),f′(v1up),f′(v1up-1),⋯,f′(v1u1),f′(v2up),f′(v2up-1),⋯,f′(v2u1),⋯,f′(vn-1up),f′(vn-1up-1),⋯,f′(vn-1u1),f′(x2p+3x2p+4),f′(x2p+2x2p+3),⋯,f′(x2x3),f′(x0x1),f′(x0x2p+4),f′(x0x2p+2),⋯,f(x0x4),f′(x0x2)=2m+np是严格递增的,映射f′:E→{1,2,…,2m+np}是双射。综合1)、2),我们有图Wm∪Kn,p是优美图。在定理1中,取p=1,可得以下结论。推论1对任意自然数n≥1,图W5∪St(n)和W6∪St(n)是优美图。推论2对任意自然数p≥1,图W2p+2+i∪G(i)p是优美图。其中G(i)p(i=1,2)表示p条边的i-优美图。证明i)当i=1时,在定理1中,取m=2p+3,n=1,图W2p+3中的顶点标号f是从V(W2p+3)到{0,p+2,p+3,⋯,2m+p}的单射,顶点标号所确定边值为{p+1,p+2,p+3,⋯,2m+p}。在图K1,p中的顶点标号值为{1,2,3,⋯,p+1},顶点标号确定的边值为{1,2,3,⋯,p}。由图的非连通性,对任意图G,若能有顶点标号g是从V(G)到{1,2,3,⋯,p+1}的单射,且顶点标号所确定的边值为{1,2,3,⋯,p},则W2p+3∪G是优美图。设g1是图G(1)p的优美标号,我们给图G(1)p的顶点用g1+1从新标号,则新标号满足该条件。特殊地,对轮Wn,结合定理A,有Wn∪W4n+3是优美图。ii)当i=2时,在定理1中,取m=2p+4,n=1,图W2p+4中的顶点标号f是V(W2p+4)到{0,p+3,p+4,⋯,2m+p}的单射,顶点标号所确定的边值为{1,p+2,p+3,⋯,2m+p}。在图K1,p中的顶点标号值为{1,2,3,⋯,p,p+2},顶点标号所确定的边值为{2,3,⋯,p+1}。由图的非连通性,对任意图G,若能有顶点标号g是从V(G)到{1,2,3,⋯,p+2}的单射,且顶点标号所确定的边值为{2,3,⋯,p+1},则W2p+4∪G是优美图。设g2是图G(2)p的2-优美标号,我们给图G(2)p用g2+1从新标号,则新标号满足该条件。定理2设任意自然数n≥1,p≥1,当m=2p+3,2p+4时,图Wm,2m+1∪Kn,p是优美图。证明设V(Wm,2m+1)={x0;x1,x2,…,xm;y1,y2,…,y2m+1},V(Kn,P))={v1,v2,…,vn;u1,u2,…,up},E=E(Wm,2m+1∪Kn,p),则|E|=6m+np+2。定义图Wm∪Kn,p的顶点标号f为:f(x0)=0‚f(x1)=6m+np+2-s‚f(xi)=s+i-12,(i=3,5,⋯,2p+3)‚f(xi)=6m+np+3-i2,(i=2,4,6,⋯,b);f(y1)=2s+2m+(n+1)p+5‚f(yi)=s+p+2+i-12,(i=3,5,⋯,2m+1)‚f(yi)=3s+2m+(n+2)p+8-i2,(i=2,4,6,⋯,2m);f(ui)=i,(i=1,2,…,p),f(vn)=s,f(vi)=s+(i+1)p+m+3,(i=1,2,…,n-1)类似定理1可证f是图Wm,2m+1∪Kn,p的优美标号。推论3对任意自然数n≥1,图W5,11∪St(n)和W6,13∪St(n)是优美图。定理3当m≥3,n≥s=[m2]时,Wm,2m+1∪St(n)是优美图。证明设V(Wm,2m+1)={x0;x1,x2,…,xm;y1,y2,…,y2m+1},V(St(n))={v0,v1,v2,…,vn},E=E(Wm,2m+1∪St(n))),则|E|=6m+n+2。定义图Wm,2m+1∪St(n)的顶点标号f为:f(x0)=0‚f(x1)=6m+n+2-s‚f(xi)=s+i-12,(i=3,5,⋯,a)‚f(xi)=6m+n+3-i2,(i=2,4,6,⋯,b)；f(xa)=m-1‚f(yi)=m+i-12,(i=3,5,⋯,2m+1)‚当m为奇数时,f(yi)=5m+n+3-s-i2,(i=2,4,6,⋯,2m);当m为偶数时,f(yi)=5m+n-s+4-i2,(i=2,4,6,⋯,2m)。f(y1)=f(y2m)-1‚f(v0)=s‚f(vi)=i,(i=1,2,⋯,m-s-2)‚f(vi)=m+2+2s+i,(i=m-s-1,m-s,⋯,n)当m-s-2=0时,去掉定义式的第一种情况。我们仅验证当m为偶数时,标号f是图Wm∪Kn,p的优美标号。当m为奇数时,类似。(i)由于序列0=f(x0),f(v1),f(v2),⋯,f(um-s-2),f(x3),f(x5),⋯,f(xm-1),f(y3),f(y5),⋯,f(y2m+1),f(um-s-1),f(um-s),⋯,f(un),f(y1),f(y2m),f(y2m-2),⋯,f(y4),f(y2),f(x1),f(xm),f(xm-2),⋯,f(x4),f(x2)=6m+n+2是严格递增的,故映射f是单射。(ii)对所有的边uv∈E,设f′(uv)=|f(u)-f(v)|,有f′(x0x1)=6m+n+2-s‚f′(x1x2)=s,f′(x1xm)=1；f′(x0xi)={s+i-12,(i=3,5,⋯,m-1)6m+n+3-i2,(i=2,4,⋯,m),f′(xixi+1)=6m+n+3-s-i,(i=2,3,⋯,m-1)；f′(v0vi)=s-i,(i=1,2,⋯,n-s-2),f′(v0vi)=m+2+s+i,(i=m-s-1,m-s,⋯,n)；f′(x0y1)=4m+n+3-s,f′(x0yi)=5m+n-s+4-i2,(i=2,4,6,⋯,2m)；f′(y1y2)=m‚f′(yiyi+1)=4m+n-s+4-i,(i=2,3,⋯,2m),f′(y1y2m+1)=2m+n-s+3因此,序列1=f′(x1xm),f′(v0vn-s-2),f′(v0vn-s-3),⋯,f′(v0v1),f′(x1x2),f′(x0x3),f′(x0x5),⋯,f′(x0xm-1),f′(y1y2),f′(x0y3),f′(x0y5),⋯,f′(x0y2m+1),f′(v0vn-s-1),f′(v0vn-s),⋯,f′(v0vn),f′(y1y2m+1),f′(y2m+1y2m),f′(y2my2m-1),⋯,f′(y3y2),f′(x0y1),f′(x0y2m),f′(x0y2m-2),⋯,f′(x0y2),f′(xmxm-1),f′(xm-1xm-2),⋯,f′(x3x2),f′(x0x1),f′(x0xm),f′(x0xm-2),⋯,f(x0x4),f′(x0x2)=6m+n+2是严格递增的,映射f′:E→{1,2,…,6m+n+2}是双射,因此,图Wm,2m+1∪St(n)是优美图。定理4对任意自然数n≥1,当m=2n+5时,图Wm,2m+1∪(C3∨Κn¯)是优美图。证明设V(Wm,2m+1)={x0;x1,x2,…,xm;y1,y2,…,y2m+1},V(C3)={