張新鴻，薛彩娟

（太原科技大學(xué) 應(yīng)用科學(xué)學(xué)院，山西 太原 030024）

0 引言

1962年，Ore提出了圖的控制集這一概念[1]，近年來，越來越多的學(xué)者們對控制集進(jìn)行了研究，圖的控制理論得到迅速的發(fā)展，并廣泛應(yīng)用于通信網(wǎng)絡(luò)、信息學(xué)等多方面，相關(guān)結(jié)論可以參看文獻(xiàn)[2-9]。

設(shè)D是一個(gè)具有n個(gè)頂點(diǎn)的有向圖，常記為D=(V，A)，其中V和A分別表示有向圖D的頂點(diǎn)集和弧集。有向圖控制集的研究可參看文獻(xiàn)[10-13]。有向圖D的階表示D中頂點(diǎn)的數(shù)目，記為|D|。如果uv是一條弧，那么稱u控制v（或v被u控制），記為u→v。對于V(D)中不交的頂點(diǎn)子集X和Y，X→Y表示X中的每一個(gè)頂點(diǎn)控制Y中的每一個(gè)頂點(diǎn)。定義

即(Y，X)D表示尾在Y中，頭在X中的弧集。X?Y表示(Y，X)D=?。X?Y表示X→Y和X?Y同時(shí)成立。給定有向圖D=(V，A)，對于頂點(diǎn)集T?V(D)，如果對每個(gè)頂點(diǎn)v∈V(D)T，至少存在一個(gè)頂點(diǎn)t∈T，使得tv∈A(D)，那么稱T是有向圖D的一個(gè)控制集[14]，其中所含頂點(diǎn)個(gè)數(shù)最少的控制集稱為D的最小控制集。

設(shè)v∈V(D)，定義集合，分別稱集合和為頂點(diǎn)v的外鄰集和內(nèi)鄰集。是以v為尾的所有弧的數(shù)目，稱為頂點(diǎn)v的外度是以v為頭的所有弧的數(shù)目，稱為頂點(diǎn)v的內(nèi)度。設(shè)V(H)?V(D)，A(H)?A(D)，如果兩個(gè)端點(diǎn)都在V(H)中的每一條弧都屬于A(H)，則稱H是由X=V(H)導(dǎo)出的，記為，也稱H為D的一個(gè)導(dǎo)出子圖。如果對于D的每一對不同的頂點(diǎn)x和y，總存在一條(x，y)途徑和(y，x)途徑，那么稱有向圖D是強(qiáng)連通的。

無2圈的有向圖稱為定向圖，任意兩個(gè)頂點(diǎn)均相鄰的定向圖稱為競賽圖。定向圖以及競賽圖的相關(guān)研究參看文獻(xiàn)[15-16]。每一對不同的頂點(diǎn)都相鄰的簡單圖稱為無向完全圖[17]。無向完全圖的雙定向圖稱為半完全有向圖。有向圖D是局部內(nèi)半完全的（局部外半完全的），如果對于D的每一個(gè)頂點(diǎn)x，它的全體內(nèi)鄰點(diǎn)（外鄰點(diǎn)）誘導(dǎo)出一個(gè)半完全有向圖。如果有向圖D既是局部內(nèi)半完全有向圖，又是局部外半完全有向圖，那么稱D是局部半完全有向圖。局部半完全有向圖的相關(guān)研究可參看文獻(xiàn)[18]。一個(gè)無2圈的局部半完全有向圖稱為局部競賽圖。局部競賽圖中除競賽圖以外的圖稱為純粹局部競賽圖。

給定一個(gè)n階有向圖D，如果它的頂點(diǎn)可標(biāo)號為v1，v2，…，vn，使得對每一個(gè)i∈ {1，2 ，…，n} ，

和

那么稱D是一個(gè)圓有向圖，稱頂點(diǎn)序v1，v2，…，vn是D的一個(gè)圓標(biāo)號，其中所有的下標(biāo)均是模n的。圓有向圖的相關(guān)研究參看文獻(xiàn)[19]。

定理1[20]每一個(gè)圓有向圖都是局部半完全的。

由定理1可知，圓有向圖屬于局部半完全有向圖。根據(jù)是否為競賽圖，可將圓的局部競賽圖分為圓的純粹局部競賽圖和圓競賽圖兩類。本文通過對圓的純粹局部競賽圖、圓競賽圖的研究，完全刻畫了圓局部競賽圖的最小控制集。

