資源描述：
《對一些控制參數(shù)下的臨界圖的研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
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ù)的問題是NP-C的，所以一般圖的控制的研究是比較困難的。對于圖的控制數(shù)，如果從一個(gè)圖中刪去一個(gè)點(diǎn)，則控制數(shù)可能增大、減小或者不變。假如給定一個(gè)圖，任意刪去其中一個(gè)點(diǎn)后得到的圖的控制數(shù)比原來小，我們則稱這個(gè)圖是控制點(diǎn)臨界圖。對于加邊的操作來說，眾所周之加上一條邊是不會(huì)增加圖的控制數(shù)的。如果任意加上一條邊，這個(gè)圖的控制數(shù)變小，我們則稱這個(gè)圖為控制邊臨界圖。1983年，Sumner最先開始對控
2、制邊臨界圖進(jìn)行研究；1984年，Brigham等人對控制點(diǎn)臨界圖進(jìn)行研究。在控制數(shù)為1或2時(shí)，控制點(diǎn)臨界圖和控制邊臨界圖已經(jīng)得到完全的刻畫。但是當(dāng)控制數(shù)大于等于3的情況，這些圖的刻畫還遠(yuǎn)沒有解決。在本文中，我們著重研究控制數(shù)為3的情況下的控制點(diǎn)臨界圖和控制邊臨界圖。第一章，我們介紹圖論中的一些基本概念、術(shù)語、符號(hào)及一些控制理論的基本知識(shí)。．第二章，我們主要對控制點(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)臨界圖，如
3、果它不包含導(dǎo)出的蜀．4子圖，且有偶數(shù)個(gè)頂點(diǎn)、最小度至少為4，那么G是雙因子臨界的。3．設(shè)圖G是3．控制點(diǎn)臨界圖，如果G不包含導(dǎo)出的墨．5子圖、2．連通的、有奇數(shù)個(gè)頂點(diǎn)且最小度至少為3，那么G是因子臨界的或是兩個(gè)特定的圖。4．設(shè)圖G是3．控制點(diǎn)臨界圖，(D如果G不包含導(dǎo)出的蜀．6子圖，G有偶數(shù)個(gè)頂點(diǎn)且不等于12，那么G有完美匹配。(Ⅱ)如果G不包含導(dǎo)出的蜀．7’有奇數(shù)個(gè)頂點(diǎn)且只有一個(gè)奇分支，頂點(diǎn)數(shù)不等于13，那么G有近似完美匹配或者是兩個(gè)特定的圖。第三章，我們主要對控制邊臨界圖進(jìn)行研究。第一節(jié)，主要介紹一些已知的結(jié)果，包括3一控制邊臨界圖的哈密頓性的證明。第二節(jié)
4、，主要給出Ananchuen和Hummer的一個(gè)猜想的證明，證明了如下結(jié)果：假設(shè)G是一個(gè)3．控制邊臨界圖，七是一個(gè)正整數(shù)，七和圖的頂點(diǎn)數(shù)同奇偶，如果這個(gè)圖是k．連通的無爪圖且最小度至少為k+1，那么G是缸因子臨界的。第四章，我們介紹了一些在其他控制參數(shù)下的臨界圖及其這方面的研究結(jié)果。關(guān)鍵詞：控制、控制點(diǎn)臨界圖、控制邊臨界圖、哈密頓圈、完美匹配、近似完美匹配、因子臨界、直徑臨界圖AbstractDominationtheoryisanimportantbranchofthegraphtheory,itcanbeusedinthecomputerscience，n
5、etworks，societystudyandSOon．Withthedevelopmentofcom-purerscienceandnetworks，thedominationtheoryhasmadeimportantgrowth．ThedominationproblemisNP-C，SOthestudyofdominationisveryhard．Forthedomi—nationnumber,itmaydecrease，increaseorequaltotheodgiIlalvaluebyremovingavertexfromagraph．Ifther
6、emovalofanyvertexfromthegraphdecTeasethedomina-tionnumber,thenthegraphiscalleddominationvertexcritical．Butfortheadditionofanedgetoagraph，thedominationnumberCanonlybedecreased,Orequaltotheone．Iftheadditionofanyedgedec他粼thedominationnumber,wecallthegraphdominationedgecritical．Inthisdi
7、ssertation。weconcentrateonthedominationVertexcriticalanddominationedgecriticalgraphsfordominationnumber3．In1983，Sumnerinitiatedthestudyofdominationedgecriticalgraphsresearch；in1984．Brighameta1．beganthestudyofdominationvertexcriticalgraphs．ForthesetWOclassesofgraphs，thecharacterizati
8、onofthemfor7S2iseas
