分?jǐn)?shù)因子臨界圖及其相關(guān)性質(zhì)的研究.pdf

1、本文所考慮的圖都是簡(jiǎn)單無(wú)向圖．設(shè)G=(V(G)，E(G))是一個(gè)圖，其中V(G)和E(G)分別表示G的頂點(diǎn)集合和邊集合．頂點(diǎn)x在G中的度記為dG(x)，δ(G)表示G中所有頂點(diǎn)度的最小值．對(duì)于任意的集合S(￠)V(G)，由S導(dǎo)出的G的子圖記為G[S]，G-S表示由V(G)＼S導(dǎo)出的子圖．用o(G-S)和i(G-S)分別代表G-S中奇分支的個(gè)數(shù)和孤立頂點(diǎn)的個(gè)數(shù)． 設(shè)g(x)≤f(x)是定義在V(G)上的兩個(gè)非負(fù)整數(shù)值函數(shù)，H是G的

2、一個(gè)支撐子圖．如果對(duì)于任意的x∈V(G)，滿足g(x)≤dH(x)≤f(x)，則稱(chēng)H是G的一個(gè)(g，f)-因子．類(lèi)似的，如果對(duì)于任意的x∈V(G)，滿足g(x)=f(x)，則稱(chēng)日是G的一個(gè)f-因子(或g-因子)；如果對(duì)于任意的x∈V(G)，有g(shù)(x)=a，f(x)=6且a，b是兩個(gè)正整數(shù)，那么(g，f)-因子就可被稱(chēng)為[a，b]-因子．特別的，對(duì)于任意的x∈V(G)，有g(shù)(x)=f(x)=1時(shí)，(g，f)-因子就變成了1-因子，即完美匹

3、配． 設(shè)g(x)≤(x)是定義在V(G)上的兩個(gè)非負(fù)整數(shù)值函數(shù)，h(e)∈[0，1]是-個(gè)定義在E(G)上的函數(shù)并且dhG(x)=∑e∈Exh(e)，其中Ex={xy：xy∈E(G)}．此時(shí)dhG(x)被稱(chēng)為是在h作用下的G中頂點(diǎn)x的分?jǐn)?shù)度，h被稱(chēng)為是一個(gè)指示函數(shù)(inditor fullction)．如果對(duì)于任意的x∈V(G)，有g(shù)(x)≤dhG(x)≤f(x)，設(shè)Eh={e：e∈E(G)，h(e)≠0}且Gh是G的一個(gè)支撐子

4、圖并使得E(Gh)=Eh，那么Gh就是G的一個(gè)分?jǐn)?shù)-(g，f)-因子．同樣的方法可以類(lèi)似的定義分?jǐn)?shù)-k-因子、分?jǐn)?shù)-[a，b]-因子等．特別的，對(duì)于任意的x∈V(G)，有g(shù)(x)=f(x)=1時(shí)，分?jǐn)?shù)-(g，f)-因子變?yōu)榉謹(jǐn)?shù)-1-因子，即分?jǐn)?shù)完美匹配． 圖的因子理論是圖論中研究的主要問(wèn)題之一．對(duì)因子理論的研究在一個(gè)多世紀(jì)以前就開(kāi)始了，但直到上世紀(jì)七十年代才逐漸地活躍了起來(lái)．到目前為止，對(duì)圖的因子方面的研究已經(jīng)得到了不少成果．分

5、數(shù)圖論是相對(duì)年輕的分支，因此仍有許多問(wèn)題有待解決． 本文共分為六大部分，第四部分和第五部分是整個(gè)文章的核心，通過(guò)分析證明得出了分?jǐn)?shù)因子臨界圖和分?jǐn)?shù)-(r，k)-可擴(kuò)圖的一些結(jié)論． 第一部分是全文的基礎(chǔ)部分．簡(jiǎn)要介紹了文中所涉及的概念、術(shù)語(yǔ)和符號(hào)，回顧了圖論及圖因子問(wèn)題的發(fā)展史，并對(duì)圖因子問(wèn)題中常用的重要參數(shù)作了詳細(xì)介紹． 第二部分概括總結(jié)了圖因子存在性問(wèn)題中整數(shù)因子和分?jǐn)?shù)因子已有的重要定理． 第三部分分析

6、概括出圖因子存在性問(wèn)題中的兩種常用研究方法． 第四部分重點(diǎn)研究了分?jǐn)?shù)因子臨界圖(設(shè)G是一個(gè)圖，若對(duì)于頂點(diǎn)集合V(G)的任意n-子集T使得G-T有分?jǐn)?shù)-r-因子，則稱(chēng)G是-個(gè)分?jǐn)?shù)-(r，n)-因子-臨界圖)的一些性質(zhì)，得出了以下結(jié)論： 設(shè)G是δ(G)≥r+n的圖且孤立韌度I(G)≥r+n-1/r．則G是一個(gè)分?jǐn)?shù)-(r，n)-因子-臨界圖． 假設(shè)G是δ(G)≥r+n的圖．若G是分?jǐn)?shù)-(r，n)-因子-臨界圖，則G也是

7、分?jǐn)?shù)-(r,n-1)-因子-臨界圖． 如果對(duì)于任意的u∈V(G)，G-{u}-有分?jǐn)?shù)-r-因子，那么G同樣也有分?jǐn)?shù)-r-因子．第五部分主要研究了分?jǐn)?shù)-(r,k)-可擴(kuò)圖(設(shè)G是一個(gè)圖，如果對(duì)于V(G)的任意r-子集T，G-T是一個(gè)分?jǐn)?shù)-k-可擴(kuò)圖，則G是一個(gè)分?jǐn)?shù)-(r，k)-可擴(kuò)圖)的一些性質(zhì)，得出了以下結(jié)論： 圖G是一個(gè)分?jǐn)?shù)-(r，k)-可擴(kuò)圖當(dāng)且僅當(dāng)對(duì)于任意的集合U∈V(G)，有i(G-U)≤U-2K-r．其中，|U

8、|≥2k+r且G[U]包含一個(gè)k-匹配． 任意—個(gè)分?jǐn)?shù)-(r，k)-可擴(kuò)圖同時(shí)也是—個(gè)分?jǐn)?shù)一(r1，k1，)-可擴(kuò)圖，其中0≤r1≤r，0≤k1≤k. 設(shè)G是—個(gè)圖．則G是—個(gè)分?jǐn)?shù)-(r，k)．可擴(kuò)圖當(dāng)且僅當(dāng)對(duì)于G任意的一個(gè)i-匹配M(0≤i≤k)，G-V(M)是一個(gè)分?jǐn)?shù)-(r，k-i)-可擴(kuò)圖． 一個(gè)分?jǐn)?shù)-(r，k)-可擴(kuò)圖是分?jǐn)?shù)-(k+r/2)-可擴(kuò)的． 第六部分是對(duì)全文的一個(gè)總結(jié)以及對(duì)下一步工作的展