版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、競(jìng)賽圖無(wú)疑是有向圖中一類非常重要的圖,并且它已經(jīng)被廣泛研究.關(guān)于競(jìng)賽圖中有向路和有向圈問(wèn)題的研究非常深入而且成果豐碩.稱有向圖D是泛圈的,如果它包含從3到|V(D)|的每個(gè)長(zhǎng)度的圈.稱有向圖D的一個(gè)頂點(diǎn)(一條?。┦莐泛的,如果它屬于每個(gè)l-圈(k≤l≤|V(D)|).當(dāng)k=3時(shí),也稱該頂點(diǎn)(?。┦欠喝Φ?稱有向圖D是頂點(diǎn)泛圈(弧泛圈)的,如果它的每個(gè)頂點(diǎn)(?。┦欠喝Φ?對(duì)某個(gè)k∈{3,4,…,|V(D)|},稱有向圖D是弧-k-圈的,如
2、果D的每條弧都包含在一個(gè)長(zhǎng)為k的圈中.顯然,有向圖D是弧泛圈的當(dāng)且僅當(dāng)對(duì)每個(gè)k=3,4,…,|V(D)|,它是弧-k-圈的.目前,在競(jìng)賽圖的泛圈性、頂點(diǎn)泛圈性及弧泛圈性方面已有了很多結(jié)果.有向圖D的一條從頂點(diǎn)x出發(fā)的弧被稱為是x的一條外弧.如果一個(gè)頂點(diǎn)的所有外弧在D中都是k泛的,則稱這個(gè)頂點(diǎn)是外弧k泛頂點(diǎn).當(dāng)k=3時(shí),也稱該頂點(diǎn)是外弧泛圈頂點(diǎn).2000年,Yao,Guo和Zhang首次對(duì)競(jìng)賽圖中頂點(diǎn)的外弧泛圈性作了討論,證明了強(qiáng)競(jìng)賽圖中
3、外弧泛圈頂點(diǎn)的存在性.本文主要研究強(qiáng)競(jìng)賽圖中頂點(diǎn)的外弧泛圈性問(wèn)題.
本文共分五章.第一章介紹了有向圖中的一些相關(guān)的基本概念以及論文內(nèi)容的安排.
第二章回顧了競(jìng)賽圖中的一些相關(guān)結(jié)果.
第三章研究了強(qiáng)競(jìng)賽圖中外弧泛圈頂點(diǎn)的個(gè)數(shù).在2000年,Yao,Guo和Zhang證明了每個(gè)強(qiáng)競(jìng)賽圖T都包含一個(gè)外弧泛圈頂點(diǎn).同時(shí)他們提出一個(gè)猜想:每個(gè)k-強(qiáng)競(jìng)賽圖至少存在k個(gè)這樣的頂點(diǎn).現(xiàn)在已經(jīng)證明了該猜想對(duì)k=1,2,3是對(duì)
4、的.然而,由于Yeo給出的下面的例子,這個(gè)猜想對(duì)k≥4是不成立的.設(shè)T1,T2和T3都是階至少為k的可遷競(jìng)賽圖.T是在Ti之間添加弧得到的一個(gè)競(jìng)賽圖,使得T1(→)T2(→)T3(→)T1.顯然T是k-強(qiáng)的.由于Ti中的任何一條弧都不在T的一個(gè)3-圈中,所以僅有在每個(gè)Ti(i=1,2,3)中出度為零的頂點(diǎn)是T的外弧泛圈頂點(diǎn).但是Yeo提出的下列猜想可能是正確的:每個(gè)2-強(qiáng)競(jìng)賽圖至少包含3個(gè)外弧泛圈頂點(diǎn).在3.2節(jié),我們證明了Yeo的猜想
5、是成立的.另外,對(duì)于最小出度為1的強(qiáng)競(jìng)賽圖,Yao等人找到一個(gè)強(qiáng)競(jìng)賽圖的無(wú)限類使得其中每個(gè)強(qiáng)競(jìng)賽圖恰包含一個(gè)外弧泛圈頂點(diǎn).那么我們自然要問(wèn):對(duì)于最小出度至少為2的強(qiáng)競(jìng)賽圖包含幾個(gè)外弧泛圈頂點(diǎn)呢?在3.3節(jié),我們證明了連通度為1且最小出度至少是2的強(qiáng)競(jìng)賽圖也至少包含3個(gè)外弧泛圈頂點(diǎn),并舉例說(shuō)明了這個(gè)結(jié)果的最佳可能性.結(jié)合3.2和3.3節(jié)的這兩個(gè)結(jié)論,我們得到具有最小出度至少是2的強(qiáng)競(jìng)賽圖至少包含3個(gè)外弧泛圈頂點(diǎn).
第四章研究了恰
6、有3個(gè)外弧泛圈頂點(diǎn)的強(qiáng)競(jìng)賽圖.Yeo在2005年給出一類例子說(shuō)明對(duì)任意的正整數(shù)k,存在一類k-強(qiáng)競(jìng)賽圖,使得其中每個(gè)競(jìng)賽圖至多包含3個(gè)外弧泛圈頂點(diǎn).那么除了這類例子以外,是否k-強(qiáng)競(jìng)賽圖就包含k外弧泛圈頂點(diǎn)?本章中,我們給出了恰有3個(gè)外弧泛圈頂點(diǎn)的5-強(qiáng)競(jìng)賽圖的一個(gè)必要條件,證明了恰有3個(gè)外弧泛圈頂點(diǎn)的5-強(qiáng)競(jìng)賽圖是某一類圖中的成員.設(shè)T1,T2和T3都是階為k≥5的強(qiáng)競(jìng)賽圖,滿足u,v1和w1分別是T1,T2和T3中出度為零的頂點(diǎn),且
7、有(V(T1)-{u})→u,(V(T2)-{v1})→v1及(V(T3)-{w1})→w1.設(shè)T4是一個(gè)競(jìng)賽圖.令T0是在Ti(i=1,2,3,4)之間添加弧得到的所有強(qiáng)競(jìng)賽圖的集合,使得T1(→)T2(→)T3(→)T1且T4中的每個(gè)頂點(diǎn)都控制{u,v1,w1},其它的弧任意定向.設(shè)T是一個(gè)恰包含3個(gè)外弧泛圈頂點(diǎn)的5-強(qiáng)競(jìng)賽圖,則T是T0中的一個(gè)成員.我們的結(jié)果表明,除T0以外,5-強(qiáng)競(jìng)賽圖一定包含4個(gè)外弧泛圈頂點(diǎ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ì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 多部競(jìng)賽圖中包含指定頂點(diǎn)的路和強(qiáng)子競(jìng)賽圖.pdf
- 26853.競(jìng)賽圖的外弧泛圈性及一類特殊圖的泛路問(wèn)題
- 局部競(jìng)賽圖的外弧泛圈點(diǎn).pdf
- 多部競(jìng)賽圖和強(qiáng)競(jìng)賽圖中的圈和路問(wèn)題
- 多部競(jìng)賽圖和強(qiáng)競(jìng)賽圖中的圈和路問(wèn)題.pdf
- 特殊圖中頂點(diǎn)無(wú)交的三圈、四圈問(wèn)題.pdf
- 多部競(jìng)賽圖的(擬)外弧泛圈點(diǎn)問(wèn)題.pdf
- 強(qiáng)競(jìng)賽圖的外孤4泛圈點(diǎn)問(wèn)題
- 強(qiáng)競(jìng)賽圖的外孤4泛圈點(diǎn)問(wèn)題.pdf
- 正則多部競(jìng)賽圖中的圈.pdf
- 多部競(jìng)賽圖中的圈和外路
- 圖的泛圈性和點(diǎn)泛圈性.pdf
- 多部競(jìng)賽圖中包含在圈中的孤.pdf
- 6789.多部競(jìng)賽圖中的圈和外路
- 圖的泛圈性和泛連通性.pdf
- 網(wǎng)絡(luò)的容錯(cuò)泛圈性研究.pdf
- 圖中的圈和網(wǎng)絡(luò)可靠性參數(shù).pdf
- 圖包含指定長(zhǎng)度的圈和泛弧問(wèn)題的研究.pdf
- 有向圖中的泛路問(wèn)題.pdf
- 圖中的圈及其相關(guān)問(wèn)題.pdf
評(píng)論
0/150
提交評(píng)論