完全偶圖的定向圖

張雪飛，王世英

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

1 引言

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

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

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

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

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

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

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

引理1［4］一個(gè)非空連通圖是Euler圖當(dāng)且僅當(dāng)它沒(méi)有奇點(diǎn)。

引理2［5］如果素?cái)?shù) p|ab，則 p|a或p|b。

本文研究Kn，n的定向圖D，滿(mǎn)足D中每個(gè)頂點(diǎn)的入度為a或者為b。為了簡(jiǎn)便起見(jiàn)，用［a，b］n表示把Kn，n定向?yàn)橛邢驁DD，使得D 中頂點(diǎn)的入度是 a或者是 b的一個(gè)圖類(lèi)，并稱(chēng) Kn，n是［a，b］n可實(shí)現(xiàn)的，簡(jiǎn)稱(chēng)［a，b］n是可實(shí)現(xiàn)的。文中其它未定義的圖論術(shù)語(yǔ)和記號(hào)參見(jiàn)文獻(xiàn)［4，6］。

2 主要結(jié)果

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

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

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

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

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

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

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

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

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

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

則在Kn，n中有以下結(jié)論成立:

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

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

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

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

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

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

下面對(duì)Y中頂點(diǎn)的入度進(jìn)行調(diào)整，對(duì)Y2中任意滿(mǎn)足d-(vl)=n－b＜b的頂點(diǎn)vl，在X2中存在某個(gè)頂點(diǎn)uj，使得 ul→uj。任取 uk∈Y1，則 uj→vk。轉(zhuǎn)換 vl→uj→vk為 vk→uj→vl。該過(guò)程中 vk的入度數(shù)減少 1，vl的入度增加1，uj的入度不變。若d-(vl)+1仍然小于b，注意到vl在X2中的外鄰集中的點(diǎn)數(shù)為b，在X2中存在某個(gè)頂點(diǎn) uj'，使得 uj'≠u(mài)j并且 vl→uj'。選取 uk'∈Y1，使得 d-(vk')＞ b，則 uj'→vk。轉(zhuǎn)換 vl→uj'→vk'為 vk'→uj'→vl。該過(guò)程中 vk'的入度減少1，vl的入度增加1，uj'的入度不變。注意到 n+s≥2b，我們有 s(n－s)≥［b－(n－b)］(n－s)。將上述過(guò)程一直進(jìn)行下去，直到 d-(vl)=b。由 vl的任意性以及(n－a－b)s=(b－(n－b))(n－s)，可知上述過(guò)程結(jié)束時(shí)Y1中的所有頂點(diǎn)的入度均為b。此時(shí)［a，b］n是可實(shí)現(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í)局部邊連通二部有向圖的鄰域條件［J］.山東科學(xué)，2012，25(2):1-7.

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

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

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