網絡結構的邊毀裂度

劉二強,李銀奎

(青海民族大學數學與統計學院,青海 西寧 810007)

網絡結構的邊毀裂度

劉二強,李銀奎

(青海民族大學數學與統計學院,青海 西寧 810007)

在毀裂度的基礎上,研究圖的邊的毀裂度.通過優化組合、歸納假設的方法界定了圖的邊毀裂度的值,如笛卡爾積圖:Pm×Pn,Pm×Cn,Cm×Cn,Km×Kn,并界定了G=G1×G2的邊毀裂度的界.最后給出了一些基本圖,如路、圈、星圖、完全二部圖Km,n的線圖邊毀裂度.

邊毀裂度;笛卡爾積圖;線圖

1 引言

特高壓交流電網不但要求穩定可靠、不容易被破壞,而且要求特高壓交流網絡一旦被毀后能夠容易確定位置,且極易修復.借助圖的連通參數討論圖網絡的穩定性,對于在復雜電網中的應用有特殊意義.文獻[1-8]引入了如邊連通度、邊堅韌度、邊完整度、離散度、邊粘連度等一些不錯的刻畫參數,只是每個參數都有各自的局限性.圖的邊毀裂度是一個新的度量參數(文獻[8]),對于圖網絡的刻畫也有一定的影響.本文進一步的探討了路、圈、完全圖在笛卡爾積下的圖的邊毀裂度以及路、圈、星圖、完全二部圖Km,n在線圖下的邊毀裂度.

設圖G=(V,E),S?E(G),用w(G?S)表示G?S的連通分支數,τ(G?S)表示圖G?S的最大連通分支的階數.圖的邊毀裂度定義為:

對于一個邊集S?E(G),如果w(G?S)?|S|?τ(G?S)=Er(G),稱S為G的一個Er?集.文中討論的圖均為簡單、無向圖,未提及的術語及定義見文獻[7].

2 一些笛卡爾積圖的邊毀裂度結果

定義 2.1[8]連通圖G1與G2的笛卡爾積G1×G2是連通圖且對 u1,v1∈V(G1),u2,v2∈V(G2),((u1,u2),(v1,v2))∈E(G1×G2)? 或者 u1=v1,且(u2,v2)∈E(G2),或者u2=v2,且(u1,v1)∈E(G1).

Pm×Pn構造的網絡圖可以看作是一頂點數為m×n的平面網格.

定理2.1連通圖G是Pm×Pn,則Er(G)=m+n?mn?1.

證明取G任一邊割集S.

情形 1S∩E(Pm)/=?,S∩E(Pn)=?.

(1)w(G?S)=2,n≤|S|≤2n?1,因此有

w(G?S)?|S|?τ(G?S)=2?|S|?(mn?n)=2+n?mn?|S|,

顯然當|S|=n時,w(G?S)?|S|?τ(G?S)=2+n?mn?n=2?mn為最大值.重復這一做法,可得:

(2)2

當w(G?S)=m時,w(G?S)?|S|?τ(G?S)=m?(m?1)n?n=m?mn.根據邊毀裂度定義可得Er(G)=m?mn.

情形 2S∩E(Pm)=?,S∩E(Pn)/=?,同情形1,不再證明.

情形 3S∩E(Pm)/=?,S∩E(Pn)/=?.

取邊求邊毀裂度最好的方法是分層去邊(Pn∪n為一層,邊數為2n?1).

(1)w(G?S)=2,2≤|S|<4,因此有

w(G?S)?|S|?τ(G?S)=2?|S|?(mn?1)=3?mn?|S|,

顯然當|S|=2時,w(G?S)?|S|?τ(G?S)=3?mn?2=1?mn為最大值.重復這一做法,可得:

(2)2

接下來再去一條邊就可以增加一分支,即

w(G?S)=n+1,|S|=n+(n?1)=2n?1,τ(G?S)=mn?n,

w(G?S)?|S|?τ(G?S)=n+1?(2n?1)?(mn?n)=2?mn.

這樣第一層邊全部去掉,當w(G?S)=n+1時,邊毀裂度為這一層最大值.

整個Pm×Pn圖中共有 m?1個這樣的層數,同上重復按層去邊,每層邊取完時的邊毀裂度最大,當去掉 m?1層的邊數后,整個圖形變為 mn?n個孤立點和一條 Pn.此時w(G?S)=mn?n+1,圖的邊毀度為:

w(G?S)?|S|?τ(G?S)=mn?n+1?{(m?1)n+(n?1)m?(n?1)}?n=m?mn.

(3)mn?n+1

w(G?S)=mn時,w(G?S)?|S|?τ(G?S)=mn?{(m?1)n+(n?1)m}?1=m?mn.根據邊毀裂度定義可得Er(G)=m+n?mn?1.

