二分圖的因子.pdf

1、具有重要的理論意義的因子問題，一直是圖論中的熱點(diǎn)話題之一，且至今已有相當(dāng)豐富的研究成果.關(guān)于分?jǐn)?shù)因子的研究也是最近幾年提出的新問題.國外數(shù)學(xué)家在匹配概念的基礎(chǔ)上提出因子、分?jǐn)?shù)因子的概念.設(shè)夕和t廠是定義在V(G)上的兩個(gè)整數(shù)值函數(shù)，且對每個(gè)x∈y(G)有0≤g(x)≤f(x)，設(shè)F是圖G的一個(gè)生成子圖，若對每個(gè)x∈y(G)有9(x)≤dF(x)≤f(x)，則稱F為圖G的一個(gè)(g，f)-因子.若9(x)=a，f(x)=6，則稱上述因子為(

2、a，b)-因子.若a=6=k，則稱(a，6)-因子為k-因子.設(shè)h是定義在圖G的邊集E(G)上的一個(gè)函數(shù)，使得對任意的e∈E(G)有h(e)∈[0，1]，令d<,G><,h>(x)=∑<,e∈E<,x>>h(e)，其中E<,x<={e|e=xy∈E(G))，則稱d<,G><,h>(z)x是G中頂點(diǎn)x的分?jǐn)?shù)度.若h滿足對任意的x∈V(G)，有g(shù)(x)≤d<,G><,h>(x)≤f(x)，則稱h是G的一個(gè)分?jǐn)?shù)(g，h)-表示函數(shù).令E<,h

3、>={e∈E(G)|h(e)≠0}，設(shè)G<,h>是G的生成子圖，若E(G<,h>)=E<,h>，則稱G,,h>是G的一個(gè)分?jǐn)?shù)(g，f)-因子.類似可定義分?jǐn)?shù)(a，b)-因子，分?jǐn)?shù)k-因子. 在第一章中，我們給出了本文所用的術(shù)語、記號. 在第二章中，給出了二分圖存在分?jǐn)?shù)k-因子的一個(gè)充要條件. 在第三章中，給出了二分圖中包含圈和對集的一個(gè)證明. 在第四章中，研究了二分圖中一個(gè)與韌度相關(guān)的參數(shù)與k-因子存在性