準(zhǔn)傳遞定向圖上的Seymour點(diǎn)

李瑞娟,史 杰,張新鴻

(1.山西大學(xué)數(shù)學(xué)科學(xué)學(xué)院,山西太原030006;2.太原科技大學(xué)應(yīng)用數(shù)學(xué)系,山西太原030024)

§1 引 言

Seymour提出的關(guān)于定向圖的二次鄰域的問(wèn)題是有向圖理論中最有趣,最具挑戰(zhàn)性的問(wèn)題之一.這里,定向圖是指沒(méi)有2圈的有向圖.本文涉及到的有向圖是無(wú)環(huán),無(wú)平行邊的簡(jiǎn)單有向圖,相關(guān)的術(shù)語(yǔ)和符號(hào)參看下一小節(jié)以及文獻(xiàn)[1].

猜想1.1[2](Seymour二次鄰域猜想) 在定向圖D中,總可以找到一個(gè)頂點(diǎn)x,這個(gè)頂點(diǎn)的二次外鄰域至少和它的外鄰域一樣大,即d+(x)6d++(x).

根據(jù)文獻(xiàn)[3],這樣的頂點(diǎn)x稱(chēng)為Seymour點(diǎn).

值得注意的是,猜想1.1只適用于定向圖,并不適用于一般的包含2圈的有向圖.例如,n個(gè)頂點(diǎn)的完全有向圖,對(duì)于每個(gè)頂點(diǎn),都有即

把Seymour二次鄰域猜想限制到競(jìng)賽圖上,稱(chēng)為Dean猜想.Fisher在文獻(xiàn)[4]中,利用Farkas引理,證明了Dean猜想[2],得到以下結(jié)論.

定理1.1[4]在任何一個(gè)競(jìng)賽圖T中,都包含一個(gè)Seymour點(diǎn).

Havet和Thomass在文獻(xiàn)[5]中給出了Dean猜想更基本的證明,并介紹了一種叫中間序的方法.他們的證明也得到了以下更強(qiáng)的結(jié)果.

定理1.2[5]若競(jìng)賽圖T無(wú)出度為零的頂點(diǎn),則T至少包含兩個(gè)Seymour點(diǎn).

文獻(xiàn)[6]進(jìn)一步發(fā)展了中間序的方法,證明了猜想1.1對(duì)于最小度為|V(D)|?2的有向圖D也同樣適用.同樣地,猜想1.1對(duì)于競(jìng)賽圖減去一顆星,競(jìng)賽圖去掉子競(jìng)賽圖的弧集也同樣適用.Ghazal在文獻(xiàn)[7]中也使用了中間序的方法,證明了猜想1.1對(duì)于加權(quán)競(jìng)賽圖去掉廣義星同樣適用.Kaneko和Locke在文獻(xiàn)[8]中證明了猜想1.1對(duì)于最小出度最多為6的定向圖也同樣適用.Cohn,Godbole,WrightHarkness和Zhang在文獻(xiàn)[3]中證明了該猜想對(duì)于某些隨機(jī)定向圖也適用.

證明猜想1.1的另一種方法是確定極大值γ,使得在每個(gè)有向圖D中存在一個(gè)頂點(diǎn)x滿(mǎn)足. 在猜想1.1中,γ=1.Chen,Shen和Yuster在文獻(xiàn)[9]中證明了γ≥r,其中r=0.657298···是2x3+x2?1=0的唯一實(shí)根.若對(duì)證明方法細(xì)化,他們還可以得到r≥0.67815···.近年來(lái),二次鄰域問(wèn)題被更多人研究,參看文獻(xiàn)[10-12].

本文將證明Seymour二次鄰域猜想在準(zhǔn)傳遞定向圖上的正確性,通過(guò)研究準(zhǔn)傳遞定向圖的Seymour點(diǎn)與擴(kuò)張競(jìng)賽圖的Seymour點(diǎn)之間的關(guān)系,得到:每個(gè)準(zhǔn)傳遞定向圖至少包含一個(gè)Seymour點(diǎn);無(wú)出度為零的點(diǎn)的準(zhǔn)傳遞定向圖至少包含兩個(gè)Seymour點(diǎn).

§2 術(shù)語(yǔ),符號(hào)和基本結(jié)論

設(shè)D是一個(gè)有向圖,分別用V(D)和A(D)表示D的頂點(diǎn)集和弧集.