Pm×Cn構造的網絡圖可以看作是一頂點數為m×n的圓柱網格.

定理2.2連通圖G是Pm×Cn(m≥2,n≥3),則

證明取G任一邊割集S.

情形 1S∩E(Pm)/=?,S∩E(Cn)=?.

若2≤w(G?S)≤m,每增加一個分支時,要多去掉n條邊,相應地最大階數減少n.因此w(G?S)?|S|?τ(G?S)隨著分支數的增加,是單調增的,當分支數取到最大值時,邊毀裂度取到最大值,因此w(G?S)=m時,

根據定義可得Er(G)=m?mn.

情形 2S∩E(Pm)=?,S∩E(Cn)/=?.

(1)w(G?S)=2,2m≤|S|≤3m?1,因此

顯然當|S|=2m時,

重復這一做法,可得:

(2)2≤w(G?S)≤n,每增加一個分支時,要多去掉m條邊,相應地最大階數減少m.因此w(G?S)?|S|?τ(G?S)隨著分支數的增加,是單調增的,當分支數取到最大值時,邊毀裂度取到最大值,因此w(G?S)=n時,w(G?S)?|S|?τ(G?S)=n?mn?m.根據定義可得Er(G)=n?mn?m.

情形 3S∩E(Pm)/=?,S∩E(Cn)/=?.

取邊求邊毀裂度最好的是分層去邊(Cn∪n為一層,邊數為2n).

(1)2≤w(G?S)≤n,每增加一個分支時,要多去掉2條邊,相應地最大階數減少1.所以w(G?S)?|S|?τ(G?S)隨著分支數的增加,是不變的.接下來再去一條邊就可以增加一分支,即

這樣第一層邊全部去掉,當w(G?S)=n+1時,邊毀裂度為這一層最大值.

Pm×Cn圖中剩下m?1層,同上重復按層去邊,每層邊取完時的邊毀裂度最大,當去掉m?1層的邊數后,整個圖形變為mn?n個孤立點和一個Cn.此時w(G?S)=mn?n+1,圖的邊毀度為:

(3)mn?n+1

根據邊毀裂度定義可得Er(G)=n?mn?1.

由于m≥2,n≥3,顯然情形2中的Er(G)結果不是最好的,情形1與情形3中的Er(G)結果在下面兩種情況下分別是最好的.

當n?1≥m,即n≥m+1時,Er(G)=n?mn?1是最好的.

反之,當n?1

定理2.3連通圖G是Cm×Cn(m,n≥3),則

證明取G任一邊割集S.

情形 1S∩E(Cm)/=?,S∩E(Cn)=?.

(1)w(G?S)=2,2n≤|S|≤3n?1,有

w(G?S)?|S|?τ(G?S)=2?|S|?(mn?n)=2+n?mn?|S|,

顯然當|S|=2n時,為最大值.重復這一做法,可得:

(2)2

因此根據定義可得,Er(G)=m?mn?n.

情形 2S∩E(Cm)=?,S∩E(Cn)/=?,情形2與情形1相同,因此不再討論.

情形 3S∩E(Cm)/=?,S∩E(Cn)/=?.

(1)w(G?S)=2,4≤|S|<7,有

顯然當|S|=4時,為最大值.重復這一做法,可得:

(2)2

當w(G?S)=n時,|S|=3n?2,τ(G?S)=mn?(n?1),因此有

接下來再去掉2條邊,就可以得到一個分支,相應地最大階數減少1.此時w(G?S)= n+1,|S|=3n,τ(G?S)=mn?n,

w(G?S)=n+1,第一層邊數已經取完,易觀察到剩余階數大的部分是圓柱網格相當于Pm?1×Cn.因此接下來求邊毀裂度是分層去邊.

重復以上做法,知Pm?1×Cn圖中共有m?2個這樣的層數,根據定理2.2,重復按層去邊,每層邊取完時的邊毀裂度最大,當去掉m?1層的邊數后,整個圖形變為mn?n個孤立點和一個Cn.此時w(G?S)=mn?n+1,圖的邊毀度為:

(3)mn?n+1

Cm×Cn與Cn×Cm得到的圖是相同的,情形1與情形2得到的結果其實可以看作是相同的,所以取情形1中得到的結果.情形1與情形3得到的結果在下面兩種情況下分別是最好的.

當n?1≥m,即n≥m+1時,Er(G)=?mn?1是最好的.

反之,當n?1

定理2.4連通圖G是Km×Kn(m,n≥3),則

證明過程同定理2.2,定理2.3.不再贅述.

