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

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

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

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

【部分圖文】：

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

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


本文編號(hào)：3345404