高 煒

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

1 預備知識

若f≡g，則分數(g,f)-因子稱為分數f-因子．若g(x)=a，f(x)=b對任意頂點x都成立，則分數(g,f)-因子稱為分數[a,b]-因子．特別地，若對任意頂點x有g(x)=f(x)=k，則分數(g,f)-因子稱為分數k-因子．

假設圖G存在多個分數f-因子，把擁有最多邊數的分數f-因子稱為圖G的最大分數f-因子．為了刻畫最大分數f-因子的特征，首先在分數f-因子框架下給出在符號交錯路，調整操作以及增廣路的概念．

約定本文中給出的路徑允許每條邊最多出現兩次．設Gh1和Gh2是圖G分別關于示性函數h1和h2的分數f-因子．記

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

2 主要結論及證明

下述定理1說明了圖G的任何兩個分數f-因子可以通過有限次調整操作進行相互轉換．

定理1設Gh1和Gh2是圖G分別關于示性函數h1和h2的分數f-因子．則Gh2可以由Gh1通過有限次重復調整操作得到．

證明假設f≠g，定義邊集合

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

下面說明H中存在關于示性函數h1和h2的符號交錯路．假設符號交錯圈不存在，則在H中取長度最長的符號交錯路P=x1x2…xm．不妨設Δh1,h2(x1x2)>0，下面分兩種情況討論．

1)若m是奇數，則Δ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的符號交錯圈； 若i≤j，則C=(x1,…,xi,…,xj,…,xm,xj,…,xi,x1)是H的符號交錯圈．

2)若m是偶數，則Δ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的符號交錯圈； 若i≤j， 則C=(x1,…,xi,…,xj,…,xm,xj,…,xi,x1)是H的符號交錯圈．

下述定理2刻畫了最大分數f-因子的特性．

定理2設Gh是圖G分別關于示性函數h的分數f-因子．則Gh是最大分數f-因子當且僅當G不存在關于h的增廣路．

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

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

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

h(ej)≤hr-1(ej)

對偶數j，有

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

根據e1的選擇可知C是G中關于示性函數h的增廣路，與假設矛盾．

3 小結和討論

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