若有向圖D中的不同頂點(diǎn)u和v,存在從u到v的弧,則稱(chēng)u控制v,寫(xiě)成u→v,并稱(chēng)v是u的外鄰點(diǎn)或者u是v的內(nèi)鄰點(diǎn).若對(duì)于D的一個(gè)子有向圖或僅僅是D的一個(gè)頂點(diǎn)子集H(可能有H=D),H中頂點(diǎn)u的外鄰點(diǎn)的集合用表示,稱(chēng)它為H中頂點(diǎn)u的外鄰域.另外,稱(chēng)為u在H中的出度.設(shè)

如果有向圖D沒(méi)有有向圈,那么它就是無(wú)圈的.如果對(duì)于無(wú)圈有向圖D的每一對(duì)弧xixj∈A(D),滿(mǎn)足i

若D=H[S1,S2,···,Sh],且每個(gè)有向圖S1,S2,···,Sh都沒(méi)有弧,則稱(chēng)D是H的擴(kuò)張.這時(shí)對(duì)每個(gè)i∈{1,2,···,h},Si稱(chēng)為D的部集.若有向圖中每對(duì)不同的頂點(diǎn)都相鄰,則稱(chēng)這個(gè)有向圖為半完全有向圖.沒(méi)有2圈的半完全有向圖稱(chēng)為競(jìng)賽圖.擴(kuò)張競(jìng)賽圖是指一個(gè)競(jìng)賽圖的擴(kuò)張.對(duì)于有向圖D中的三個(gè)不同的頂點(diǎn)x,y和z,若在D中存在弧xy,yz,在x和z之間總存在一條弧,那么稱(chēng)有向圖D是準(zhǔn)傳遞的.若在D中存在弧xy,yz,在x和z之間總存在弧xz,那么稱(chēng)有向圖D是傳遞的.顯然每個(gè)傳遞有向圖是準(zhǔn)傳遞的,每個(gè)擴(kuò)張競(jìng)賽圖也是準(zhǔn)傳遞的.

為了簡(jiǎn)化準(zhǔn)傳遞有向圖上某些結(jié)論的證明,Bang-Jensen和Huang在文獻(xiàn)[13]中給出了這類(lèi)有向圖的結(jié)構(gòu)刻畫(huà).

定理2.1[13]設(shè)D是一個(gè)準(zhǔn)傳遞有向圖,則

(a)若D是非強(qiáng)連通的,則存在一個(gè)傳遞定向圖T,它的頂點(diǎn)集為{u1,u2,···,ut},還存在強(qiáng)連通的準(zhǔn)傳遞有向圖H1,H2,···,Ht,使得D=T[H1,H2,···,Ht],其中對(duì)于任意的i∈{1,2,···,t},Hi代替了ui.

(b)若D是強(qiáng)連通的,則存在一個(gè)強(qiáng)連通的半完全有向圖S,它的頂點(diǎn)集為{v1,v2,···,vs},還存在準(zhǔn)傳遞有向圖Q1,Q2,···,Qs,使得Qi不是單點(diǎn)就是非強(qiáng)連通的,且D=S[Q1,Q2,···,Qs],其中對(duì)于任意的i∈{1,2,···,s},Qi代替了vi.

定理2.1中描述的分解稱(chēng)為準(zhǔn)傳遞有向圖D的典型分解. '

圖1 一個(gè)非強(qiáng)連通的準(zhǔn)傳遞定向圖D的典型分解

更多有關(guān)準(zhǔn)傳遞定向圖的結(jié)論參看文獻(xiàn)[14-20].

本文研究的是Seymour二次鄰域猜想對(duì)于準(zhǔn)傳遞定向圖同樣適用,因?yàn)闇?zhǔn)傳遞定向圖是準(zhǔn)傳遞有向圖沒(méi)有2圈時(shí)的特殊情況,所以在運(yùn)用定理2.1時(shí),需要取其沒(méi)有2圈的情況,也就是要把準(zhǔn)傳遞有向圖用準(zhǔn)傳遞定向圖代替.同樣地,半完全有向圖用競(jìng)賽圖代替.

