版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、本文所考慮的圖都是簡單無向圖.設(shè)G=(V(G),E(G))是一個圖,其中V(G)和E(G)分別表示G的頂點集合和邊集合.頂點x在G中的度記為dG(x),δ(G)表示G中所有頂點度的最小值.對于任意的集合S(¢)V(G),由S導(dǎo)出的G的子圖記為G[S],G-S表示由V(G)\S導(dǎo)出的子圖.用o(G-S)和i(G-S)分別代表G-S中奇分支的個數(shù)和孤立頂點的個數(shù). 設(shè)g(x)≤f(x)是定義在V(G)上的兩個非負整數(shù)值函數(shù),H是G的
2、一個支撐子圖.如果對于任意的x∈V(G),滿足g(x)≤dH(x)≤f(x),則稱H是G的一個(g,f)-因子.類似的,如果對于任意的x∈V(G),滿足g(x)=f(x),則稱日是G的一個f-因子(或g-因子);如果對于任意的x∈V(G),有g(shù)(x)=a,f(x)=6且a,b是兩個正整數(shù),那么(g,f)-因子就可被稱為[a,b]-因子.特別的,對于任意的x∈V(G),有g(shù)(x)=f(x)=1時,(g,f)-因子就變成了1-因子,即完美匹
3、配. 設(shè)g(x)≤(x)是定義在V(G)上的兩個非負整數(shù)值函數(shù),h(e)∈[0,1]是-個定義在E(G)上的函數(shù)并且dhG(x)=∑e∈Exh(e),其中Ex={xy:xy∈E(G)}.此時dhG(x)被稱為是在h作用下的G中頂點x的分數(shù)度,h被稱為是一個指示函數(shù)(inditor fullction).如果對于任意的x∈V(G),有g(shù)(x)≤dhG(x)≤f(x),設(shè)Eh={e:e∈E(G),h(e)≠0}且Gh是G的一個支撐子
4、圖并使得E(Gh)=Eh,那么Gh就是G的一個分數(shù)-(g,f)-因子.同樣的方法可以類似的定義分數(shù)-k-因子、分數(shù)-[a,b]-因子等.特別的,對于任意的x∈V(G),有g(shù)(x)=f(x)=1時,分數(shù)-(g,f)-因子變?yōu)榉謹?shù)-1-因子,即分數(shù)完美匹配. 圖的因子理論是圖論中研究的主要問題之一.對因子理論的研究在一個多世紀以前就開始了,但直到上世紀七十年代才逐漸地活躍了起來.到目前為止,對圖的因子方面的研究已經(jīng)得到了不少成果.分
5、數(shù)圖論是相對年輕的分支,因此仍有許多問題有待解決. 本文共分為六大部分,第四部分和第五部分是整個文章的核心,通過分析證明得出了分數(shù)因子臨界圖和分數(shù)-(r,k)-可擴圖的一些結(jié)論. 第一部分是全文的基礎(chǔ)部分.簡要介紹了文中所涉及的概念、術(shù)語和符號,回顧了圖論及圖因子問題的發(fā)展史,并對圖因子問題中常用的重要參數(shù)作了詳細介紹. 第二部分概括總結(jié)了圖因子存在性問題中整數(shù)因子和分數(shù)因子已有的重要定理. 第三部分分析
6、概括出圖因子存在性問題中的兩種常用研究方法. 第四部分重點研究了分數(shù)因子臨界圖(設(shè)G是一個圖,若對于頂點集合V(G)的任意n-子集T使得G-T有分數(shù)-r-因子,則稱G是-個分數(shù)-(r,n)-因子-臨界圖)的一些性質(zhì),得出了以下結(jié)論: 設(shè)G是δ(G)≥r+n的圖且孤立韌度I(G)≥r+n-1/r.則G是一個分數(shù)-(r,n)-因子-臨界圖. 假設(shè)G是δ(G)≥r+n的圖.若G是分數(shù)-(r,n)-因子-臨界圖,則G也是
7、分數(shù)-(r,n-1)-因子-臨界圖. 如果對于任意的u∈V(G),G-{u}-有分數(shù)-r-因子,那么G同樣也有分數(shù)-r-因子.第五部分主要研究了分數(shù)-(r,k)-可擴圖(設(shè)G是一個圖,如果對于V(G)的任意r-子集T,G-T是一個分數(shù)-k-可擴圖,則G是一個分數(shù)-(r,k)-可擴圖)的一些性質(zhì),得出了以下結(jié)論: 圖G是一個分數(shù)-(r,k)-可擴圖當(dāng)且僅當(dāng)對于任意的集合U∈V(G),有i(G-U)≤U-2K-r.其中,|U
8、|≥2k+r且G[U]包含一個k-匹配. 任意—個分數(shù)-(r,k)-可擴圖同時也是—個分數(shù)一(r1,k1,)-可擴圖,其中0≤r1≤r,0≤k1≤k. 設(shè)G是—個圖.則G是—個分數(shù)-(r,k).可擴圖當(dāng)且僅當(dāng)對于G任意的一個i-匹配M(0≤i≤k),G-V(M)是一個分數(shù)-(r,k-i)-可擴圖. 一個分數(shù)-(r,k)-可擴圖是分數(shù)-(k+r/2)-可擴的. 第六部分是對全文的一個總結(jié)以及對下一步工作的展
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- k可擴圖和n因子臨界圖的等價及其性質(zhì).pdf
- 幾類圖的交叉數(shù)及其相關(guān)性質(zhì).pdf
- nbanach空間及其相關(guān)性質(zhì)的研究
- 阿基米德鋪砌圖相關(guān)性質(zhì)的研究.pdf
- n-Banach空間及其相關(guān)性質(zhì)的研究.pdf
- 圖的因子與分數(shù)因子.pdf
- 雙重強子產(chǎn)生及其相關(guān)性質(zhì)的研究
- 關(guān)于阿基米德鋪砌圖相關(guān)性質(zhì)的研究.pdf
- 速溶米糠粉制備及其相關(guān)性質(zhì)的研究.pdf
- 硼酸鹽的合成及其相關(guān)性質(zhì)的研究.pdf
- 27026.區(qū)間值模糊圖的相關(guān)性質(zhì)
- 關(guān)于邊染色臨界圖有關(guān)性質(zhì)的研究.pdf
- 半模真正合列及其相關(guān)性質(zhì).pdf
- 原發(fā)性肝癌趨化因子的表達及其相關(guān)性研究.pdf
- 受控分枝過程相關(guān)性質(zhì)的研究.pdf
- 阿基米德鋪砌相關(guān)性質(zhì)的研究.pdf
- 石墨烯條帶中的自旋相關(guān)性質(zhì)及其調(diào)控.pdf
- 板栗種皮多酚的提取、純化及其相關(guān)性質(zhì)的研究.pdf
- 冠心病氣虛血瘀型與冠脈臨界病變血流儲備分數(shù)的相關(guān)性研究.pdf
- 27320.加權(quán)g期望及其相關(guān)性質(zhì)
評論
0/150
提交評論