1 圓的純粹局部競賽圖的最小控制集

1.1 非強(qiáng)連通圓的純粹局部競賽圖的最小控制集

為敘述方便，我們進(jìn)行如下定義。設(shè)D是一個(gè)有向圖，P=v1…vn是D的一條有向路。如果存在弧vsvr∈A(D)滿足r-s≥2(s，r∈ {1，2，…，n})，則稱弧vsvr為路P的一條跨弧，并且稱|r-s|為弧vsvr的跨度。如果在路P上不存在跨弧vsαvrα使得sα＜s＜r＜rα，那么就稱跨弧vsvr為路P上的一條極大跨弧。如果存在路P的一個(gè)跨弧集合H=滿足：(1)|si+1-ri-1|≥2；(2)不存在極大跨弧vsmvrm使得si+1＜sm≤ri＜ri+1＜rm；(3)si＜si+1≤ri＜ri+1，或者si＜ri＜si+1＜ri+1且si+1-ri=1，那么稱集合H為路P上的一個(gè)極大跨弧覆蓋，稱頂點(diǎn)集被H覆蓋。設(shè)Pm是P的一條子路，如果Pm上的所有頂點(diǎn)均不被任何極大跨弧覆蓋所覆蓋，則稱Pm為P的一條純粹子路。若不存在vα∈V(P)使得是P的純粹子路，則稱Pm為P的一條極大純粹子路，稱V(Pm)中的所有頂點(diǎn)被Pm覆蓋，如圖1。

圖1 {vs1vr1，vs2vr2}為P=v1v2...v19上的一個(gè)極大跨弧覆蓋，{vs3vr3}是P上一個(gè)只含一條極大跨弧的極大跨弧覆蓋Fig.1 {vs1vr1，vs2vr2}is a maximal cross arc onP=v1v2…v19，{v s 3vr3} is a maximal cross arc cover with one maximal cross arc on P

由非強(qiáng)連通性可知，頂點(diǎn)vn與v1之間不存在弧。由圓有向圖的定義可知，必有vi→vi+1，其中，i∈{1，2，…，n-1}，因此非強(qiáng)連通圓的純粹局部競賽圖必存在一條哈密爾頓路。根據(jù)非強(qiáng)連通圓的純粹局部競賽圖的結(jié)構(gòu)，我們可以得到下面的結(jié)論。

引理1設(shè)非強(qiáng)連通圓的純粹局部競賽圖D=v1v2…vn是一條路。當(dāng)n=2k時(shí)，D的最小控制集為{vα|α=1，3，…，2k-1}；當(dāng)n=2k+1 時(shí)，D的最小控制集為

圖2 一個(gè)16階的非強(qiáng)連通圓的純粹局部競賽圖D，{vs1vr1，vs2vr2，vs3vr3}構(gòu)成了一個(gè)極大跨弧覆蓋，vs3+m3是只能被極大跨弧vs3vr3覆蓋的所有頂點(diǎn)中下標(biāo)最小的頂點(diǎn)Fig.2 Around pure local tournamentDwithn=16which is non-strong ，{vs1vr1，vs2vr2，vs3vr3}form a maximal cross arc cover，vs3+m3is a vertex with the smallest subscript which is only covered by cross arcvs3vr3

或

其中m∈ {1，3，5，…，2k-1}，k∈Z+。

證明因?yàn)镈是一條路，所以顯然有vi→vi+1，1≤i≤n-1。

情形1n=2k。

設(shè)頂點(diǎn)集T={vα|α=1，3，…，2k-1}。首先證明T是D的最小控制集。由vi→vi+1可知，T是D的控制集，其中i∈{1，2，…，n-1}。任取頂點(diǎn)集T'={vi1，vi2，vi3，…，vi|T|-1}知|T'|=|T|-1。不妨設(shè)i1＜i2＜…＜i|T|-1。(1)若?t∈ {1，2，…，|T|-2}，有|it+1-it|≤2，則由D是一條路可知，T'不能控制頂點(diǎn)vi|T|-1；(2)若?t∈ {1，2，…，|T|-1}，有it-it-1≥3，則由D是一條路可知，vit-1必不被頂點(diǎn)集T'控制。因此，D的最小控制集為T={vα|α=1，3，…，2k-1} 。再證唯一性。假設(shè)T1是D的一個(gè)最小控制集且T1≠T，則至少存在一個(gè)頂點(diǎn)vp∈TT1，其中p∈{1，3，…，2k-1}。 如果vp-1∈T1，那么由D是一條路及T1是D的最小控制集可知，T1不能控制vp+1；同理，如果vp+1∈T1，那么T1不能控制vp；如果{vp-1，vp+1}?T1，那么T1不能控制vp。故T是D唯一的最小控制集。

