网络拓扑结构设计中几个问题的.研究

《网络拓扑结构设计中几个问题的.研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、中国科学技术大学硕士学位论文5中，已指出了一些优图的图类．在这里，我们首先给出一些非优图的必要条件，然后由此获得一些优图的图类，它们包括非平凡的边可迁图，不含三角形的奇阶连通点可迁图．另外，在[14]，[25]，[27]，[37]中所得到的某些优图图类可有我们这里的结果导出．§1．2一些记号和预备结果设G=(KE)是图，x，y是v(a)的非空子集，则有(见[28】，Problem6481：d(XnY)+d(XuY)≤d(X)+d(Y)(1．2．1)若xnY=O，记(x，Y)={e=xy∈E：z∈X且Y∈Y)s

2、是G的1一限制边割，如果}SI=A’(G)，则称s为A，-割．易知，对于任意的A’一割S，G—s恰有两个连通分支．设x是V(V)的真子集，若O(X)是G的A’一割，就称x是G的分片．如果x是G的一个分片，则又也是G的分片．令r(a)=．tin{Ixl：X是G的分片)．显然，2≤r(G)茎{1vf．分片x如果满足IXl=r(G)就称x是G的原子．定理1．1非平凡图G是优的当且仅当r(e)=2．证明：设r(a)=2．则存在X={z，g}满足d(X)=Ⅳ(G)=话(e)，这里e=xy∈E(G)．由(1．1．1)及f

3、(G)的定义得，∈(G)≤fG(e)=d(X)=入’(G)≤f(G)，所以G是优的．反之，假设G是优的，则存在G的一条边e=xy满足Ⅳ(G)=f(G)=如(e)=de(x)+da(y)一2．现令X=fX，g)．若G—O(X)无孤立点，则r(G)=2．下设G—O(X)有一个孤立点u．显然1≤dc(u)S2．如果如(u)=l，不失一般性，我们设u与Y相邻，那么dG(z)+da(y)一2=f(G)≤da(y)+da(u)一2=da(y)一1．中国科学技术大学硕士学位论文6这说明da(x)=1．于是矛盾A’(G)≤f

4、{yz：da(z)≥2}I≤da(x)～2=(da(x)+dv(y)一2)一1=f(G)如果dG(“)=2，u与z，Y都相邻．则dG(x)+da(y)一2=∈(G)≤da(y)+de(u)一2=da,(y)从而得da(x)=2，类似地，又可得da(y)=2G就是一个三角形，矛盾于假设§1．3非优图原子的性质引理1．2G是非优图，F是G的一个分片，u是F的真子集，』是图G—O(U)中孤立点的集合．如果J∈u且I(j-，_)I≥l(，，F＼u)l，则F＼I是G的一个分片．证明：不妨假设，≠0令Y=r＼i，F’=F

5、＼u那么y≠O，F’≠0，因为，∈u且u是F的真子集．记z是G—O(Y)的全体孤立点的集合．如果Z=D，则y是G的1一限制边割．由假设I(』，F)I≥l(，，F引，我们有A’(G)茎d(Y)=d(F)一I(，，F)I+I(』，F引Sd(F)=A’(G)这说明y是G的分片．故当Z=O时引理结论成立．以下证明Z=O．假设Z≠0，我们导出矛盾．首先，说明对于任意X∈I，(z，F)≠0．令I’={X∈I：(X，F)=0)．如果17≠0，则ⅣG(，’)∈F’，因为由假设知(I，U＼I)=O．令Z’=(znF，)＼ⅣG(

6、，’)，W=(Yu』，)＼砂易知，G—O(W)不含孤立点，o(w)是G的一个1一限制边割．注意到l(』＼，’，F)l=I(，，_)l≥l(J，F引≥l(』’，F引≥I，7I>0，2002年中国科学技术大学硕士学位论文7得i＼1’≠0且I(八，’，F)f≥l(，，F引≥l』’，F7＼z’l+I(，＼，’，F7＼z引>I(，＼，’，F’＼z’)于是我们有d(仉7)=d(F)一1(z’，F)1d(F)一I(Z’，F)I曼d(r)f(J＼，’，F)1+i(i＼1’，F’＼z’)A’(G)．矛盾导出，’=0，即对于任给

7、X∈I，(X，F)≠D．于是(Y，，”)l=』Na(v)n，”l≤f(Na(y)n』”，F)I，Vy∈Z，，”∈，(1．3．1)其次，我们断言z=NG(y)nF’I’=0说明z∈y．因为z是G—a(FV)的孤立点的集合且G—o(E)不含孤立点，故z￡Ⅳ舀(n但ⅣG(，)nU=0，因为由假设J∈u是G—o(u)的孤立点的集合．于是z∈Ⅳ舀(，)nF，．另一方面，如果(ⅣG(，)nF，)＼z≠0，那么v＼z≠0，G—oW＼z)不含孤立点，因为F是G的一个分片．又由j≠O和D≠z∈ⅣG(J)nF’知(J，Z)≠O．

8、根据假设J』，F}2II，F仉我们有A’(G)≤d(Y＼Z)=d(F)一I(，，-f)I—J(z，_)l+『，，F’＼z