圓的有向圖的全控制數(shù)

張 越,張新鴻

(太原科技大學(xué) 應(yīng)用科學(xué)學(xué)院,太原 030024)

1980年,全控制的概念被E.J.Cockayne等人提出[1]。1998年,Teresa Haynes、Stephen Hedetniemi和Peter Slater出版了兩本關(guān)于“控制”的圖書,其中首次對(duì)圖論中的控制理論、算法和應(yīng)用方面進(jìn)行了全面的分析和討論[2-3]。近年來,控制理論在通訊、計(jì)算機(jī)等很多方面也有了長足的發(fā)展[4-6]。

在有向圖D中,設(shè)S∈V(D),如果D中每個(gè)點(diǎn)都至少控制S中的一個(gè)點(diǎn),就稱S是D的一個(gè)全控制集,具有最小基數(shù)的全控制集稱為最小全控制集,其基數(shù)稱為全控制數(shù)。圓的有向圖D中v1,v2,…,vn滿足圓序,且每個(gè)頂點(diǎn)滿足:

{vi-d-(vi),…,vi-1},

其中i∈{1,2,…,n}.強(qiáng)連通是指在有向圖中,既有從x到y(tǒng)的途徑,也有從y到x的途徑[7-12]。文中未提及的概念或符號(hào)參看文獻(xiàn)[7].

1 圓的競賽圖的最小全控制集和全控制數(shù)

圓的競賽圖有n個(gè)頂點(diǎn),且滿足任意兩點(diǎn)間都有弧且不存在2圈的圖,其中頂點(diǎn)v1,v2,…,vn滿足圓序,下標(biāo)均模n.

定理1對(duì)于每個(gè)強(qiáng)連通競賽圖的任意一個(gè)頂點(diǎn),都包含一個(gè)通過它的k圈,其中k=3,4,…,n且n∈Z[8].

引理1設(shè)T是一個(gè)n階的競賽圖,則T的全控制數(shù)γt(D)≥3.

證明由全控制集的定義易知,T中任意一個(gè)頂點(diǎn)都不能構(gòu)成T的一個(gè)全控制集。任取T中兩個(gè)頂點(diǎn)vi,vj.因?yàn)門是一個(gè)競賽圖,故vi和vj之間有且僅有一條弧,不妨設(shè)vivj∈A(t).令M={vi,vj}.容易看出,M中不存在頂點(diǎn)v使得vi→v.由全控制集的定義可知,M不是T的一個(gè)全控制集,再由vi,vj的任意性,可知γt(D)≥3.

定理2若一個(gè)n階的圓的競賽圖D是強(qiáng)連通的,v1,v2,…,vn滿足圓序,則{vi,vj,vk}?V(D)是D的最小全控制集,當(dāng)且僅當(dāng)vi→vj→vk→vi,且所有頂點(diǎn)的下標(biāo)均是模n的。

證明(必要性)任取頂點(diǎn)子集M′={x,y,z}?V(D),且x,y,z不構(gòu)成D中的3圈,由D是一個(gè)競賽圖可知,M′中必有一個(gè)頂點(diǎn)被其它兩個(gè)頂點(diǎn)控制。不失一般性,設(shè)y→x,z→x.顯然,由全控制集的定義易知,M′中不存在頂點(diǎn)被點(diǎn)x控制,因此M′不是D的全控制集,(如圖1)。因?yàn)镈是一個(gè)競賽圖,所以由引理1可得到γt(D)≥3.

圖1 D是強(qiáng)連通的圓的競賽圖n=14

(充分性)因?yàn)槎ɡ?可知,D中存在3圈。任取D中的一個(gè)3圈,記作vi,vj,vk,vi,假設(shè)M={vi,vj,vk},下面可證M是D的一個(gè)最小的全控制集。由vi→vj以及D是一個(gè)圓的有向圖可知,v?→vj,其中?∈{i+1,i+2,…,j-1},又由于vj→vk,同理可知vβ→vk,其中β∈{j+1,j+2,…,k-1},又因?yàn)関k→vi,同時(shí)有vγ→vi,γ∈{k+1,k+2,…,i-1}.這樣,M就是D的一個(gè)最小全控制集。

