對(duì)一些控制參數(shù)下的臨界圖的研究.pdf

1、控制理論是圖論中的一個(gè)重要分支，它在計(jì)算機(jī)科學(xué)、通訊網(wǎng)絡(luò)、社會(huì)關(guān)系學(xué)等領(lǐng)域都有著廣泛的應(yīng)用。隨著計(jì)算機(jī)科學(xué)和網(wǎng)絡(luò)技術(shù)的不斷興起，控制理論的研究得到了迅猛的發(fā)展。求圖的控制數(shù)的問(wèn)題是NP-C的，所以一般圖的控制的研究是比較困難的。對(duì)于圖的控制數(shù)，如果從一個(gè)圖中刪去一個(gè)點(diǎn)，則控制數(shù)可能增大、減小或者不變。假如給定一個(gè)圖，任意刪去其中一個(gè)點(diǎn)后得到的圖的控制數(shù)比原來(lái)小，我們則稱這個(gè)圖是控制點(diǎn)臨界圖。對(duì)于加邊的操作來(lái)說(shuō)，眾所周之加上一條邊是不會(huì)增

2、加圖的控制數(shù)的。如果任意加上一條邊，這個(gè)圖的控制數(shù)變小，我們則稱這個(gè)圖為控制邊臨界圖。
　　 1983年，Sumner最先開(kāi)始對(duì)控制邊臨界圖進(jìn)行研究；1984年，Brigham等人對(duì)控制點(diǎn)臨界圖進(jìn)行研究。在控制數(shù)為1或2時(shí)，控制點(diǎn)臨界圖和控制邊臨界圖已經(jīng)得到完全的刻畫(huà)。但是當(dāng)控制數(shù)大于等于3的情況，這些圖的刻畫(huà)還遠(yuǎn)沒(méi)有解決。
　　 在本文中，我們著重研究控制數(shù)為3的情況下的控制點(diǎn)臨界圖和控制邊臨界圖。
　　 第一

3、章，我們介紹圖論中的一些基本概念、術(shù)語(yǔ)、符號(hào)及一些控制理論的基本知識(shí)。
　　 第二章，我們主要對(duì)控制點(diǎn)臨界圖進(jìn)行研究，研究集中在禁止子圖情況下的因子方面的性質(zhì)，主要得到了下面這些結(jié)果：
　　 1.設(shè)圖G是3-控制點(diǎn)臨界圖，如果它有偶數(shù)個(gè)頂點(diǎn)且最小度至少為3，那么G是3-連通的。
　　 2.設(shè)圖G是3-控制點(diǎn)臨界圖，如果它不包含導(dǎo)出的k1，4子圖，且有偶數(shù)個(gè)頂點(diǎn)、最小度至少為4，那么G是雙因子臨界的。
　　

4、 3.設(shè)圖G是3-控制點(diǎn)臨界圖，如果G不包含導(dǎo)出的K1，5子圖、2-連通的、有奇數(shù)個(gè)頂點(diǎn)且最小度至少為3，那么G是因子臨界的或是兩個(gè)特定的圖。
　　 4.設(shè)圖G是3-控制點(diǎn)臨界圖，(I)如果G不包含導(dǎo)出的K1，6子圖，G有偶數(shù)個(gè)頂點(diǎn)且不等于12，那么G有完美匹配。(II)如果G不包含導(dǎo)出的K1，7，有奇數(shù)個(gè)頂點(diǎn)且只有一個(gè)奇分支，頂點(diǎn)數(shù)不等于13，那么G有近似完美匹配或者是兩個(gè)特定的圖。
　　 第三章，我們主要對(duì)控制邊臨界