如圖所示,給出了一個(gè)非強(qiáng)連通準(zhǔn)傳遞定向圖D的典型分解,這個(gè)典型分解可表示為D=T[H1,H2,H3,H4],其中,T為一個(gè)傳遞定向圖,如圖2(a)所示;對(duì)于任意的i∈{1,2,3,4},Hi是強(qiáng)連通的準(zhǔn)傳遞定向圖.圖1中的大弧表示不同框集之間在顯示方向上有一個(gè)完全控制.

§3 準(zhǔn)傳遞定向圖和擴(kuò)張競(jìng)賽圖的Seymour點(diǎn)的關(guān)系

這部分考慮強(qiáng)連通準(zhǔn)傳遞定向圖的Seymour點(diǎn)與擴(kuò)張競(jìng)賽圖的Seymour點(diǎn)之間的關(guān)系.為此,先考慮圖1的最后一個(gè)強(qiáng)分支H4,它是一個(gè)強(qiáng)連通的準(zhǔn)傳遞定向圖,對(duì)于任意的i∈{1,2,···,s},用Qi的頂點(diǎn)集Vi代替Qi,得到一個(gè)擴(kuò)張競(jìng)賽圖,如圖2(b).容易驗(yàn)證,V1和V4中的點(diǎn)都是中的Seymour點(diǎn);x,y是Q1中的Seymour點(diǎn);z是Q4中的Seymour點(diǎn);x,y,z是H4中的Seymour點(diǎn).由此可得,Q1和Q4中的Seymour點(diǎn)都是H4中的Seymour點(diǎn).

圖2 傳遞定向圖T和擴(kuò)張競(jìng)賽圖

引理3.1設(shè)D是一個(gè)強(qiáng)連通的準(zhǔn)傳遞定向圖,它的典型分解為D=S[Q1,Q2,···,Qs].設(shè)D?=S[V1,V2,···,Vs]是一個(gè)擴(kuò)張競(jìng)賽圖,其中,對(duì)于任意的i∈{1,2,···,s},Vi是子有向圖Qi的頂點(diǎn)集.若存在一個(gè)頂點(diǎn)v∈Vi,使得v是Qi的一個(gè)Seymour點(diǎn),同時(shí)也是D?的一個(gè)Seymour點(diǎn),那么v也是D的一個(gè)Seymour點(diǎn).

證因?yàn)関是Qi中的一個(gè)Seymour點(diǎn),也是D?中的一個(gè)Seymour點(diǎn),則有

由于D?是擴(kuò)張競(jìng)賽圖,顯然有

§4 擴(kuò)張競(jìng)賽圖的Seymour點(diǎn)

這部分考慮擴(kuò)張競(jìng)賽圖上的Seymour點(diǎn).首先證明猜想1.1對(duì)擴(kuò)張競(jìng)賽圖是成立的.

定理4.1每個(gè)擴(kuò)張競(jìng)賽圖至少包含一個(gè)Seymour點(diǎn).

證設(shè)D=S[V1,V2,···,Vs]是一個(gè)擴(kuò)張競(jìng)賽圖,其中每個(gè)Vi都是一個(gè)獨(dú)立集.現(xiàn)用一個(gè)和Vi有相同頂點(diǎn)集的傳遞競(jìng)賽圖代替每個(gè)Vi,這樣就得到了一個(gè)新的有向圖D0.顯然,D0是一個(gè)競(jìng)賽圖,由定理1.1得,D0存在一個(gè)Seymour點(diǎn),設(shè)為x,即有又有

此外,定理1.2也可以推廣到擴(kuò)張競(jìng)賽圖中.事實(shí)上,可以得到更強(qiáng)的結(jié)論,即如果這兩個(gè)Seymour點(diǎn)在同一部集中,則至少有一個(gè)點(diǎn)的二次外鄰域的頂點(diǎn)個(gè)數(shù)嚴(yán)格大于一次外鄰域的頂點(diǎn)個(gè)數(shù).

定理4.2設(shè)D=S[V1,V2,···,Vs]是一個(gè)擴(kuò)張競(jìng)賽圖,且每個(gè)Vi是獨(dú)立集.若D中無(wú)出度為零的頂點(diǎn),則

(a)D中至少包含兩個(gè)Seymour點(diǎn);

(b)D中至少存在一個(gè)Seymour點(diǎn)x,使得,除非存在另一個(gè)和x在不同部集的Seymour點(diǎn)y.