定理3設(shè)一個(gè)有n個(gè)頂點(diǎn)v1,v2,…,vn的非強(qiáng)連通圓的有向圖D,其中v1,v2,…,vn滿足圓序,則D的全控制集是空集,全控制數(shù):γt(D)=0,且所有下標(biāo)均是模n的。

證明因?yàn)橛邢驁DD是非強(qiáng)連通的圓的有向圖,故在D中沒有圈,由全控制集的定義可知,n階的非強(qiáng)連通圓的有向圖沒有全控制集,那么其全控制集是空集,全控制數(shù):γt(D)=0.

2 強(qiáng)連通純粹局部競賽的圓圖的全控制數(shù)

純粹的局部競賽圖是局部競賽圖中除去競賽圖的剩余圖類,考慮到圓的有向圖中的純粹局部競賽圖的結(jié)構(gòu),給出以下定義。

有向圖D中,其中P=v1…vn作為D的一條有向路。如果存在vsvr∈A(D)滿足r-s≥2(s,r∈{1,2,…,n}),那么稱弧vsvr為路P上的一個(gè)跳躍弧,并且稱|r-s|為弧vsvr的跳躍度。假如在路P上沒有跳躍弧vsαvrα滿足關(guān)系sα

(1)|si+1-ri-1|≥2

(2)若不存在極大跳躍弧vsmvrm滿足si+1

(3)si

滿足以上定義可稱集合H為路P的一個(gè)極大跳躍弧閉包,稱頂點(diǎn)集{vs1,vs1+1,…,vrt}被H閉覆蓋。令Pm是P中一條子路,如果任何極大跳躍弧閉包不能覆蓋Pm上的所有頂點(diǎn),則Pm是P的一個(gè)純粹的子路。Pm為P的一條極大的純粹的子路時(shí),是當(dāng)沒有vα∈V(P)滿足D〈V(Pm)∪{vα}〉是P的純粹的子路,則Pm覆蓋V(Pm)中的所有頂點(diǎn)。

引理2設(shè)強(qiáng)連通圓的純粹局部競賽圖D=v1v2…vnv1是一個(gè)圈,如果只存在一條跳躍弧vsvr∈A(D),那么D的最小全控制集

{vs,vr,vr+1…,vs-1}∈V(D),

全控制數(shù):γt(D)=n-|r-s|+1,且所有下標(biāo)均模n.

證明如果在一個(gè)強(qiáng)連通純粹局部競賽圖中D=v1v2…vnv1是一個(gè)圈,存在一條跨弧vsvr,vs→vr,并且滿足r-s≥2(s,r∈{1,2,…,n})。假設(shè)M={vs,vr,vr+1,…,vs-1},下面可證M是D的一個(gè)最小全控制集。由vs→vr,且D是一個(gè)圓的有向圖知,vr→vr+1,且vi→vi+1→vi+2…→vi-1→vi(i∈{1,2,…,n}),(如圖2).同理可知,vα→vr,其中α∈{s,s+1,s+2,…,r-1}.這樣{vs,vr,vr+1…,vs-1}就為D的一個(gè)最小全控制集。

圖2 有一條跳躍弧閉包{vsvr}的14階強(qiáng)連通圓競賽圖D

任取頂點(diǎn)子集M′={vs,vr,vr+1…,vs-2}∈V(D)且此集合不構(gòu)成vs→vr→vr+1→vr+2…→vs-1→vs的一個(gè)圈,但不能在M′中找到被vs-2控制的點(diǎn),不符合全控制集的定義,所以M′中必然至少再存在一點(diǎn)被vs-2控制。不失一般性,有vs-2→vs-1.顯然知M′不是D的全控制集,那么全控制數(shù):γt(D)=n-|r-s|+1,顯然是D中最短圈的長。

|s1-v1|,且所有的下標(biāo)均是模n的。

