• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      完全偶圖的定向圖

      2013-12-03 08:06:54張雪飛王世英
      山東科學(xué) 2013年3期
      關(guān)鍵詞:有向圖素?cái)?shù)立方體

      張雪飛,王世英

      (山西大學(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.

      猜你喜歡
      有向圖素?cái)?shù)立方體
      孿生素?cái)?shù)
      疊出一個(gè)立方體
      兩個(gè)素?cái)?shù)平方、四個(gè)素?cái)?shù)立方和2的整數(shù)冪
      有向圖的Roman k-控制
      關(guān)于兩個(gè)素?cái)?shù)和一個(gè)素?cái)?shù)κ次冪的丟番圖不等式
      超歐拉和雙有向跡的強(qiáng)積有向圖
      關(guān)于超歐拉的冪有向圖
      圖形前線(xiàn)
      立方體星交會(huì)對(duì)接和空間飛行演示
      太空探索(2016年9期)2016-07-12 09:59:53
      折紙
      沙坪坝区| 公主岭市| 河北区| 仁怀市| 黑山县| 搜索| 绥滨县| 分宜县| 娄底市| 普兰县| 泸西县| 林口县| 泰来县| 吉林省| 乌兰察布市| 北安市| 崇信县| 青川县| 伊春市| 界首市| 拉孜县| 江源县| 喀喇沁旗| 合川市| 日照市| 莎车县| 德安县| 渭南市| 河津市| 霍邱县| 浪卡子县| 宝兴县| 邹平县| 崇义县| 河间市| 广宁县| 裕民县| 栾城县| 囊谦县| 商都县| 北安市|