本文關鍵詞：k元n方體和OTG圖的H-強迫數

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

【摘要】：在圖理論中,哈密爾頓圈問題一直是人們重點關注的問題.G的一個圈稱為哈密爾頓圈,如果它包含G中所有點.圖G稱為一個哈密爾頓圖如果它包含一個哈密爾頓圈.若G是一個哈密爾頓圖,對于非空頂點集X(?)V(G),如果每個包含X的圈都是哈密爾頓圈,則X稱為G的H-強迫集.最小的H-強迫集的頂點個數稱為G的H-強迫數.H-強迫數和H-強迫集這兩個概念是由I.Fabrici等人在2009年提出的概念.因為這個概念對于研究圖的哈密爾頓性有重要意義,所以這一概念一經提出就引起了人們的廣泛關注.k元n方體,是一種特殊的拓撲網絡模型,記為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相鄰當且僅當存在一個整數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都是哈密爾頓圖.本文研究的是網絡拓撲圖k元n方體Qkn和OTG圖的H-強迫集和H-強迫數,通過分析圖形結構及分類歸納來得到結論.本文分為四章.第一章是緒論,介紹了本文的研究背景及相關結論.第二章是基本概念,介紹了本文將要用到的術語和概念.第三章通過研究Cm×Cn的H-強迫數,得出網絡拓撲圖k元n方體Qnk的H-強迫數.分別得到三個主要的結論：(i)設G=Cm×Cn(m2,n2),則(ii)設G=Qkn(n≥2,k2),則(iii)設G=Pn×Pn (n≥4,且n為偶數),則h(G)=n2/2-2.第四章研究了OTG圖的H-強迫數和最小H-強迫集.通過研究這類圖的弱閉包得到這一類圖的H-強迫數為n或n-2或n/2,并由此給出了這類圖的一個劃分,得到了下面的結論：設G是一個OTG且有n≥5個頂點,X是G的最小H-強迫集.令Cω(G)是G的弱閉包,S是Cω(G)的最大獨立集.則(1)H-強迫數h(G)=n-2或n/2或n.(2)其中x,y ∈V(G)且dCw(G)(x)=n-1,dCw(G)(y)=n-1.
【關鍵詞】：H-強迫集 H-強迫數 k元n方體 Ore定理 弱閉包
【學位授予單位】：山西大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：O157.5
【目錄】：

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

【共引文獻】

中國期刊全文數據庫 前10條

1 白亞蘭;師海忠;;完全二叉樹到星連通圈網絡的嵌入[J];甘肅科學學報;2014年03期

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

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

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

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

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

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

8 張國珍;;單向k-元n-立方體網絡[J];計算機工程與應用;2015年20期

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

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

中國博士學位論文全文數據庫 前6條

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

2 沈華;基于Petri網的Web服務組合性能評價體系的研究[D];武漢大學;2013年

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

4 洪振木;某些網絡可靠性和有效性研究[D];中國科學技術大學;2014年

5 劉艷霞;基于代數圖論的復雜網絡的拓撲性質和構造方法研究[D];華南理工大學;2013年

6 程冬琴;若干互連網絡的圈嵌入和路嵌入[D];北京交通大學;2015年

中國碩士學位論文全文數據庫 前10條

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

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

3 張娟;兩類網絡有關條件邊連通性的研究[D];中國科學技術大學;2014年

4 李佳傲;整數5-流及相關問題研究[D];中國科學技術大學;2014年

5 閆小艷;星圖互連網絡的最小邊界和可靠性研究[D];西安電子科技大學;2014年

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

7 喻雪榮;三角金字塔網的若干性質[D];浙江師范大學;2014年

8 王培艷;某些網絡的容錯性及條件容錯性[D];北京交通大學;2014年

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

10 李小燕;兩類網絡拓撲結構的可靠性評估[D];福建師范大學;2014年

，

本文編號：885050