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

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

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

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

【共引文獻】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

10 李小燕;兩類網(wǎng)絡(luò)拓撲結(jié)構(gòu)的可靠性評估[D];福建師范大學(xué);2014年

，

本文編號：885050