版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、圖的哈密頓問題是圖論中一個十分重要且又十分活躍的研究課題,每年都有大量的關(guān)于這一問題的學術(shù)論文。1857年,愛爾蘭數(shù)學家哈密頓提出:“一個連通圖有哈密頓圈的充要條件是什么?”這樣一個問題。但是這個問題至今仍未能解決。后來人們發(fā)現(xiàn)它是一個NPC問題,于是降低要求間接研究該問題。與此同時,以Hamilton問題為出發(fā)點發(fā)展起了對圖的圈性質(zhì)的研究,這些性質(zhì)主要包括Hamilton性、泛圈性、完全圈可擴性等。我們知道圖的完全圈可擴性要比圖的泛圈
2、性更強,圖的泛圈性要比圖的哈密頓性更強,所以研究泛圈性和完全圈可擴性就研究了圖的Hamilton性。關(guān)于哈密頓性的研究及最新進展可見參考文獻[17]-[23]。關(guān)于泛圈性的研究及最新進展可見參考文獻[24]-[34],關(guān)于完全圈可擴性的研究及最新進展可見參考文獻[4]-[15]。對這些性質(zhì)的研究主要集中在兩方面,一方面是尋求這些圈性質(zhì)的充分條件,另一方面是研究某些特殊圖類的圈性質(zhì)。 本文主要討論了兩種特殊圖類中的圈性質(zhì)的問題。一
3、種圖類是[s,t]-圖,劉春房最早提出了[s,t]-圖的概念并進行研究的。對[s,t]-圖的研究有著深刻的應(yīng)用價值,很典型的一個應(yīng)用就是在計算機的網(wǎng)絡(luò)配置上。另一種圖類是高連通度圖。這里的高連通度是指一個圖的連通度相對圖的階是較高的。當一個圖的連通度足夠高時,這個圖可以保證圖的各種圈性質(zhì),那么隨著圖的連通度的降低,圖的圈性質(zhì)將發(fā)生什么變化呢?本文就此討論了高連通度圖的完全圈可擴性。為方便討論,在第三章中提出了s-點連通圖的概念,即連通度
4、為κ(G)=|G|-s+1的圖。在此基礎(chǔ)上主要討論了5-點連通圖,6-點連通圖的完全圈可擴性,即連通度分別為|G|-4和|G|-5的高連通度圖的完全圈可擴性。根據(jù)所得結(jié)果提出了s-點連通圖(κ(G)=|G|-s+1)在完全圈可擴性方面的一個猜想。在第三章最后給出例子說明定理及猜想中對圖G的階的限制是最好可能的。 本文的主要內(nèi)容包括三章。在第一章中,我們主要介紹了文章中所涉及的一些概念、術(shù)語符號和本文的研究背景及已有的結(jié)果;在第二
5、章中,我們討論了2-連通[4,2]-圖中的圈;在第三章中,我們討論了高連通度圖的完全圈可擴性并提出猜想。 我們得到的主要結(jié)果如下:定理2.1.1設(shè)G是2-連通[4,2]-圖,C是G中滿足|V(C)|<|V(G)|的任一圈,則或者G中有(|C|+1)-圈,或者G同構(gòu)于K2,3,K1,1,3,F(xiàn)1,F(xiàn)2,F(xiàn)3,F(xiàn)4,F(xiàn)5。(其中F1,F(xiàn)2,F(xiàn)3,F(xiàn)4,F(xiàn)5如下圖)推論3.1.1設(shè)G為4-點連通圖且|G|≥7,則G是完全圈可擴的。定理
6、3.1.1設(shè)G為5-點連通圖且|G|≥9,則G是完全圈可擴的。定理3.1.1′設(shè)G滿足κ(G)=|G|-4且|G|≥9,則G是完全圈可擴的定理3.1.2設(shè)G為6-點連通圖且|G|≥11,則G是完全圈可擴的。定理3.1.2′設(shè)G滿足κ(G)=|G|-5且|G|≥11,則G是完全圈可擴的。由上述定理提出下面的猜想猜想3.1.1設(shè)G為s-點連通圖且|G|≥2s-1,則G是完全圈可擴的。 猜想3.1.1′設(shè)G滿足κ(G)=|G|-s+1
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 圖的連通度與其路圈可擴性.pdf
- [s,t]-圖的Hamilton性及幾乎局部連通條件下[4,2]-圖的完全圈可擴.pdf
- 1-可擴圖與圈邊連通度的有效判定算法.pdf
- 畢業(yè)論文2連通4,2圖中的圈以及含有hamilton圈的一個充分條件的再證明
- 連通圖中可去邊和圈的研究.pdf
- 連通度,H-局部連通與[s,l]-圖的路圈性質(zhì).pdf
- 關(guān)于一類圖的可圈性與強連通可推性.pdf
- 關(guān)于正則圖的圈邊連通度判定算法.pdf
- 關(guān)于正則圖的圈邊連通度判定算法
- 雙圈圖的代數(shù)連通度的分類排序.pdf
- 4-連通平面圖中的圈及邊著色問題的研究.pdf
- 圖的泛圈性和泛連通性.pdf
- 完全多部圖的廣義連通度.pdf
- 2-連通圖的單圈子圖.pdf
- κ-連通圖中最長圈上可收縮邊數(shù)目.pdf
- 21645.4連通圖中最長圈上弦的存在性與可去邊的關(guān)系
- k-連通圖中最長圈及余直徑研究.pdf
- H-局部連通圖的路圈性質(zhì).pdf
- Johnson圖的連通度、割集和哈密爾頓圈.pdf
- 若干h局部連通圖的路和圈問題
評論
0/150
提交評論