圖的高階邊連通性和網絡的可靠性比較.pdf

1、上海交通大學博士學位論文圖的高階邊連通性和網絡的可靠性比較姓名：王應前申請學位級別：博士專業(yè)：應用數(shù)學指導教師：李喬2001.8.1＼上海交通大學博士學位論文在條件n≥2h下關于Ah(G)的存在性的新結果：(1)Ah(G)存在當且僅當G有兩個點集不交的h階連通子圖。(2)若G是2連通的，則h(G)存在。(3)若A(G)=12mlnJ，則Ah(G)存在，其中m表示G的邊數(shù)。(4)若G的最小點度6(G)≥h，則h(G)存在。(5)刻劃了A3

2、(G)不存在的所有圖G。21上界2優(yōu)化問題熟知Al(G)≤5l(G)，這里61(G)=6(G)是G的最小點度，即G中與一點相關聯(lián)的邊集的最小基數(shù)。又已證明f8]，如果A2(G)存在，則有A2(G)≤62(G)，其中52(G)是G的最小邊度，即G中與一邊相鄰的邊集的最小基數(shù)。一般地，對于正整數(shù)h≤【n／2J，可定義G的h階最小外度靠(G)如下：設F是G的一個h階導出連通子圖。把G的一端屬于F，另一端不屬于F的邊的集，叫做F的外關聯(lián)邊集，其