完全偶圖的定向圖

張雪飛，王世英

(山西大學數(shù)學科學學院，山西太原030006)

1 引言

給定任意圖G，對于它的每條邊，給其端點指定一個順序，從而確定一條弧，由此得到一個有向圖。這樣的有向圖稱為G的一個定向圖。Buhler等［1］研究了超立方體的定向圖D，滿足D中的頂點的入度是a或者是b，證明了這樣的定向圖存在的充分必要條件是存在兩個非負整數(shù)s和t使得s+t=2n且as+bt=n2n－1。用(a，b)n表示n維超立方體H可以定向，使得它的頂點的入度是a或者是b，并稱H是(a，b)n可實現(xiàn)的。上面的結果可以重新敘述如下:設n為正整數(shù)，a，b∈{0，1，2，…，n}，(a，b)n可實現(xiàn)當且僅當存在非負整數(shù)s和t，滿足下面兩個方程:

其中方程(1)是關于超立方體的頂點數(shù)的，方程(2)是關于超立方體的邊數(shù)的。

上述結果的必要性是明顯的，事實上通過計算超立方體的頂點和邊數(shù)就可以得到。但是在充分性的證明中利用了源放入理論［2］，以致并不是所有圖都可以定向，滿足定向圖的頂點的入度是a或者是b。

每一對不同的頂點都有一條邊相連的簡單圖稱為完全圖。偶圖(或二部圖)是指一個圖，它的頂點集可以分解為兩個非空子集X和Y，使得每一條邊都有一個端點在X中，另一個端點在Y中，這樣一種二分類(X，Y)稱為圖的一個二分類。完全偶圖是具有二分類(X，Y)的簡單偶圖，其中X的每個頂點與Y的每個頂點相連，若|X|=m，|Y|=n，則這樣的圖記為Km，n。對于二部圖的研究得到了廣泛的關注，如文［3］。

對于一條弧(u，v)，稱頂點u控制頂點v，記為u→v。稱u是弧(u，v)的尾，v是弧(u，v)的頭。對有向圖D的兩個不相交的頂點子集X和Y，X→Y表示X中的每一個頂點控制Y中的每一個頂點。有向圖D中頂點v的入度d-D(v)是指以v為頭的弧的數(shù)目，在沒有混淆的情況下把d-D(v)寫成d-(v)。

圖G的一條途徑是指一個有限非空序列W=v0e1v1…ekvk，它的項交替地為頂點和邊，使得對1≤i≤k，ei的端點是vi－1和vi，稱W是從v0到vk的一條途徑。若途徑W的邊e1，e2，…，ek互不相同，則W稱為跡。經(jīng)過圖G的每條邊的跡稱為G的Euler跡。圖G的環(huán)游是指經(jīng)過G的每條邊至少一次的閉途徑。經(jīng)過每條邊恰好一次的環(huán)游為Euler環(huán)游。換言之，Euler環(huán)游是閉Euler跡。一個圖若包含Euler環(huán)游，則這個圖稱為Euler圖。

設a，b為整數(shù)且b≠0，用b|a表示b整除a。

引理1［4］一個非空連通圖是Euler圖當且僅當它沒有奇點。

引理2［5］如果素數(shù) p|ab，則 p|a或p|b。

本文研究Kn，n的定向圖D，滿足D中每個頂點的入度為a或者為b。為了簡便起見，用［a，b］n表示把Kn，n定向為有向圖D，使得D 中頂點的入度是 a或者是 b的一個圖類，并稱 Kn，n是［a，b］n可實現(xiàn)的，簡稱［a，b］n是可實現(xiàn)的。文中其它未定義的圖論術語和記號參見文獻［4，6］。

2 主要結果

定理1 設 n 為正整數(shù)，a，b∈{0，1，2…n}，若 Kn，n是［a，b］n可實現(xiàn)的，則存在非負整數(shù) s和 t，滿足下面兩個方程:

證明 由于Kn，n是［a，b］n可實現(xiàn)的，因此存在Kn，n的一個定向圖D使得每個頂點的入度是a或者是b。設D中入度為a的頂點個數(shù)為s。注意到D中所有頂點入度的和為n2。我們有sa+(2n－s)b=n2，令t=2n－s，此時s和t為滿足方程(3)和(4)的非負整數(shù)。證畢。

如果 n 為正整數(shù)，a，b∈{0，1，2，…，n}，則有以下命題成立。

命題1 (1)若［a，b］n是可實現(xiàn)的，則［n－a，n－b］n是可實現(xiàn)的。

(2)［0，n］n是可實現(xiàn)的。

證明 (1)當［a，b］n可實現(xiàn)時，則Kn，n中每個頂點的入度是a或者是b，把Kn，n中所有弧的方向調(diào)換，即原來弧的始點變?yōu)榻K點，終點變?yōu)槭键c，又因為Kn，n是n正則的，所以后來得到的有向圖D的每個頂點的入度是n－a或者n－b。

