高 煒

(云南師范大學(xué) 信息學(xué)院，云南 昆明 650500)

1 預(yù)備知識(shí)

若f≡g，則分?jǐn)?shù)(g,f)-因子稱為分?jǐn)?shù)f-因子．若g(x)=a，f(x)=b對(duì)任意頂點(diǎn)x都成立，則分?jǐn)?shù)(g,f)-因子稱為分?jǐn)?shù)[a,b]-因子．特別地，若對(duì)任意頂點(diǎn)x有g(shù)(x)=f(x)=k，則分?jǐn)?shù)(g,f)-因子稱為分?jǐn)?shù)k-因子．

假設(shè)圖G存在多個(gè)分?jǐn)?shù)f-因子，把擁有最多邊數(shù)的分?jǐn)?shù)f-因子稱為圖G的最大分?jǐn)?shù)f-因子．為了刻畫(huà)最大分?jǐn)?shù)f-因子的特征，首先在分?jǐn)?shù)f-因子框架下給出在符號(hào)交錯(cuò)路，調(diào)整操作以及增廣路的概念．

約定本文中給出的路徑允許每條邊最多出現(xiàn)兩次．設(shè)Gh1和Gh2是圖G分別關(guān)于示性函數(shù)h1和h2的分?jǐn)?shù)f-因子．記

圖G關(guān)于示性函數(shù)h的增廣路W是一條長(zhǎng)度為偶數(shù)的閉路徑，它的邊在大于0和小于1之間交替，且至少有一條邊在h下的值為0．若將增廣路定義為邊的序列W=(e0,e1,…,e2m-1,e0)，則對(duì)于0≤r≤m-1有h(e2r)<1和h(e2r+1)>0成立，且對(duì)某些i有h(e2i)=0．

2 主要結(jié)論及證明

下述定理1說(shuō)明了圖G的任何兩個(gè)分?jǐn)?shù)f-因子可以通過(guò)有限次調(diào)整操作進(jìn)行相互轉(zhuǎn)換．

定理1設(shè)Gh1和Gh2是圖G分別關(guān)于示性函數(shù)h1和h2的分?jǐn)?shù)f-因子．則Gh2可以由Gh1通過(guò)有限次重復(fù)調(diào)整操作得到．

證明假設(shè)f≠g，定義邊集合

Eh1≠h2={e∈E(G):h1(e)≠h2(e)}.

下面說(shuō)明H中存在關(guān)于示性函數(shù)h1和h2的符號(hào)交錯(cuò)路．假設(shè)符號(hào)交錯(cuò)圈不存在，則在H中取長(zhǎng)度最長(zhǎng)的符號(hào)交錯(cuò)路P=x1x2…xm．不妨設(shè)Δh1,h2(x1x2)>0，下面分兩種情況討論．

1)若m是奇數(shù)，則Δh1,h2(xm-1xm)<0． 由于δ(H)≥2， 必然存在i,j∈{1,2,…,m}使得Δh1,h2(x1xi)<0和Δh1,h2(xmxj)>0成立． 從而C1=(x1,…,xi,x1)和C2=(xj,…,xm,xj)均為奇圈． 若i>j， 則C=(x1,…,xj,xm,…,xi,x1)是H的符號(hào)交錯(cuò)圈； 若i≤j，則C=(x1,…,xi,…,xj,…,xm,xj,…,xi,x1)是H的符號(hào)交錯(cuò)圈．

2)若m是偶數(shù)，則Δh1,h2(xm-1xm)>0． 由于δ(H)≥2， 必然存在i,j∈{1,2,…,m}使得Δh1,h2(x1xi)<0和Δh1,h2(xmxj)<0成立． 從而C1=(x1,…,xi,x1)和C2=(xj,…,xm,xj)均為奇圈． 若i>j， 則C=(x1,…,xj,xm,…,xi,x1)是H的符號(hào)交錯(cuò)圈； 若i≤j， 則C=(x1,…,xi,…,xj,…,xm,xj,…,xi,x1)是H的符號(hào)交錯(cuò)圈．

