本文關鍵詞：圖中具有特定條件的點不交的圈

  更多相關文章： 圖 圈 點不交 二分圖

【摘要】：本文主要介紹圖中具有特定條件的點不交的圈。圖G中含有k個頂點的路或圈分別記為k-路或k-圈。若一條路(或一個圈)包含圖G的全部頂點,則稱這條路(或這個圈)為G的Hamilton(哈密爾頓)路(或Hamilton圈)。圖中點不交的圈的問題是著名的Hamilton圈理論的一個推廣。Catlin (Ph. D.Dissertation.Ohio State University,1976),Aiger,Brandt(J.London Math.Soc,1993,48(2):39-51)和Alon(Discrete Math.,1996,152(1):13-23)分別給出了圖中含點不交的圈的度條件。1984年,El-Zahar給出了下列猜想：設G是一個含有n=n1+n2+…+nk(ni≥3,1≤i≤k)個頂點的簡單圖,若則G包含κ個點不交的圈C1,C2,…,Ck,其長度分別為n1,n2,…,nk.此猜想至今未得到解決。但是El-Zahar在同一篇論文中證明了k=2時的情況：設G是一個含有n=n1+n2個頂點的簡單圖,若則G包含兩個點不交的圈C1,C2,其長度分別為n1,n2。2009年,Gao,Yan和Li(J.Appl.Math.Comput.2009,31:203-215)給出了二分圖中包含特定點的點不交的圈問題的度條件。本文中證明了如下結果：結果1：設G是一個含有n個頂點的簡單圖,若對G中任意兩個不相鄰的點x,y,有d(x)+d(y)≥n+4,則對任意的(n1,n2),ni≥2,n=n1+n2,G包含兩個點不交的圈C1,C2,其長度分別為n1,n2。結果2：設k是一個正整數(shù),G是一個含有n≥4k個頂點的簡單圖。若對于G中任意一對不相鄰的點x,y有max{d(x),d(y)}≥2k,則G包含κ點不交的圈。結果3：令G=(V1,V2,E)是一個二分圖,|V1|=|V2|=n≥2k+1,其中k≥1是一個整數(shù)。若對G中任意兩個不相鄰的點x∈V1,y∈V2,有d(x)+d(y)≥n+k,則對G中的任意k個不同的點v1,v2,…,vk,G都包含k-1個點不交的4-圈C1,C2,…,Ck-1和一條含有2t個頂點的路Pk,其中t=n-2(k-1),使得每個圈和路Pk中都包含一個特定的點。結果4：令G=(V1,V2,E)是一個二分圖,|V1|=|V2|=n≥2k+1,其中k≥1是一個整數(shù)。若對G中任意兩個不相鄰的點x∈V1,y∈V2,有d(x)+d(y)≥n+k,則對G中的任意k個不同的點v1,v2,…,vk,G都包含k個點不交的圈C1,C2,…,Ck,使得每個圈中都包含一個特定的點,并且這k個圈中有k-1個是4-圈。
【關鍵詞】：圖 圈 點不交 二分圖
【學位授予單位】：山東大學
【學位級別】：碩士
【學位授予年份】：2016
【分類號】：O157.5
【目錄】：

• 中文摘要6-8
• 英文摘要8-10
• 符號說明10-11
• 第一章 前言11-21
• §1.1 基本概念11-13
• §1.2 圖中的圈理論的發(fā)展13-21
• 第二章 圖中的2-因子21-29
• §2.1 主要結果21-22
• §2.2 相關引理22-26
• §2.3 定理2.1.1的證明26-29
• 第三章 圖中點不交的圈29-38
• §3.1 預備知識及定理29-30
• §3.2 相關引理30-33
• §3.3 定理3.1.1的證明33-38
• 第四章 二分圖中點不交的圈38-50
• §4.1 預備知識及定理38-40
• §4.2 相關引理40-43
• §4.3 定理的證明43-50
• 參考文獻50-54
• 致謝54-55
• 已完成和發(fā)表的論文55-56
• 學位論文評閱及答辯情況表56

【相似文獻】

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

1 楊宏晨;關于k-消去二分圖的一些結果[J];數(shù)學的實踐與認識;2003年11期

2 楊宏晨,薛秀謙;二分圖為k-消去圖的 2個條件(英文)[J];Journal of Southeast University(English Edition);2003年02期

3 李峰;耿建艷;李碩;梁峰;;一種用4-圈和8-圈對二分圖的劃分[J];山東大學學報(理學版);2008年06期

4 王宏祥,蘇磊,車文剛;二分圖的無關分解[J];云南工業(yè)大學學報;1998年01期

5 車軍領;關于二分圖的2-因子[J];山東師大學報(自然科學版);2000年03期

6 錢建波;二分圖中k-因子存在的兩個充分條件[J];山東大學學報(自然科學版);2001年04期

7 顏謹;二分圖中相互獨立的圈[J];山東大學學報(理學版);2002年05期

8 石建軍;何大韌;;二分圖的投影、邊權及點強度[J];商丘師范學院學報;2009年09期

9 汪小玲;;滿足某些不等式條件的置換與二分圖[J];西南師范大學學報(自然科學版);2010年03期

10 周磊;支蓉;馮愛霞;龔志強;;基于二分圖的溫度網(wǎng)絡拓撲性質(zhì)研究[J];物理學報;2010年09期

中國重要會議論文全文數(shù)據(jù)庫 前2條

1 楊楠;丁暉;劉悅;;Web社區(qū)緊密核的抽取方法[A];NDBC2010第27屆中國數(shù)據(jù)庫學術會議論文集(B輯)[C];2010年

2 付春花;劉愛芬;陳卓輝;何大韌;;合作-競爭網(wǎng)絡的二分圖描述建議[A];中國數(shù)學力學物理學高新技術交叉研究學會第十二屆學術年會論文集[C];2008年

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

1 高云澍;圖中存在獨立圈及指定條件因子的度條件[D];山東大學;2009年

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

1 朱文;基于時序二分圖的優(yōu)化派工方法研究及Web實現(xiàn)[D];南京理工大學;2015年

2 張紹華;圖中具有特定條件的點不交的圈[D];山東大學;2016年

3 魯富榮;二分圖的因子[D];山西大學;2007年

4 劉瓊;包含大圈的2-因子在二分圖中的存在性[D];江西師范大學;2007年

5 朱瑯;基于二分圖的查詢推薦算法[D];安徽大學;2014年

6 鄭思遠;基于二分圖的混合推薦系統(tǒng)的研究與實現(xiàn)[D];北京郵電大學;2015年

7 李改枝;基本極大（m+1）K_2-free二分圖[D];河南大學;2009年

8 蔡瑩瑩;基于二分圖的應急預案體系有效性研究[D];大連理工大學;2012年

9 李金娜;關于圖的[k，，k+1]-因子的若干結果[D];東北大學;2006年

10 李峰;圖的獨立圈和2-因子理論的幾個最新結果[D];山東大學;2009年

本文編號：724964