本文關(guān)鍵詞：k元n方體和OTG圖的H-強(qiáng)迫數(shù)

  更多相關(guān)文章： H-強(qiáng)迫集 H-強(qiáng)迫數(shù) k元n方體 Ore定理 弱閉包

【摘要】：在圖理論中,哈密爾頓圈問(wèn)題一直是人們重點(diǎn)關(guān)注的問(wèn)題.G的一個(gè)圈稱(chēng)為哈密爾頓圈,如果它包含G中所有點(diǎn).圖G稱(chēng)為一個(gè)哈密爾頓圖如果它包含一個(gè)哈密爾頓圈.若G是一個(gè)哈密爾頓圖,對(duì)于非空頂點(diǎn)集X(?)V(G),如果每個(gè)包含X的圈都是哈密爾頓圈,則X稱(chēng)為G的H-強(qiáng)迫集.最小的H-強(qiáng)迫集的頂點(diǎn)個(gè)數(shù)稱(chēng)為G的H-強(qiáng)迫數(shù).H-強(qiáng)迫數(shù)和H-強(qiáng)迫集這兩個(gè)概念是由I.Fabrici等人在2009年提出的概念.因?yàn)檫@個(gè)概念對(duì)于研究圖的哈密爾頓性有重要意義,所以這一概念一經(jīng)提出就引起了人們的廣泛關(guān)注.k元n方體,是一種特殊的拓?fù)渚W(wǎng)絡(luò)模型,記為Qkn(k≥1,n≥1)它有kn個(gè)頂點(diǎn),每個(gè)頂點(diǎn)可以記為u=un-1un-2...u0,其中ui∈{0,1,...k-1},0≤i≤n-1.頂點(diǎn)u=un-1un-2...u0和頂點(diǎn)u=un-1un-2...u0相鄰當(dāng)且僅當(dāng)存在一個(gè)整數(shù)J,0≤j≤n-1,使得uj=uj±1(mod k)且對(duì)每個(gè)i∈{0,1,...,j-1,j+1,...,n-1}都有ui=vi.對(duì)于G中每一對(duì)不相鄰的頂點(diǎn)u,v,如果d(u)+d(u)≥n,則稱(chēng)G滿足了Ore定理的條件.為了方便,用OTG表示一個(gè)滿足Ore定理?xiàng)l件的圖.Ore證明了任意一個(gè)OTG都是哈密爾頓圖.本文研究的是網(wǎng)絡(luò)拓?fù)鋱Dk元n方體Qkn和OTG圖的H-強(qiáng)迫集和H-強(qiáng)迫數(shù),通過(guò)分析圖形結(jié)構(gòu)及分類(lèi)歸納來(lái)得到結(jié)論.本文分為四章.第一章是緒論,介紹了本文的研究背景及相關(guān)結(jié)論.第二章是基本概念,介紹了本文將要用到的術(shù)語(yǔ)和概念.第三章通過(guò)研究Cm×Cn的H-強(qiáng)迫數(shù),得出網(wǎng)絡(luò)拓?fù)鋱Dk元n方體Qnk的H-強(qiáng)迫數(shù).分別得到三個(gè)主要的結(jié)論：(i)設(shè)G=Cm×Cn(m2,n2),則(ii)設(shè)G=Qkn(n≥2,k2),則(iii)設(shè)G=Pn×Pn (n≥4,且n為偶數(shù)),則h(G)=n2/2-2.第四章研究了OTG圖的H-強(qiáng)迫數(shù)和最小H-強(qiáng)迫集.通過(guò)研究這類(lèi)圖的弱閉包得到這一類(lèi)圖的H-強(qiáng)迫數(shù)為n或n-2或n/2,并由此給出了這類(lèi)圖的一個(gè)劃分,得到了下面的結(jié)論：設(shè)G是一個(gè)OTG且有n≥5個(gè)頂點(diǎn),X是G的最小H-強(qiáng)迫集.令Cω(G)是G的弱閉包,S是Cω(G)的最大獨(dú)立集.則(1)H-強(qiáng)迫數(shù)h(G)=n-2或n/2或n.(2)其中x,y ∈V(G)且dCw(G)(x)=n-1,dCw(G)(y)=n-1.
【關(guān)鍵詞】：H-強(qiáng)迫集 H-強(qiáng)迫數(shù) k元n方體 Ore定理 弱閉包
【學(xué)位授予單位】：山西大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類(lèi)號(hào)】：O157.5
【目錄】：

