圖論是以圖作為研究對象,以探究事物以及事物之間關(guān)系為研究目的,且有著豐富的歷史背景和實用價值的一門的數(shù)學(xué)學(xué)科。隨著信息技術(shù)的不斷突破以及各學(xué)科之間的交叉融合,圖論的發(fā)展進(jìn)入到了一個新時代。它不僅僅在蛋白質(zhì)結(jié)構(gòu)的研究、交通網(wǎng)絡(luò)圖的繪制、電路圖的設(shè)計、計算機(jī)編程等方面有著廣泛的應(yīng)用,在邏輯學(xué)、語言學(xué)、通訊網(wǎng)絡(luò)等領(lǐng)域的應(yīng)用也尤為突出,應(yīng)用范圍不斷的拓廣�？刂茊栴}一直是圖論領(lǐng)域的研究熱點。已有結(jié)論表明圖的控制數(shù)問題是一類NP—完備問題,因此探究出圖的控制數(shù)的精確值或者控制數(shù)較好的上下界具有重大的理論意義。本文以圖的強(qiáng)羅馬控制數(shù)和意大利控制數(shù)作為研究對象,針對一些特殊圖上的強(qiáng)羅馬控制數(shù)和意大利控制數(shù)的界及性質(zhì)進(jìn)行深入的研究和討論,主要工作包括:首先,概述了圖論的起源和發(fā)展歷程,闡述了圖的羅馬控制、強(qiáng)羅馬控制和意大利控制問題的研究背景、研究現(xiàn)狀以及研究意義,并給出了一些有關(guān)符號和定義。其次,利用歸納法對完全圖的刺圖、扇圖的中間圖、完全二部圖等特殊圖上的強(qiáng)羅馬控制數(shù)進(jìn)行數(shù)學(xué)推導(dǎo),得出了這些特殊圖的強(qiáng)羅馬控制數(shù)的上界,驗證了“對所有n ≥3的連通圖G有γStR（G）≤6n/7成立”的猜想在這部分特殊圖... 

【文章來源】：大連海事大學(xué)遼寧省 211工程院校

【文章頁數(shù)】：45 頁

【學(xué)位級別】：碩士

【部分圖文】：

圖２．?３扇圖的中間圖??Ｆｉｇ．?２．３?Ｍｉｄｄｌｅ?ｇｒａｐｈ?ｏｆ?ｆａｎ?ｇｒａｐｈ??

?關(guān)于特殊圖上的兩類控制數(shù)的研究???Ｖ〇?ｖｏ??（？）?Ｆ４?（Ａ）?Ｍ｛Ｆ４）??圖２．?３扇圖的中間圖??Ｆｉｇ．?２．３?Ｍｉｄｄｌｅ?ｇｒａｐｈ?ｏｆ?ｆａｎ?ｇｒａｐｈ??格子圖ｔ３％兩個路徑圖分別為ｇ?＝?ｐ？，和／／?＝?ｐ？，它們的笛卡爾乘積圖稱為〃＾？的??格子圖，記做乂．？。??并圖ｉ３６］：若圖ｇ，和圖ｇ２不相交，且組合的圖形的頂點集合與邊集合分別滿足??以ＧｊＵＫｑ）與五（ＧｊＵＭＧ），則組合后的圖形稱為圖Ｇ，和圖Ｇ２的并圖。由Ｐ個圖??Ｇ共用一個頂點的并圖記作圖ｉ＼ｃ［３６ｌ。??雙星：僅有兩個非葉子結(jié)點的樹。兩個支撐頂點上分別連接；？，ｇ個葉子頂點的??雙星圖記作??符號壞和分別對應(yīng)表示星圖４的剖分圖和雙星圖的剖分圖，也稱為剖??分星和剖分雙星。當(dāng)？為大于等于２的正整數(shù)時，圖也被稱為健康的蜘蛛圖，當(dāng)星??圖內(nèi)的剖分邊的數(shù)目至多為時，則稱此時的剖分星圖；為病態(tài)的蜘蛛圖或者??受傷的蜘蛛圖。在圖中，若＜ｖ）?＝?（則稱頂點ｖ為蜘蛛圖的頭頂點，所有滿足條件??出麵…，ｖ）二２的頂點《被稱為蚨丨蛛圖的腳頂點，如圖２．４所示。??圖２．?４蜘蛛圖??Ｆｉｇ．?２．４?Ｓｐｉｄｅｒ?ｇｒａｐｈ??－１２－??


本文編號：3345404