情形2n=2k+1。

取頂點(diǎn)集T={vβ|β=1，3，…，2k+1}或 {vβ|β=1，…，m-2，m，m+1，m+3，…，2k}。由

可知，T是D的控制集。由n=2k時(shí)的證明可同理得，此時(shí)T是D的最小控制集。

引理2設(shè)D是一個(gè)n階非強(qiáng)連通圓的純粹局部競賽圖，v1，v2，…，vn是D的一個(gè)圓標(biāo)號。P=v1v2…vn是D的哈密爾頓路。如果路P上存在一個(gè)極大跨弧覆蓋H={vsivri|i=1，2，…，t}，那么，DV0的最小控制集為{vαi|i=1，2，…，t}，其中αi∈ {si，si+1，…，si+mi}且vsi+mi是只能被vsivri覆蓋的下標(biāo)最小的頂點(diǎn)，Vo={vs1，vs1+1，…，vrt}。

圖3 (1)一個(gè)16階的非強(qiáng)連通圓的純粹局部競賽圖D，其中t1=1，t2=1；(2)一個(gè)19階的非強(qiáng)連通圓的純粹局部競賽圖D，其中t1=2，t2=2Fig.3 （1）Around pure local tournament withn=16 which is non-strong，t1=1，t2=1；（2）Around pure local tournament with n=19 which is non-strong，t1=2，t2=2

1.2 強(qiáng)連通圓的純粹局部競賽圖的最小控制集

設(shè)D是一個(gè)強(qiáng)連通圓的純粹局部競賽圖，v1，v2，…，vn是D的一個(gè)圓標(biāo)號，所有下標(biāo)均是模n的。設(shè)C是圖D的一個(gè)長度至少為4的有向圈。連接圈上任意兩個(gè)不相鄰頂點(diǎn)的弧稱為圈C的跨弧，即跨弧vsvr滿足 |r-s|≥2(s，r∈{1，2，…，m})，稱|r-s|為跨弧vsvr的跨度。設(shè)vsvr是圈C的一條跨弧，如果在圈C上不存在跨弧vsαvrα使得sα＜s＜r＜rα(rα＜r＜s＜sα)，那么就稱跨弧vsvr為圈C上的一條極大跨弧。如果存在圈C的一個(gè)跨弧集合H={vsivri|i=1，…，t}滿足：(1)|si+1-ri-1|≥2，(2)不存在極大跨弧vsmvrm使得si+1＜sm≤ri＜ri+1＜rm；(3)si＜si+1≤ri＜ri+1，或者si＜ri＜si+1＜ri+1且si+1-ri=1，那么稱集合H為圈C上的一個(gè)極大跨弧覆蓋，稱頂點(diǎn)集被H覆蓋。設(shè)Pm是C的一條子路，如果Pm上的所有頂點(diǎn)均不被任何極大跨弧覆蓋所覆蓋，則稱Pm為C的一條純粹子路。若不存在vα∈V(C)使得是C的純粹子路，則稱Pm為C的一條極大純粹子路，稱Pm中的所有頂點(diǎn)被Pm覆蓋。如圖4。

圖4 一個(gè)13階的強(qiáng)連通圓的純粹局部競賽圖D，其中{vs1vr1，vs2vr2}構(gòu)成一個(gè)極大跨弧覆蓋，v5v8不屬于極大跨弧覆蓋，P=v10v11v12v13v1是圈C的一條極大純粹子路Fig.4 Around pure local tournamentD，{vs1vr1，vs2vr2}form a maximal cross arc cover，andv5v8is not included in a maximal cross arc cover，P=v10v11v12v13v1is a maximal purely subpath on cycleC

引理3設(shè)強(qiáng)連通圓的純粹局部競賽圖D=v1v2...vnv1是一個(gè)圈。那么D的最小控制集為：當(dāng)n=2k時(shí)，D的最小控制集為{vα|α=1，3，…，2k-1}，或{vα|α=2，4，…，2k}；當(dāng)n=2k+1 時(shí) ，D的最小控制集為

其中，k∈Z+，所有的下標(biāo)均是模n的。

