k階限制邊連通度的最優(yōu)化.pdf

1、設(shè)G=(V, E)是無向簡(jiǎn)單連通圖，S(C)E是G的一個(gè)邊割，如果G-S的每個(gè)連通分支都至少包含k個(gè)頂點(diǎn)，則稱S為G的一個(gè)k階限制邊割.若G的k階限制邊割存在，則稱G是λk-連通的，并把G的最小k階限制邊割所含的邊數(shù)稱為G的k階限制邊連通度，記為λk(G).k階限制邊連通度作為邊連通度的推廣，是計(jì)算機(jī)互連網(wǎng)絡(luò)可靠性的一個(gè)重要度量參數(shù).令ξk(G)=min{|[X，(X)]|∶X(∈)V,|X|=k，G[X]連通}.我們稱一個(gè)存在k階限制

2、邊連通度的圖G是最優(yōu)k階限制邊連通的(簡(jiǎn)稱為λk-最優(yōu)的)，如果λk(G)=ξk(G).本文主要研究了圖的最優(yōu)k階限制邊連通性，其中k=4，5.本文分為兩章:
　　第一章主要介紹了有關(guān)圖論方面的基本概念和記號(hào).
　　第二章從不同角度研究了圖是λ4-最優(yōu)和λ5-最優(yōu)的充分條件.主要結(jié)果如下:
　　(1)設(shè)G是階為n(n≥11)的λ4-連通圖，若對(duì)G中任意一對(duì)不相鄰的頂點(diǎn)u，v都有|N(u)∩N(v)|≥6且G[N(u)∩

3、N(v)]至少包含16條邊，則G是λ4-最優(yōu)的.
　　(2)設(shè)G是λ5-連通圖.S=[X，Y]是G的一個(gè)λ5-割.若對(duì)G中的任意一對(duì)不相鄰頂點(diǎn)u，v都有|N(u)∩N(v)|≥8且|X4|≤1，則G是λ5-最優(yōu)的.
　　(3)設(shè)G是n(n≥52)階的λ5-連通圖.若對(duì)G中任意一對(duì)不相鄰頂點(diǎn)u，v都有|N(u)∩N(v)|≥8且ξ5(G)≤2n+3，則G是λ5-最優(yōu)的.
　　(4)設(shè)G是λ5-連通圖.若對(duì)G中任意一對(duì)不相