一些圖的斷裂度和孤立斷裂度.pdf

1、設(shè)G是連通圖，S是G的一個(gè)頂點(diǎn)子集，當(dāng)G不是完全圖時(shí)，若G-S不連通，則稱(chēng)S是G的點(diǎn)斷集;當(dāng)G=Kn時(shí)，Kn的任何（n-1）個(gè)點(diǎn)組成的集合，亦稱(chēng)為G的點(diǎn)斷集.G的所有點(diǎn)斷集組成的集合記為C(G').斷裂度是圖的哈密爾頓性和容錯(cuò)性的一個(gè)有效度量，被定義為b(G)=max{ω(G-S)-|S|:S∈C(G)}，其中ω(G-S)表示G-S的分支數(shù).孤立斷裂度B(G)定義為B(G)=max{i(G-S)-|S|:S∈C(G)}，其中i(G-S)

2、表示G-S的孤立點(diǎn)數(shù).它是斷裂度的改進(jìn)，能刻畫(huà)具有相同連通度和相同斷裂度的圖在連通程度上的差異.本文研究了樹(shù)的斷裂度和一些圖的孤立斷裂度.
　　在第一章中，我們給出本文用到的基本的概念和符號(hào).第一節(jié)給出本文涉及到的圖論的基本概念.第二節(jié)給出了斷裂度和孤立斷裂度的定義和一些研究成果.
　　本文第二章第一節(jié)研究樹(shù)的斷裂度的緊上界，得到了樹(shù)的最大斷裂度公式:設(shè)T[n，△]是階為n(≥2)，最大度為△（≥1）的樹(shù)組成的集合.那么ma

3、x T∈T[n，△] b（T）={ n-2[n-1/△] r（n-1/△）≠1n-2[n-1/△]+1 r(n-1/△)=1，其中r（n-1/△）表示n-1/△的余數(shù).第二節(jié)研究了樹(shù)T的斷裂度b(T)與它的余樹(shù)(T)的斷裂度b（(T)）的和b(T)+b((T))以及積b（T）b（(T)）的取值范圍.
　　第三章第一節(jié)給出了連通圖G與其連通補(bǔ)圖G的孤立斷裂度的關(guān)系:-（n-3）≤B(G)+B((G))≤n-3，并證明了對(duì)[-(n-3