證設(shè)D=S[V1,V2,···,Vs]是一個(gè)擴(kuò)張競(jìng)賽圖.現(xiàn)用一個(gè)和Vi有相同頂點(diǎn)集的傳遞競(jìng)賽圖代替每個(gè)Vi,這樣D就變成了一個(gè)新的競(jìng)賽圖T.因?yàn)镈無(wú)出度為零的頂點(diǎn),所以T的每個(gè)頂點(diǎn)出度也不為零.根據(jù)定理1.2,T中至少包含兩個(gè)Seymour點(diǎn)x,y,則顯然

則x,y也是D上的Seymour點(diǎn),故(a)成立.

若這兩個(gè)Seymour點(diǎn)x,y在不同的部集中,則(b)成立.故假設(shè)這兩個(gè)Seymour點(diǎn)x,y在相同的部集中,即有某個(gè)i∈{1,2,···,s},x,y∈Vi.不失一般性,假設(shè)在T中x控制y.因此

由此可得(b)成立.

§5 準(zhǔn)傳遞定向圖的Seymour點(diǎn)

這部分考慮準(zhǔn)傳遞定向圖上的Seymour點(diǎn).設(shè)D是一個(gè)準(zhǔn)傳遞定向圖,它的階數(shù)為n.表1列出了當(dāng)n=1,2,3時(shí)所有的準(zhǔn)傳遞定向圖,并在表1的第三行中指出對(duì)應(yīng)圖的Seymour點(diǎn).

表1 n=1,2,3時(shí)所有的準(zhǔn)傳遞定向圖及其Seymour點(diǎn)

下面證明猜想1.1對(duì)準(zhǔn)傳遞定向圖是成立的.

定理5.1每個(gè)準(zhǔn)傳遞定向圖至少包含一個(gè)Seymour點(diǎn).

證設(shè)D是一個(gè)準(zhǔn)傳遞定向圖,通過(guò)對(duì)D的階數(shù)n進(jìn)行歸納證明.參看表1,易知當(dāng)1≤n≤3時(shí),結(jié)論成立.現(xiàn)假設(shè)n≥4.

情形1D是非強(qiáng)連通的.

設(shè)D=T[H1,H2,...,Ht]是D的典型分解,其中,T是傳遞定向圖,且對(duì)i∈{1,2,···,t},Hi是強(qiáng)連通的準(zhǔn)傳遞定向圖.不失一般性,現(xiàn)假設(shè)H1,H2,···,Ht是D的強(qiáng)分支無(wú)圈序.通過(guò)歸納假設(shè),設(shè)x是Ht的Seymour點(diǎn),則.顯然

情形2D是強(qiáng)連通的.

設(shè)D=S[Q1,Q2,···,Qs]是D的典型分解,其中,S是強(qiáng)連通的競(jìng)賽圖,且對(duì)i∈{1,2,···,s},Qi是單點(diǎn)或者非強(qiáng)連通的準(zhǔn)傳遞定向圖.設(shè)D?=S[V1,V2,···,Vs]是一個(gè)擴(kuò)張競(jìng)賽圖,其中,對(duì)i∈{1,2,···,s},Vi都是子有向圖Qi的頂點(diǎn)集.由定理4.1可知,D?有一個(gè)Seymour點(diǎn)x.現(xiàn)假設(shè)x∈Vi,則Vi的每個(gè)頂點(diǎn)都是D?中的Seymour點(diǎn).由歸納假設(shè),Qi有一個(gè)Seymour點(diǎn),也記為x.則由引理3.1可知,x也是準(zhǔn)傳遞定向圖D中的一個(gè)Seymour點(diǎn).

根據(jù)定理5.1的證明,在圖1所示的準(zhǔn)傳遞定向圖D中,最后一個(gè)強(qiáng)分支H4中的Seymour點(diǎn)就是D中的Seymour點(diǎn).通過(guò)觀察,頂點(diǎn)x,y,z是H4中的Seymour點(diǎn),也是D中的Seymour點(diǎn).又注意到,在圖1所示的準(zhǔn)傳遞定向圖D中,每個(gè)頂點(diǎn)的出度都不為零,且D包含的 Seymour點(diǎn)多于1個(gè).現(xiàn)證明,定理1.2可以推廣到準(zhǔn)傳遞定向圖中.

定理5.2設(shè)D是準(zhǔn)傳遞定向圖,若D中無(wú)出度為零的頂點(diǎn),則D中至少包含兩個(gè)Seymour點(diǎn).

