圖的高階邊連通性和網(wǎng)絡(luò)的可靠性比較.pdf

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

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