下述定理2刻畫(huà)了最大分?jǐn)?shù)f-因子的特性．

定理2設(shè)Gh是圖G分別關(guān)于示性函數(shù)h的分?jǐn)?shù)f-因子．則Gh是最大分?jǐn)?shù)f-因子當(dāng)且僅當(dāng)G不存在關(guān)于h的增廣路．

證明設(shè)Gh是最大分?jǐn)?shù)f-因子且G存在增廣路C=(e1,e2,…,em)． 設(shè)E′(C)={e∈E′(C):0

不失一般性，可以設(shè)h(e1)=0． 設(shè)：h′(ei)=ε若i是奇數(shù)；h′(ei)=-ε若i是偶數(shù)；h′(e)=0若e∈E(G)-E(C)． 則Gh+h′是G的關(guān)于示性函數(shù)h+h′的分?jǐn)?shù)f-因子，而它的邊數(shù)為大于Gh的邊數(shù)，這與Gh是最大分?jǐn)?shù)f-因子的假設(shè)矛盾．

反之，設(shè)G中沒(méi)有關(guān)于h的增廣路，證明Gh是G的最大分?jǐn)?shù)f-因子．否則，設(shè)Gh′是G的最大分?jǐn)?shù)f-因子，對(duì)應(yīng)示性函數(shù)h′，且|Eh′|>|Eh|． 進(jìn)而至少存在一條邊e1∈E(G)使得h′(e1)>0和h(e1)=0成立． 根據(jù)定理1，Gh′可以由Gh通過(guò)一些列調(diào)整操作得到， 且設(shè)h=h0,h1,…,hs-1,hs=h′是調(diào)整超過(guò)過(guò)程中對(duì)應(yīng)的示性函數(shù)序列，r是滿足hr-1(e1)=0和hr(e1)>0的最小下標(biāo)． 進(jìn)而在Ghr-1中存在符號(hào)交錯(cuò)圈C=(e1,e2,…,em)包含e1．根據(jù)符號(hào)交錯(cuò)路的定義可知：對(duì)任意滿足h(e)h′(e)的e∈E(C)， 有hr-1(e)>hr(e)． 進(jìn)而有： 對(duì)所有滿足h(e)h′(e)的e∈E(G)， 對(duì)任意i=0,1,…,s-1有hi(e)≥hi+1(e)．進(jìn)一步，對(duì)奇數(shù)j，有

h(ej)≤hr-1(ej)

對(duì)偶數(shù)j，有

h(ej)≥hr-1(ej)>hr(ej)≥h′(ej)≥0.

根據(jù)e1的選擇可知C是G中關(guān)于示性函數(shù)h的增廣路，與假設(shè)矛盾．

3 小結(jié)和討論

本文指出圖G的兩個(gè)不同兩個(gè)分?jǐn)?shù)f-因子可以通過(guò)有限次調(diào)整操作進(jìn)行相互轉(zhuǎn)換，并且從增廣路的角度給出Gh是最大分?jǐn)?shù)f-因子的充分必要條件．然而本文中給出的定理1和定理2無(wú)法直接推廣到分?jǐn)?shù)(g,f)-因子或者分?jǐn)?shù)[a,b]-因子，其根本原因在于不同分?jǐn)?shù)(g,f)-因子或分?jǐn)?shù)[a,b]-因子在具體某個(gè)頂點(diǎn)上的值不固定，導(dǎo)致定理1證明過(guò)程中的δ(H)≥2不一定成立．而定理2的證明是基于定理1的，因此定理2也無(wú)法直接推廣．關(guān)于最大分?jǐn)?shù)(g,f)-因子或最大分?jǐn)?shù)[a,b]-因子的刻畫(huà)，還需要進(jìn)一步研究．