版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、隨著大型計(jì)算機(jī)的出現(xiàn)和計(jì)算機(jī)科學(xué)的迅速發(fā)展,特別值得一提的是計(jì)算機(jī)網(wǎng)絡(luò)的出現(xiàn)和發(fā)展,大大地促進(jìn)了圖論的發(fā)展和繁榮,無(wú)論在數(shù)學(xué),物理,化學(xué),生物等基礎(chǔ)學(xué)科,還是在交通運(yùn)輸,計(jì)算機(jī)科學(xué),系統(tǒng)工程等應(yīng)用領(lǐng)域,圖論都顯示出越來(lái)越重要的作用,因而研究圖論問(wèn)題及其解法具有重要的理論和實(shí)際意義。 本文主要研究了二分圖的哈密頓[k,k+1]-因子與其頂點(diǎn)度之間的關(guān)系。第一章對(duì)研究的背景和現(xiàn)狀進(jìn)行了概述;第二章介紹了與研究有關(guān)的一些術(shù)語(yǔ)及記號(hào);第
2、三章重點(diǎn)研究二分圖中包含任意給定的哈密頓圈的[k,k+1]-因子的度條件。 自從1952年以來(lái),對(duì)圖的因子理論的研究進(jìn)展十分迅速,到現(xiàn)在已有很多的研究成果。圖的因子理論與很多圖論中的其它知識(shí)有關(guān),如圖的因子與堅(jiān)韌度之間有聯(lián)系。1971年,Chvatal提出了下面的猜想:若圖G是3/2-堅(jiān)韌的,則G有2-因子。該猜想至今未得到證實(shí)。圖的因子與其頂點(diǎn)度數(shù)之間也有緊密地聯(lián)系,1992年,T.Nishimura提出了下面的猜想:設(shè)G是一
3、個(gè)n階圖,對(duì)任意x,y∈V(G),如果x與y之間的距離dG(x,y)=2,且max{dG(x),dG(y)}≥n/2,n≥4k-3,kn為偶數(shù),則圖G有k-因子。該猜想也沒(méi)有完全解決,1997年錢建波證明了該猜想對(duì)二分圖成立,同年T.Niniessen證明了當(dāng)n≥8k2+12k+6時(shí)該猜想成立。1998年蔡茂誠(chéng)給出了:設(shè)G是一個(gè)n階圖,對(duì)不相鄰的兩個(gè)頂點(diǎn)x,y∈V(G),如果dG(x)+dG(y)≥n,則圖G中包含任意給定的哈密頓圈C的
4、[k,k+1]-因子。2002年,H.Matsuda[14]改進(jìn)為:設(shè)k為正整數(shù),且k≥2,G是階|G|≥3的2-連通圖,δ(G)≥k,對(duì)偶數(shù)|G|有|G|≥8k-16且對(duì)奇數(shù)|G|有|G|≥6k-13,如果G中每一對(duì)不相鄰的頂點(diǎn)x和y有max{dG(x),dG(y)}≥|G|/2則對(duì)G的任意哈密頓圈C,G有[k,k+1]-因子包含圈C。 本文給出了二分圖中包含任意給定的哈密頓圈C的[k,k+1]-因子的度條件,即:1.設(shè)G是頂
5、點(diǎn)數(shù)為n的均衡二分圖,且是n/4+1臨界圖,n≥8k-12,n≥12,k≥2,則對(duì)G的任意哈密頓圈C,G有[k,k+1]-因子包含圈C。 2.設(shè)k≥2,G=(X,Y,E)中,|X|=|Y|=n/2≥4(k-2)-1,n≥6,δ(G)≥k,k為正整數(shù)。如果G的每一對(duì)距離為2的頂點(diǎn)u,v有max{dG(u),dG(v)}≥n/4+2,則對(duì)G的任意哈密頓圈C,G有[k,k+1]-因子包含圈C。 3.設(shè)G=(X,Y,E),|X|
6、=|Y|=n/2≥4(k-2)-3,k≥2且n≥6,δ(G)≥k,若G中每一對(duì)不相鄰的頂點(diǎn)u,v有max{dG(x),dG(x)}≥n/4+2,則G有包含哈密頓圈C的[k,k+1]-因子。 4.設(shè)二分圖G=(X,Y,E),|X|=|Y|=n/2≥4(k-2)-3,k≥2且n≥6,δ(G)≥k,若G中每一對(duì)不相鄰的頂點(diǎn)u,v有dG(u)+dG(v)≥n/2+4,則G有包含哈密頓圈C的[k,k+1]-因子。 此度條件改進(jìn)了階
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 關(guān)于圖的因子和因子-覆蓋圖的若干結(jié)果.pdf
- 關(guān)于圖的因子與分?jǐn)?shù)因子的若干結(jié)果.pdf
- 關(guān)于圖的哈密頓因子的若干結(jié)果.pdf
- 關(guān)于反射對(duì)稱圖的若干結(jié)果.pdf
- 關(guān)于分?jǐn)?shù)消去圖的若干結(jié)果.pdf
- 關(guān)于(下)整和圖的若干結(jié)果.pdf
- 圖的哈密頓[a,b]-因子的若干結(jié)果.pdf
- 關(guān)于圖的可嵌入性的若干結(jié)果.pdf
- 關(guān)于圖的L(3,2,1)標(biāo)號(hào)的若干結(jié)果.pdf
- 關(guān)于Maass形式的若干結(jié)果.pdf
- 關(guān)于圖的對(duì)策染色數(shù)的若干結(jié)果.pdf
- 關(guān)于圖的導(dǎo)出匹配問(wèn)題的若干結(jié)果.pdf
- 關(guān)于sn網(wǎng)的若干結(jié)果.pdf
- 關(guān)于商環(huán)的若干結(jié)果.pdf
- 關(guān)于商s映象的若干結(jié)果.pdf
- 關(guān)于Stackelberg模型拓展的若干結(jié)果.pdf
- 關(guān)于D-空間的若干結(jié)果.pdf
- 關(guān)于變換半群的若干結(jié)果.pdf
- 關(guān)于約束最優(yōu)樹問(wèn)題的若干結(jié)果.pdf
- 關(guān)于素環(huán)李理想的若干結(jié)果.pdf
評(píng)論
0/150
提交評(píng)論