(2)在二部圖Kn，n中，它有一個二分類(X，Y)，且|X|=n，|Y|=n，我們給其一種特殊的定向，使得X→Y，則X中n個頂點的入度為0，Y中n個頂點的入度為n，因此［0，n］n是可實現(xiàn)的。

表1 ［a，b］n的數(shù)據(jù)表Table 1 The datasheet of［a，b］n

通過觀察這些數(shù)據(jù)，發(fā)現(xiàn)它們有一定的規(guī)律可循。特別地，K1，1中只有一條邊，把該邊定向后，弧的兩個端點中一個入度為0，一個入度為1，顯然［0，1］1是可實現(xiàn)的，以下假設n≥2。

定理 2 設 a，b，s，t為非負整數(shù)(a，b∈{0，1，2，…，n})滿足下面兩個方程:

則在Kn，n中有以下結論成立:

(1)若 n為素數(shù)時，則［a，b］n是可實現(xiàn)的，其中 b=n－a。

(2)若 n為合數(shù)且滿足 s≥a，n－s≥b和 n+≥2b，則［a，b］n是可實現(xiàn)的。

證明 (1)當n為素數(shù)時，a≠b，設 a＜b。由方程組(3)，(4)可得 a(2n－t)+bt=n2，整理后得到(b－a)t=n(n－2a)。因為a，b∈{0，1，2，…，n}，a＜b，且 n為素數(shù)，故 n|(b－a)t。又因為 0 ＜b－ a≤n，當b－a=n時，a=0，b=n，可知s=n，t=n。當0 ＜b－a＜n時，n|(b－a)，由引理2 可知n|t。同理可知n|s。又因為s+t=2n，且s，t為非負整數(shù)，故得到s=t=n。當s=t=n時，可求解出b=n－a。故由方程組僅可求出的解為［a，n－a］n。下證［a，n－a］n是可實現(xiàn)的。

在 Kn，n中，它有一個二分類(X，Y)，且|X|=n，|Y|=n，X 中的頂點表示為 ui，Y 中的頂點表示為 vj，i，j∈{1，2，…，n}。

對X中任意頂點ui，令v(i+l)(mods)→ui，其中l(wèi)=0，1，…，a－1。對 Y中的其他頂點 vk，定向 vk與 ui間的弧為ui→vk。這樣集合X中n個頂點的入度為a，集合Y中n頂點的入度為n－a，故證得［a，n－a］n是可實現(xiàn)的。

對 X1中任意頂點 ui，令 v(i+l)(mods)→ui，其中l(wèi)=0，1，…，a －1。對 Y1中的其他頂點 vk，定向 vk與 ui間的弧為ui→vk，且X1中的頂點控制Y2中的頂點，即X1→Y2。同理，對X2中任意頂點uj，令v(j+l)→uj，其中l(wèi)=0，1，…，b－1，且當 j+l＞n時，令 v(j+l)=v(j+l)(modn)+s。對 Y2中的其他頂點 vm，定向 vm與 uj間的弧為 uj→um，且X2中的頂點控制Y1中的頂點，即X2→Y1。

下面對Y中頂點的入度進行調(diào)整，對Y2中任意滿足d-(vl)=n－b＜b的頂點vl，在X2中存在某個頂點uj，使得 ul→uj。任取 uk∈Y1，則 uj→vk。轉換 vl→uj→vk為 vk→uj→vl。該過程中 vk的入度數(shù)減少 1，vl的入度增加1，uj的入度不變。若d-(vl)+1仍然小于b，注意到vl在X2中的外鄰集中的點數(shù)為b，在X2中存在某個頂點 uj'，使得 uj'≠uj并且 vl→uj'。選取 uk'∈Y1，使得 d-(vk')＞ b，則 uj'→vk。轉換 vl→uj'→vk'為 vk'→uj'→vl。該過程中 vk'的入度減少1，vl的入度增加1，uj'的入度不變。注意到 n+s≥2b，我們有 s(n－s)≥［b－(n－b)］(n－s)。將上述過程一直進行下去，直到 d-(vl)=b。由 vl的任意性以及(n－a－b)s=(b－(n－b))(n－s)，可知上述過程結束時Y1中的所有頂點的入度均為b。此時［a，b］n是可實現(xiàn)的。證畢。

［1］BUHLER J，BUTLER S，GRAHAM R，et al.Hypercube orientations with only two in-degrees［J］.Journal of Combinatorial Theory，Series A，2011，118(6):1695-1702.

［2］BUTLER S，HAJIAGHAYI M T，KLEINBERG R D，et al.Hat guessing games［J］.SIAM Journal on Discrete Mathematics，2008，22(2):592-605.

［3］高敬振，邵光鳳.極大局部邊連通和超級局部邊連通二部有向圖的鄰域條件［J］.山東科學，2012，25(2):1-7.

［4］BONDY J A，MURTY U S R.Graph Theory［M］.New York:Springer，2008.

［5］聶靈沼，丁石孫.代數(shù)學引論［M］.北京:高等教育出版社，2009.

［6］JENSEN J B，GUTIN G.Digraphs Theory，Algorithms and Applications［M］.New York:Springer，2007.