国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

網(wǎng)絡結(jié)構(gòu)的邊毀裂度

2014-07-24 14:34劉二強李銀奎
關鍵詞:條邊邊數(shù)階數(shù)

劉二強,李銀奎

(青海民族大學數(shù)學與統(tǒng)計學院,青海 西寧 810007)

網(wǎng)絡結(jié)構(gòu)的邊毀裂度

劉二強,李銀奎

(青海民族大學數(shù)學與統(tǒng)計學院,青海 西寧 810007)

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

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

1 引言

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

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

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

2 一些笛卡爾積圖的邊毀裂度結(jié)果

定義 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構(gòu)造的網(wǎng)絡圖可以看作是一頂點數(shù)為m×n的平面網(wǎng)格.

定理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.根據(jù)邊毀裂度定義可得Er(G)=m?mn.

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

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

取邊求邊毀裂度最好的方法是分層去邊(Pn∪n為一層,邊數(shù)為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個這樣的層數(shù),同上重復按層去邊,每層邊取完時的邊毀裂度最大,當去掉 m?1層的邊數(shù)后,整個圖形變?yōu)?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.根據(jù)邊毀裂度定義可得Er(G)=m+n?mn?1.

Pm×Cn構(gòu)造的網(wǎng)絡圖可以看作是一頂點數(shù)為m×n的圓柱網(wǎng)格.

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

證明取G任一邊割集S.

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

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

根據(jù)定義可得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條邊,相應地最大階數(shù)減少m.因此w(G?S)?|S|?τ(G?S)隨著分支數(shù)的增加,是單調(diào)增的,當分支數(shù)取到最大值時,邊毀裂度取到最大值,因此w(G?S)=n時,w(G?S)?|S|?τ(G?S)=n?mn?m.根據(jù)定義可得Er(G)=n?mn?m.

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

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

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

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

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

(3)mn?n+1

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

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

當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

因此根據(jù)定義可得,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條邊,就可以得到一個分支,相應地最大階數(shù)減少1.此時w(G?S)= n+1,|S|=3n,τ(G?S)=mn?n,

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

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

(3)mn?n+1

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

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

反之,當n?1

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

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

在笛卡爾積圖中發(fā)現(xiàn),邊毀裂度越小,圖的結(jié)構(gòu)越復雜,圖就越穩(wěn)定,越不容易被破壞.這種圖網(wǎng)絡的抗毀性最好.在笛卡爾積圖中,Pm×Pn的圖結(jié)構(gòu)是最簡單的,這種圖網(wǎng)絡抗毀性最差,最容易被破壞;Km×Kn的圖結(jié)構(gòu)是最復雜的,也是最穩(wěn)定的,網(wǎng)絡抗毀性最好.所以結(jié)合定理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 一些線圖的邊毀裂度的結(jié)果

引理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.根據(jù)引理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.根據(jù)引理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,根據(jù)引理3.3,所以Er(L(G))=4?2n.

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

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

[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].工程數(shù)學學報,2004,21(5):704-708.

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

[4] 李銀奎,段寶榮,陳忠.完全k叉樹的離散數(shù)和完整度[J].純粹數(shù)學與應用數(shù)學,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] 李銀奎.圖的連通參數(shù)的相關研究[D].西安:西北工業(yè)大學,2003.

[9] 李學良,劉艷.路圖與線圖的一個綜述[J].工程數(shù)學學報,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.

教育部“信息網(wǎng)絡抗毀性與嵌入式理論研究”(Z2010007);青海民族大學“基于抗毀性的網(wǎng)絡結(jié)構(gòu)優(yōu)化研究”(xjz201403).

劉二強(1988-),碩士,研究方向:圖論與網(wǎng)絡優(yōu)化.

2010MSC:05C15

猜你喜歡
條邊邊數(shù)階數(shù)
確定有限級數(shù)解的階數(shù)上界的一種n階展開方法
盤點多邊形的考點
復變函數(shù)中孤立奇點的判別
2018年第2期答案
有關垂足三角形幾個最值猜想的證明*
西江邊數(shù)大船
認識平面圖形
最大度為10的邊染色臨界圖邊數(shù)的新下界
關于動態(tài)電路階數(shù)的討論
基于疊加序列的信道估計的研究*