證現(xiàn)通過(guò)對(duì)D的階數(shù)n進(jìn)行歸納證明.顯然n≥3.參看表1,易知當(dāng)n=3時(shí),結(jié)論成立.現(xiàn)假設(shè)n≥4.

情形1D是非強(qiáng)連通的.

設(shè)D=T[H1,H2,···,Ht]是D的典型分解,其中,T是傳遞定向圖,且對(duì)i∈{1,2,···,t},Hi是強(qiáng)連通的準(zhǔn)傳遞定向圖.不失一般性,假定H1,H2,···,Ht是D的強(qiáng)分支無(wú)圈序.因?yàn)镈無(wú)出度為零的頂點(diǎn),所以最后一個(gè)分支Ht至少包含3個(gè)頂點(diǎn),即Ht是一個(gè)每個(gè)頂點(diǎn)出度都不為零的準(zhǔn)傳遞定向圖.通過(guò)歸納假設(shè),在Ht中至少包含兩個(gè)Seymour點(diǎn).因?yàn)镠t中的每一個(gè)Seymour點(diǎn)也是D的Seymour點(diǎn),所以D中至少包含兩個(gè)Seymour點(diǎn).

情形2D是強(qiáng)連通的.

設(shè)D=S[Q1,Q2,···,Qs]是D的典型分解,其中,S是強(qiáng)連通競(jìng)賽圖,且對(duì)i∈{1,2,···,s},Qi是單點(diǎn)或者非強(qiáng)連通的準(zhǔn)傳遞定向圖.設(shè)D?=S[V1,V2,···,Vs]是一個(gè)擴(kuò)張競(jìng)賽圖,這里對(duì)i∈{1,2,···,s},Vi是子有向圖Qi的頂點(diǎn)集.顯然D?是強(qiáng)連通的且無(wú)出度為零的頂點(diǎn).由定理4.2(b)可得,要么存在一個(gè)Seymour點(diǎn)x,使得;要么存在另一個(gè)和x在不同部集的Seymour點(diǎn)y.在后面這種情況下,D?有兩個(gè)屬于不同部集的Seymour點(diǎn),記這兩個(gè)部集為Vα和Vβ.由歸納假設(shè),對(duì)每個(gè)i∈{1,2,···,s},Qi都至少包含一個(gè)Seymour點(diǎn).特別地,Qα和Qβ中都包含Seymour點(diǎn).再由引理3.1可知,Qα和Qβ中的Seymour點(diǎn)也是D的Seymour點(diǎn).因此在這種情形下D包含兩個(gè)Seymour點(diǎn).

現(xiàn)考慮前面一種情形,即D?中存在一個(gè)Seymour點(diǎn)x,使得為了方便,設(shè)x∈V1.如上所述,Q1中的Seymour點(diǎn),仍記為x,也是D的Seymour點(diǎn).下面尋找D的另一個(gè)Seymour點(diǎn).

首先斷言部集V1中至少包含2個(gè)頂點(diǎn).否則,x是V1中的唯一頂點(diǎn).由定理4.2(a)知,D?中存在另一個(gè)不在V1的Seymour點(diǎn)y.如上所述,y所在的部集中必存在D的另一個(gè)Seymour點(diǎn).結(jié)論成立.故假設(shè)V1至少包含2個(gè)頂點(diǎn).

如果Q1至少包含兩個(gè)Seymour點(diǎn),則它們也是D中的Seymour點(diǎn).故假設(shè)Q1恰好只有一個(gè)Seymour點(diǎn)x.

現(xiàn)斷言V1中存在一個(gè)不同于x的頂點(diǎn)y,使得.設(shè)

是Q1的典型分解,其中,T1是一個(gè)傳遞定向圖,且對(duì)是強(qiáng)連通的準(zhǔn)傳遞定向圖.類(lèi)似地,假定是Q1的強(qiáng)分支無(wú)圈序.易知,是唯一的終止強(qiáng)分支,且x是中唯一的頂點(diǎn).否則,Q1中會(huì)有除x外的其它Seymour點(diǎn),與假設(shè)矛盾.由歸納假設(shè),在中存在一個(gè)Seymour點(diǎn)y,則.現(xiàn)有

從而斷言成立.

因?yàn)閥和x在D?的相同部集V1中,所以它們的外鄰域和二次外鄰域在D?中是相同的,從而不等式也成立.顯然

綜上所述,該定理成立.