處處h-可斷圖的若干問題研究.pdf

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

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

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

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

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