證明在一個(gè)強(qiáng)連通的純粹局部競賽圖D中,C=v1v2…vnv1是D中的一個(gè)圈,若在圈C上存在一個(gè)極大跳躍弧閉包H={vsivri|i=1,2…,p},且任意vsi與vri都不重合,由圓的有向圖的定義可知,在圈C上只有v1→v2→…vn-1→vn→v1這樣的一個(gè)哈密爾頓圈,因?yàn)榇嬖趘si→vri,所以任取D中的一個(gè)圈,記為vsi→vri→vri+1→…→vsi-1→vsi,則V0={vs1,vr1,vr1+1,…,vs2-1,vs2,…,vsi,vri,vri+1…,si-1},再證V0是D的一個(gè)最小全控制集。

因?yàn)镈中存在i條跳躍弧vsvr,并且都有vsi→vri,v?→vri,且α∈{si,si+1,si+2,…,ri-1},同時(shí)滿足r-s≥2(s,r∈{1,2,…,n}),且任意vsi與vri都不相重合,跳躍弧之間均沒有交叉,又由于vs→vr且D是一個(gè)圓的有向圖知,有vr→vr+1及vi→vi+1→vi+2…→vi,(i,r∈{1,2,…,n}).這樣就有,V0成為D的一個(gè)最小全控制集。

γt(D)=

(如圖3).

圖3 有兩條跳躍弧的強(qiáng)連通圓純粹局部競賽圖

證明在一個(gè)強(qiáng)連通的圓的純粹局部競賽圖中,C=v1v2…vnv1是一個(gè)圈,若在圈C上存在一個(gè)極大跳躍弧閉包H={vsivri|i=1,2…,p},且任意vsi+1與vri重合,即跳躍弧是依次連接的,當(dāng)vn與vrn不重合時(shí),根據(jù)圓的有向圖定義知,在圈C上存在這樣v1→v2→…vn-1→vn→v1僅有的一個(gè)哈密爾頓圈,因?yàn)榇嬖趘si→vri,所以任意取D中的一個(gè)圈,記為vsi→vri→vri+1→…→vsi-1→vsi,則可以讓V0={vs1,vs2,…,vsi,vsi+1…,vs1-1},再證V0是D的最小全控制集。因?yàn)镈中存在i條跳躍弧vsvr,并且有vsi→vri,同時(shí)有v?→vri,α∈{si,si+1,si+2,,…,ri-1},且滿足r-s≥2(s,r∈{1,2,…,n}),構(gòu)成一個(gè)極大跳躍弧閉包H={vsivri|i=1,2,…,t},且任意vsi+1與vri都重合,跳躍弧之間均不存在交叉,由于vs→vr且D是一個(gè)圓的有向圖可知,得到v?→vri(?∈{si,si+1,si+2,…,ri-1}),(s,r∈{1,2,…,n-1}),那么D的最小全控制集是V0.

當(dāng)vn與vrn重合時(shí),有v?→vri,(?∈{si,si+1,si+2,…ri}),(i∈{1,2,…,n}),同理可得,D的全控制數(shù)γt(D)=i.(如圖4).

圖4 一個(gè)圓的純粹局部競賽圖D是強(qiáng)連通的,{v2v4}{v4v7}{v7v10}是其跳躍弧

引理5若D是一個(gè)n階的強(qiáng)連通圓的純粹局部競賽圖,其頂點(diǎn)集{v1,…,vn}滿足圓序。C=v1…vnv1作為D中的一個(gè)哈密爾頓圈。

如果圈C上存在一個(gè)極大跳躍弧閉包H={vsivri|i=1,2,…,t},其中跳躍弧vsi與vri之間是相互交叉的,且vsi+mi是只能被vsivri閉包的下標(biāo)最小的頂點(diǎn),那么D的全控制數(shù):

|n-rn|+|s1-v1|,i∈{1,2,…,n},

且所有下標(biāo)均是模n的。

證明由引理3的證明可知,當(dāng)一個(gè)n階強(qiáng)連通圓的純粹局部競賽圖存在跳躍弧交叉的情況下,對(duì)其進(jìn)行討論,(如圖5).這樣即得D的全控制數(shù):

