圖的等周邊連通度的最優(yōu)化.pdf

1、網(wǎng)絡(luò)的可靠性可以通過圖的邊連通度來度量.但是，用圖的邊連通度來度量網(wǎng)絡(luò)的可靠性存在一些缺陷.為了彌補(bǔ)這些缺陷，Hakimi[1]提出了條件邊連通度的概念.圖的等周邊連通度是一種條件邊連通度。
　　本文第一章介紹了圖的一些基本概念以及內(nèi)容安排。
　　第二章討論了二部圖的k-等周邊連通性.我們證明了:
　　(a)設(shè)G(X∪ Y,E)是一個(gè)頂點(diǎn)數(shù)n≥4的連通二部圖.若有一個(gè)飽和X或Y中所有頂點(diǎn)的匹配且對任意的u，v∈X和u，

2、v∈Y有|N(u)∩ N(v)|≥2則G是γ2-最優(yōu)的。
　　(b)設(shè)G是一個(gè)n階連通二部圖，δ≥3，若β3≥n-2則G為γ3-最優(yōu)的。
　　(c)設(shè)k是一個(gè)正整數(shù)且設(shè)G是一個(gè)n階二部圖.若G的最小度δ（G）≥n+2k/4則G是γk-最優(yōu)的。
　　第三章在第二章的基礎(chǔ)上進(jìn)一步討論了無三角圖的k-等周邊連通性，主要證明了:
　　(a)設(shè)G是一個(gè)頂點(diǎn)數(shù)n≥4的連通無三角圖，如果對于任意距離為2的點(diǎn)對u，v都有d(u)