證明因?yàn)镈是一個(gè)非強(qiáng)連通圓的局部競賽圖，且C=v1v2…vnv1是D的唯一哈密爾頓圈，所以有vi→vi+1，1≤i≤n-1。下面分兩種情形證明結(jié)論成立。

情形1n=2k。

取頂點(diǎn)集T={vα|α=1，3，…，2k-1}。首先證明T是D的一個(gè)最小控制集。由vi→vi+1，1≤i≤n-1，可知，T是D的控制集。任取頂點(diǎn)集T'={vis|s=1，2，…，|T|-1}，并且|T'|=|T|-1。不妨設(shè)i1＜i2＜…＜i|T|-1。(1)若?t∈ {2，…，|T|-1}，有|it-it-1|≤2，則由D是一個(gè)哈密爾頓圈可知，T'不能控制頂點(diǎn)vi|T|-1；(2)若?t∈ {1，2，…，|T|-1}，有|it-it-1|≥3，則由D是一個(gè)哈密爾頓圈可知，T'不能控制vit-1。因此，由T'的任意性可知，T是D的一個(gè)最小控制集。再證唯一性。假設(shè)T1是D的一個(gè)最小控制集且T1≠T，則至少存在一個(gè)頂點(diǎn)vp∈TT1，其中p∈{1，3，…，2k-1} 或p∈{2，4，…，2k}。如果vp-1∈T1，那么由D是一個(gè)圈可知，T1不能控制vp+1；同理，如果vp+1∈T1，那么T1不能控制vp；如果{vp-1，vp+1}?T1，那么T1不能控制vp。故T是D唯一的最小控制集。

情形2n=2k+1。

由vi→vi+1，1≤i≤n-1，可知，T是D的控制集。由n=2k時(shí)的證明可同理得，此時(shí)T是D的最小控制集。

引理4設(shè)D是一個(gè)n階強(qiáng)連通圓的純粹局部競賽圖，v1，…，vn是D的一個(gè)圓標(biāo)號。C=v1…vnv1是D的一個(gè)哈密爾頓圈。如果圈C上存在一個(gè)極大跨弧覆蓋，那么的最小控制集為，其中αi∈{si，si+1，…，si+mi}且vsi+mi是只能被vsivri覆蓋的下標(biāo)最小的頂點(diǎn)且所有的下標(biāo)均是模n的，V0=。

證明首先證明是D最小控制集。因?yàn)樗杂蓤A有向圖的定義可知，由引理2可知，的控制集，令任取M?V0且|M|=t-1，則存在μ∈{1，…，t}使得Aμ∩M=?。由H是一個(gè)極大跨弧覆蓋可知，對任意的都有v不能控制vμ，其中vμ∈Aμ。又由于存在只被極大跨弧覆蓋，故vγ不能控制，γ∈ {s1，s1+1，…，sμ-1}。因此，M不能控制。由M的任意性可知是的最小控制集（如圖5）。設(shè)再證唯一性。任取頂點(diǎn)集，則至少存在一個(gè)頂點(diǎn)有

圖5 一個(gè)13階的強(qiáng)連通圓的純粹局部競賽圖D，其中{v2v6，v7v11}構(gòu)成一個(gè)極大跨弧覆蓋，vs1+m1是只能被極大跨弧vs1vr1覆蓋的所有頂點(diǎn)中下標(biāo)最小的頂點(diǎn)Fig.5 Around pure local tournamentDwithn=13which is strong，{v2v6，v7v11}form a maximal cross arc cover，vs1+m1is a vertex with the smallest subscript which is only covered by cross arcvs1vr1

那么T0不能控制，所以的最小控制集為T。

定理3設(shè)D是一個(gè)n階強(qiáng)連通圓的純粹局部競賽圖，v1，v2，…，vn是D的 一個(gè)圓標(biāo)號。C=v1v2…vnv1是D的哈密爾頓圈。如果圈C上存在h個(gè)極大跨弧覆蓋

那么，D的最小控制集為

是D的最小控制集（如圖6）。

圖6 (1)一個(gè)13階的強(qiáng)連通圓的純粹局部競賽圖D，其中v2v5，v7v11是兩個(gè)只包含一條極大跨弧的跨弧覆蓋；(2)一個(gè)17階的強(qiáng)連通圓的純粹局部競賽圖D，并且t1=2，t2=2Fig.6 （1）Around pure local tournamentDwithn=13which is strong，v2v5，v7v11are two cross arc cover with a maximal cross arc；(2)Around pure local tournamentDwithn=17which is strong，andt1=2，t2=2

