張雪飛,王世英
(山西大學(xué)數(shù)學(xué)科學(xué)學(xué)院,山西太原030006)
給定任意圖G,對于它的每條邊,給其端點指定一個順序,從而確定一條弧,由此得到一個有向圖。這樣的有向圖稱為G的一個定向圖。Buhler等[1]研究了超立方體的定向圖D,滿足D中的頂點的入度是a或者是b,證明了這樣的定向圖存在的充分必要條件是存在兩個非負(fù)整數(shù)s和t使得s+t=2n且as+bt=n2n-1。用(a,b)n表示n維超立方體H可以定向,使得它的頂點的入度是a或者是b,并稱H是(a,b)n可實現(xiàn)的。上面的結(jié)果可以重新敘述如下:設(shè)n為正整數(shù),a,b∈{0,1,2,…,n},(a,b)n可實現(xiàn)當(dāng)且僅當(dāng)存在非負(fù)整數(shù)s和t,滿足下面兩個方程:
其中方程(1)是關(guān)于超立方體的頂點數(shù)的,方程(2)是關(guān)于超立方體的邊數(shù)的。
上述結(jié)果的必要性是明顯的,事實上通過計算超立方體的頂點和邊數(shù)就可以得到。但是在充分性的證明中利用了源放入理論[2],以致并不是所有圖都可以定向,滿足定向圖的頂點的入度是a或者是b。
每一對不同的頂點都有一條邊相連的簡單圖稱為完全圖。偶圖(或二部圖)是指一個圖,它的頂點集可以分解為兩個非空子集X和Y,使得每一條邊都有一個端點在X中,另一個端點在Y中,這樣一種二分類(X,Y)稱為圖的一個二分類。完全偶圖是具有二分類(X,Y)的簡單偶圖,其中X的每個頂點與Y的每個頂點相連,若|X|=m,|Y|=n,則這樣的圖記為Km,n。對于二部圖的研究得到了廣泛的關(guā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圖。
設(shè)a,b為整數(shù)且b≠0,用b|a表示b整除a。
引理1[4]一個非空連通圖是Euler圖當(dāng)且僅當(dāng)它沒有奇點。
引理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)的。文中其它未定義的圖論術(shù)語和記號參見文獻[4,6]。
定理1 設(shè) n 為正整數(shù),a,b∈{0,1,2…n},若 Kn,n是[a,b]n可實現(xiàn)的,則存在非負(fù)整數(shù) s和 t,滿足下面兩個方程:
證明 由于Kn,n是[a,b]n可實現(xiàn)的,因此存在Kn,n的一個定向圖D使得每個頂點的入度是a或者是b。設(shè)D中入度為a的頂點個數(shù)為s。注意到D中所有頂點入度的和為n2。我們有sa+(2n-s)b=n2,令t=2n-s,此時s和t為滿足方程(3)和(4)的非負(fù)整數(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)當(dāng)[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)的,以下假設(shè)n≥2。
定理 2 設(shè) a,b,s,t為非負(fù)整數(shù)(a,b∈{0,1,2,…,n})滿足下面兩個方程:
則在Kn,n中有以下結(jié)論成立:
(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)當(dāng)n為素數(shù)時,a≠b,設(shè) 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,當(dāng)b-a=n時,a=0,b=n,可知s=n,t=n。當(dāng)0 <b-a<n時,n|(b-a),由引理2 可知n|t。同理可知n|s。又因為s+t=2n,且s,t為非負(fù)整數(shù),故得到s=t=n。當(dāng)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,且當(dāng) 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。轉(zhuǎn)換 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。轉(zhuǎn)換 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),可知上述過程結(jié)束時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].山東科學(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.