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

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

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