處處h-可斷圖的若干問(wèn)題研究.pdf

1、圖的連通性理論是圖論學(xué)科重要而基礎(chǔ)的研究領(lǐng)域。通過(guò)該領(lǐng)域的研究，人們對(duì)圖的結(jié)構(gòu)和性質(zhì)有了進(jìn)一步的認(rèn)識(shí)，并且將所得到的結(jié)果應(yīng)用于網(wǎng)絡(luò)設(shè)計(jì)等實(shí)際問(wèn)題中，取得了很多應(yīng)用成果。圖的連通性研究所具有的理論和實(shí)際意義，激發(fā)了很多圖論專(zhuān)家的興趣。長(zhǎng)期以來(lái)，人們圍繞圖的點(diǎn)連通度、邊連通度、局部點(diǎn)(邊)連通度開(kāi)展了大量的研究工作，也取得了許多深刻的理論成果。 隨著研究的深入，人們發(fā)現(xiàn)上述參數(shù)僅反映了系統(tǒng)被毀壞的難易，而很難準(zhǔn)確反映系統(tǒng)被毀壞的程度

2、。于是，人們開(kāi)始摸索研究圖的連通性的新途徑。在1988年，賈曉峰等人提出了一個(gè)新的圖類(lèi)——處處h-可斷圖。設(shè)h是一個(gè)正整數(shù)。若S是圖G的一個(gè)(頂點(diǎn))極小割集，且|S|≤h，則稱(chēng)S是圖G的一個(gè)下h-割集。若對(duì)于每個(gè)頂點(diǎn)v，∈V(G)，至少存在一個(gè)下h-割集S，使得頂點(diǎn)v∈S，則稱(chēng)圖G是一個(gè)處處h-可斷圖。新圖類(lèi)的提出為廣泛圖類(lèi)中圖的最大邊數(shù)，最大團(tuán)等問(wèn)題的解決提供了新的途徑。從處處h-可斷圖的提出到目前為止，賈曉峰等人對(duì)該類(lèi)圖進(jìn)行了較深入

3、的研究，尤其是在最大團(tuán)問(wèn)題方面，取得了較好的結(jié)果。 本文對(duì)處處h-可斷圖的(頂點(diǎn))極小割集進(jìn)行了分類(lèi)：設(shè)G是一個(gè)處處h-可斷圖，S是G的下h-割集，且G中無(wú)其它下h-割集與S交叉，則稱(chēng)S是圖G的A類(lèi)割集。否則稱(chēng)其為圖G的B類(lèi)割集。在此分類(lèi)及前人研究結(jié)果的基礎(chǔ)上，文章討論了與處處h-可斷圖連通性及遞歸證明相關(guān)的新問(wèn)題——可加邊問(wèn)題，并在這個(gè)問(wèn)題的啟發(fā)下引入了刻畫(huà)處處h-可斷圖的連通性的新參數(shù)——圖的完整度。它既反映了將處處h-可斷

4、圖從(頂點(diǎn))極小割集拆分開(kāi)的難易，又反映了該圖被拆分的程度。而在一個(gè)網(wǎng)絡(luò)中，這個(gè)參數(shù)不僅反映了網(wǎng)絡(luò)被毀壞的難易，而且也能反映網(wǎng)絡(luò)被毀壞的程度。所以，對(duì)處處h-可斷圖的可加邊問(wèn)題及其完整度的研究有比較重要的理論和實(shí)際意義。 第一部分，在闡述圖的連通性問(wèn)題的研究現(xiàn)狀及進(jìn)展的同時(shí)，分析了以往圖的連通性研究方法的局限性，論證了處處h-可斷圖和處處h-可斷圖的完整度兩個(gè)概念的提出對(duì)圖的連通性研究的理論意義。 第二部分，給出了關(guān)于圖

5、的(頂點(diǎn))極小割集的一些研究結(jié)果。這些結(jié)果是我們對(duì)處處h-可斷圖的連通性展開(kāi)研究的基石。 第三部分，主要討論了在A類(lèi)割集是割點(diǎn)和A類(lèi)割集不是割點(diǎn)且不是完全圖兩種情況下處處h-可斷圖的可加邊問(wèn)題，論證了處處h-可斷圖可加邊的存在性，給出了刻畫(huà)處處h-圖的結(jié)構(gòu)特性的兩個(gè)充分條件。 第四部分，研究了處處h-可斷圖的完整度及其與圖的其它一些參數(shù)的關(guān)系，并對(duì)處處h-可斷圖的完整度進(jìn)行了界的估計(jì)。 第五部分，在總結(jié)全文的基礎(chǔ)