再證唯一性。

2 圓競賽圖的最小控制集

引理5設(shè)D是一個(gè)n階強(qiáng)連通圓競賽圖，v1，v2，…，vn是D的一個(gè)圓標(biāo)號，則D的最小控制集為{vs，vr}，其中vs，vr兩個(gè)頂點(diǎn)滿足vr=vs-d-(vs)或vs=vr-d-(vr)，并且所有的下標(biāo)均是模n的。

證明任取頂點(diǎn)vs∈V(D)，因?yàn)镈是圓競賽圖，所以vs不能控制vs-1，故vs不是圓競賽圖D的控制集。因此，圓競賽圖D的最小控制集至少包含兩個(gè)頂點(diǎn)。由于D是強(qiáng)連通圓競賽圖，故存在一點(diǎn)vr→vs，不妨設(shè)vr=vs-d-(vs)，則由強(qiáng)連通圓競賽圖的定 義 可 知 ，vs→ {vs+1， }vs+2，…，vr-1，vr→vs，因 此 ，{vs，vr}是D的控制集，所以，D的最小控制集包含兩個(gè)頂點(diǎn)（如圖7）。

圖7 一個(gè)13階的強(qiáng)連通圓競賽圖DFig.7 A strong round tournamentDwithn=13

引理6設(shè)D是一個(gè)n階強(qiáng)連通圓競賽圖，v1，v2，…，vn是D的一個(gè)圓標(biāo)號，對任意的頂點(diǎn)vα∈V(D)，必存在頂點(diǎn)vβ∈V(D)，使得{vα，vβ}是D的一個(gè)最小控制集。

定理4設(shè)D是一個(gè)n階強(qiáng)連通圓競賽圖，v1，v2，…，vn是D的一個(gè)圓標(biāo)號，則D的最小控制集為其中，t∈{1，2，…，n}，并且所有的下標(biāo)均是模n的。

證明由D是一個(gè)強(qiáng)連通的競賽圖可知，|V(D)|≥3，并且對任取的vt∈V(D)，都有d+(vt)≤n-2。下面分兩種情形進(jìn)行證明。如圖8。

圖8 一個(gè)13階的強(qiáng)連通圓競賽圖DFig.8 Astrong round tournamentDwithn=13

情形 1d+(vt)＜n-2，t∈ {1，2，…，n}。

因?yàn)镈是強(qiáng)連通的，所以N-(vt)≠?。又D是一個(gè)強(qiáng)連通的圓競賽圖，不妨設(shè)由D是圓的競賽圖可知，這樣就有

若m=v，則。否則，有。任取頂點(diǎn)，易知

這樣{vt，vk}是D的一個(gè)控制集。再由引理5可知，{vt，vk}是D的最小控制集。

情形 2d+(vt)=n-2，t∈ {1，2，...，n}。

由d+(vt)=n-2可知，d-(vt)=1。因此，N-(vt)={vt-1}，即vt? {vt+1，vt+2，…，vt-2}。再由引理 5，立刻就有{vt，vt-1}構(gòu)成D的一個(gè)最小控制集。又D是一個(gè)強(qiáng)連通的圓競賽圖，此時(shí)N-(vt-1)∩N+(vt)≠?。任取vk∈ (N+(vt)∩N-(vt-1))，由情形1可知{vt，vk}構(gòu)成D的一個(gè)最小控制集。

任取頂點(diǎn)vp?(N+(vt)∩N-(vt-1))∪{vv}。 若vp∈ {vt+1，vt+2，…，vm-1}，則由vm=vt-1-d-(vt-1)和強(qiáng)連通圓競賽圖的定義可知，vt和vp都不能控制vt-1，即{vt，vp}不是D的控制集。若vp∈ {vv+1，vv+2，…，vt-2}，則由vv=vt-d-(vt)可 知 ，vv? {vv+1，vv+2，…，vt-1，vt}，故{vt，vp}不能控制vv，即{vt，vp}不是D的控制集。因此，{vt，vk}是D的最小控制集，

其中，t∈{1，2，…，n}。

定理5設(shè)D是一個(gè)n階非強(qiáng)連通的圓競賽圖，v1，v2，…，vn是D的一個(gè)圓標(biāo)號，則D的最小控制集為{v1}。

證明由D是非強(qiáng)連通的圓競賽圖，得v1?vi，i∈{2，3，…，n}，故D的最小控制集為{v1}。