圖5 存在交叉跳躍弧{vsivri}的圓純粹局部競賽圖D且是強(qiáng)連通的

γt(D)=

定理4如果D是一個(gè)包含n個(gè)頂點(diǎn)的強(qiáng)連通圓的純粹局部競賽圖,v1,v2,…,vn滿足圓序。D的一個(gè)哈密爾頓圈記為C=v1v2…vnv1.

如果圈C上存在h個(gè)極大跳躍弧閉包Hi={vsiavria|i=1,2,…,h;a=1,2,…,ti}.那么,D的全控制數(shù):

γt(D)=

其中vsia+mia是只能被極大跳躍弧vsiavria覆蓋的全部頂點(diǎn)的下標(biāo)最小的頂點(diǎn),且所有的下標(biāo)均是模n的。

證明在一個(gè)強(qiáng)連通的純粹的局部競賽圖中,C=v1v2…vnv1是一個(gè)圈,若在圈C上存在一個(gè)極大跳躍弧閉包H={vsivri|i=1,2…,p},根據(jù)引理2-5中的幾種跳躍弧類型構(gòu)成的不同跳躍弧閉包,圖形的結(jié)構(gòu)有所不同,但都有vsi→vri,以及v?→vri且α∈{si,si+1,si+2,…,ri-1}且滿足r-s≥2(s,r∈{1,2,…,n}),由于vs→vr且D是一個(gè)圓有向圖可知,v?→vri,(?∈{si,si+1,si+2,…ri-1}),(s,r∈{1,2,…,n-1}),這樣可得出D的一個(gè)最小全控制集是V0.

γt(D)=

得證。

3 圓的非局部的競賽圖的全控制數(shù)

因?yàn)閳A的非局部競賽圖至少有一點(diǎn)的內(nèi)鄰或外鄰不構(gòu)成競賽圖,所以一定有2圈,那么可知這類圖是強(qiáng)連通的。

定理5若D是一個(gè)包含n個(gè)頂點(diǎn)的強(qiáng)連通圓的非局部的競賽圖,頂點(diǎn)集{v1,v2,…,vn}滿足D的圓序,且存在vivjvi這樣的2圈。那么,全控制數(shù):γt(D)=g(D)=2.其中,i,j∈{0,1,…,n-1,n},并且所有下標(biāo)均是模n的。

證明首先可知D是圓的非局部的競賽圖,D中存在2圈,記作vivjvi,記M={vi,vj},下證M為D的最小全控制集。由vi→vj以及D是圓的有向圖可知,vχ→vi,其中χ∈{i+2,i+3,…,i-1}.

由于vδ→vj,其中δ∈{j+2,i+3,…,j-1}.這樣,{vi,vj}是D的最小全控制集。任取頂點(diǎn)子集M′={p,q}?V(D)且p,q不構(gòu)成D中的其他2圈,又因?yàn)镈是強(qiáng)連通的非局部競賽圖,M′中一定存在一點(diǎn)被其它的一個(gè)頂點(diǎn)控制。不失一般性,設(shè)p→q,q→p.顯然,由全控制集的定義可知,M′中的兩個(gè)頂點(diǎn)不能互相控制,因此M′不是D的全控制集。再由引理2可知,D的全控制數(shù):γt(D)=g(D)=2.(如圖6).

圖6 強(qiáng)連通圓的非局部的競賽圖D(n=13)

4 結(jié)論

定理6(Caccetta-H?ggkvist猜想)

設(shè)G是一個(gè)圖,那么γt(G)≥g(G)[13],其中γt(G)是圖G的全控制數(shù),g(G)表示圖G的圍長。

根據(jù)上面研究的結(jié)論可知,對(duì)于非強(qiáng)連通的圓的有向圖的全控制數(shù):γt(D)=0;對(duì)于強(qiáng)連通的圓的有向圖來說,其全控制數(shù)是它的圍長,這就說明對(duì)于這一圖類來說,Caccetta-H?ggkvist猜想所刻畫的界是緊的。