• 中文摘要6-8
• Abstract8-10
• 第一章 緒論10-12
• 第二章 基本概念12-15
• 第三章 k元n方體Q_n~k的H-強(qiáng)迫數(shù)15-23
• §3.1 準(zhǔn)備知識(shí)15-16
• §3.2 主要結(jié)論16-19
• §3.3 其他結(jié)論19-23
• 第四章 OTG圖的H-強(qiáng)迫數(shù)23-36
• §4.1 準(zhǔn)備知識(shí)23-25
• §4.2 主要結(jié)論25-36
• 參考文獻(xiàn)36-38
• 研究成果38-39
• 致謝39-41
• 個(gè)人簡(jiǎn)況及聯(lián)系方式41-42
• 承諾書(shū)42-43

【共引文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前10條

1 白亞蘭;師海忠;;完全二叉樹(shù)到星連通圈網(wǎng)絡(luò)的嵌入[J];甘肅科學(xué)學(xué)報(bào);2014年03期

2 楊玉星;王世英;;k元n立方網(wǎng)絡(luò)的k圈排除問(wèn)題的遞歸算法[J];計(jì)算機(jī)應(yīng)用;2013年09期

3 李瑞娟;張文娟;;圈和路的笛卡爾積的H-強(qiáng)迫數(shù)[J];中北大學(xué)學(xué)報(bào)(自然科學(xué)版);2013年05期

4 周后卿;周琪;;循環(huán)圖的Kirchhoff指標(biāo)[J];華中師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2014年02期

5 張淑蓉;王世英;董操;;邊故障k元n立方體的超級(jí)哈密頓交織性[J];計(jì)算機(jī)工程與應(yīng)用;2014年21期

6 鄭麗麗;李海東;;折疊超立方體網(wǎng)絡(luò)的自適應(yīng)診斷[J];河南工程學(xué)院學(xué)報(bào)(自然科學(xué)版);2014年04期

7 高珊;;匹配組合網(wǎng)絡(luò)的寬直徑[J];湖北大學(xué)學(xué)報(bào)(自然科學(xué)版);2015年01期

8 張國(guó)珍;;單向k-元n-立方體網(wǎng)絡(luò)[J];計(jì)算機(jī)工程與應(yīng)用;2015年20期

9 李瑞娟;李麗;;兩類(lèi)圖的H-強(qiáng)迫數(shù)[J];山西大學(xué)學(xué)報(bào)(自然科學(xué)版);2013年04期

10 張欣;師海忠;;交叉立方體連通圈網(wǎng)絡(luò)的Hamilton分解[J];軟件;2015年08期

中國(guó)博士學(xué)位論文全文數(shù)據(jù)庫(kù) 前6條

1 王巖;扭立方體和奇偶立方體上獨(dú)立生成樹(shù)的嵌入研究[D];蘇州大學(xué);2014年

2 沈華;基于Petri網(wǎng)的Web服務(wù)組合性能評(píng)價(jià)體系的研究[D];武漢大學(xué);2013年

3 王凡;超立方中匹配的哈密爾頓圈擴(kuò)張問(wèn)題的研究[D];蘭州大學(xué);2014年

4 洪振木;某些網(wǎng)絡(luò)可靠性和有效性研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2014年

5 劉艷霞;基于代數(shù)圖論的復(fù)雜網(wǎng)絡(luò)的拓?fù)湫再|(zhì)和構(gòu)造方法研究[D];華南理工大學(xué);2013年

6 程冬琴;若干互連網(wǎng)絡(luò)的圈嵌入和路嵌入[D];北京交通大學(xué);2015年

中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫(kù) 前10條

1 程文英;（n，κ）-星圖的條件邊容錯(cuò)哈密爾頓性[D];湖北大學(xué);2013年

2 蔡紅艷;泡型星圖的局部連通性及匹配排除[D];湖北大學(xué);2013年

3 張娟;兩類(lèi)網(wǎng)絡(luò)有關(guān)條件邊連通性的研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2014年

4 李佳傲;整數(shù)5-流及相關(guān)問(wèn)題研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2014年

5 閆小艷;星圖互連網(wǎng)絡(luò)的最小邊界和可靠性研究[D];西安電子科技大學(xué);2014年

6 陳光永;某些圖類(lèi)的k-距離控制數(shù)與K-距離約束數(shù)[D];中國(guó)科學(xué)技術(shù)大學(xué);2014年

7 喻雪榮;三角金字塔網(wǎng)的若干性質(zhì)[D];浙江師范大學(xué);2014年

8 王培艷;某些網(wǎng)絡(luò)的容錯(cuò)性及條件容錯(cuò)性[D];北京交通大學(xué);2014年

9 朱文慧;五類(lèi)變換圖的圈邊連通性[D];湖北師范學(xué)院;2014年

10 李小燕;兩類(lèi)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的可靠性評(píng)估[D];福建師范大學(xué);2014年

，

本文編號(hào)：885050