亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        完全偶圖的定向圖

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

        張雪飛,王世英

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

        1 引言

        給定任意圖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]。

        2 主要結(jié)果

        定理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.

        猜你喜歡
        有向圖素數(shù)立方體
        孿生素數(shù)
        疊出一個立方體
        兩個素數(shù)平方、四個素數(shù)立方和2的整數(shù)冪
        有向圖的Roman k-控制
        關(guān)于兩個素數(shù)和一個素數(shù)κ次冪的丟番圖不等式
        超歐拉和雙有向跡的強積有向圖
        關(guān)于超歐拉的冪有向圖
        圖形前線
        立方體星交會對接和空間飛行演示
        太空探索(2016年9期)2016-07-12 09:59:53
        折紙
        亚洲熟妇av一区二区三区| 国产chinese在线视频| 日日骚一区二区三区中文字幕 | 人妻少妇乱子伦无码视频专区| 色老头在线一区二区三区| 国产亚洲sss在线观看| 中文字幕亚洲视频三区| 韩国av一区二区三区不卡| 中文成人无码精品久久久不卡| 欧美成人在线A免费观看| 久久精品国产亚洲av一| 精品人妻一区二区三区浪人在线| 熟女性饥渴一区二区三区| 99久久综合精品五月天| 极品少妇一区二区三区四区| 黑人老外3p爽粗大免费看视频| 骚片av蜜桃精品一区| 亚洲午夜无码AV不卡| 国产91成人自拍视频| 日韩经典午夜福利发布| www国产精品内射熟女| 久久dvd| 亚洲精品一区二区成人精品网站 | 亚洲av无码一区二区三区天堂| 好大好深好猛好爽视频免费| 国产精品白浆视频免费观看| 日本国产一区二区在线| 无码aⅴ精品一区二区三区浪潮| 国产精品久久久久久麻豆一区| 蜜桃av观看亚洲一区二区| 成人大片免费视频播放一级| 欧美乱妇高清无乱码在线观看 | 婷婷激情五月综合在线观看| 色婷婷综合激情| 亚洲视频一区二区蜜桃| 亚洲性无码av中文字幕| 欧美午夜精品一区二区三区电影 | 久久综合一本中文字幕| 91精品人妻一区二区三区久久久| 老熟妇仑乱视频一区二区 | 老熟妇高潮av一区二区三区啪啪|