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

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

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

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