在笛卡爾積圖中發現,邊毀裂度越小,圖的結構越復雜,圖就越穩定,越不容易被破壞.這種圖網絡的抗毀性最好.在笛卡爾積圖中,Pm×Pn的圖結構是最簡單的,這種圖網絡抗毀性最差,最容易被破壞;Km×Kn的圖結構是最復雜的,也是最穩定的,網絡抗毀性最好.所以結合定理2.1,定理2.2,定理2.3,定理2.4,有下面的推論:

推論2.1設G=G1×G2,則5?(mn+m+n)≤Er(G)≤?1.

注 2.1當P2×P2時,圖為圈,恰好取到上界-1.當Km×Kn且m≥4時,恰好取到下界.

3 一些線圖的邊毀裂度的結果

引理3.1G是樹當且僅當Er(G)=0.

引理3.2設G為n階的圈,則Er(G)=?1.

引理3.3G是完全圖Kn(n≥5),則Er(G)=4?2n.

定義 3.1[9]一個圖G的線圖L(G),它的頂點是圖G的邊,任意兩個點之間相鄰,當且僅當圖G中相應的邊之間是相鄰的.

推論3.1圖G是n階的路Pn,則Er(L(G))=0.

證明因為G的線圖L(G)顯然仍是一條路,且L(G)=Pn?1.根據引理3.1,Pn是樹,顯然有Er(Pn)=0.所以Er(L(G))=0.

推論3.2圖G是n階的圈Cn,則Er(L(G))=?1.

證明因為G的線圖L(G)顯然仍是一個圈,且L(G)=Cn.根據引理3.2,顯然Er(Cn)=?1.所以Er(L(G))=?1.

推論3.3圖G是n+1階的星圖K1,n,則Er(L(G))=4?2n(n≥5).

證明因為G的線圖L(G)是一個完全圖,

當n=2時,K1,2的線圖L(K1,2)=P2,所以Er(L(K1,3))=0;

當n=3時,K1,3的線圖L(K1,3)=C3,所以Er(L(K1,3))=?1;

當n=4時,K1,4的線圖L(K1,4)=K4,很容易得出Er(L(K1,4))=?3;

當n≥5時,K1,n的線圖L(G)=Kn,根據引理3.3,所以Er(L(G))=4?2n.

推論3.4圖G是完全二部圖Km,n,則

證明易知L(G)=Km×Kn,因此圖G的線圖的邊毀裂度相當于Km×Kn的邊毀裂度.根據定理2.5,得到上面結果.

[1] Li Y,Zhang S,Li X．The rupture degree of graphs[J]．International Journal of Computer Mathematics, 2005,82(7):793-803.

[2] 武燕,魏暹蓀.關于圖的邊粘連度[J].工程數學學報,2004,21(5):704-708.

[3] 陳忠,李銀奎.完全k叉樹的粘連度[J].純粹數學與應用數學,2013,29(5):484-488.

[4] 李銀奎,段寶榮,陳忠.完全k叉樹的離散數和完整度[J].純粹數學與應用數學,2011,27(3):285-291.

[5] K S Bagga,L W Beineke,M I Lipman,R E Pippert.Edge-integrity:a Survey[J].Discrete Math.,1994,124: 3-12.

[6] B L Piazzal,F S Roberts,S K Stueckle.Edge-tenacious networks[J].Networks,1995,25:7-17.

[7] 邦迪J A,默蒂U S F.圖論及其應用[M].北京:科學出版社,1984.

[8] 李銀奎.圖的連通參數的相關研究[D].西安:西北工業大學,2003.

[9] 李學良,劉艷.路圖與線圖的一個綜述[J].工程數學學報,2007,05:761-787.

The edge rupture degree of network structure

Liu Erqiang,Li Yinkui
(School of Mathematics and Statistics,Qinghai Nationalities University,Xining 810007,China)

This paper is based on the rupture degree,and researches the edge rupture degree of graphs.By methods of optimized combination,inductive hypothesis,de fi ne the edge rupture degree of graphs.Such as the Cartesian product graphs:Pm×Pn,Pm×Cn,Cm×Cn,Km×Kn,and de fi ne the bound of edge rupture degree of

G=G1×G2.At last,discussed the rupture degree of line graph of some graph classes,such as paths,circle,star graph,complete bipartite graph Km,nand so on.

the stability of network,edge rupture degree,the cartesian product graph,line graph

O157.5

A

1008-5513(2014)04-0428-07

10.3969/j.issn.1008-5513.2014.04.013

2014-05-19.

教育部“信息網絡抗毀性與嵌入式理論研究”(Z2010007);青海民族大學“基于抗毀性的網絡結構優化研究”(xjz201403).

劉二強(1988-),碩士,研究方向：圖論與網絡優化.

2010MSC:05C15