张 越,张新鸿
(太原科技大学 应用科学学院,太原 030024)
1980年,全控制的概念被E.J.Cockayne等人提出[1]。1998年,Teresa Haynes、Stephen Hedetniemi和Peter Slater出版了两本关于“控制”的图书,其中首次对图论中的控制理论、算法和应用方面进行了全面的分析和讨论[2-3]。近年来,控制理论在通讯、计算机等很多方面也有了长足的发展[4-6]。
在有向图D中,设S∈V(D),如果D中每个点都至少控制S中的一个点,就称S是D的一个全控制集,具有最小基数的全控制集称为最小全控制集,其基数称为全控制数。圆的有向图D中v1,v2,…,vn满足圆序,且每个顶点满足:
{vi-d-(vi),…,vi-1},
其中i∈{1,2,…,n}.强连通是指在有向图中,既有从x到y的途径,也有从y到x的途径[7-12]。文中未提及的概念或符号参看文献[7].
圆的竞赛图有n个顶点,且满足任意两点间都有弧且不存在2圈的图,其中顶点v1,v2,…,vn满足圆序,下标均模n.
定理1对于每个强连通竞赛图的任意一个顶点,都包含一个通过它的k圈,其中k=3,4,…,n且n∈Z[8].
引理1设T是一个n阶的竞赛图,则T的全控制数γt(D)≥3.
证明由全控制集的定义易知,T中任意一个顶点都不能构成T的一个全控制集。任取T中两个顶点vi,vj.因为T是一个竞赛图,故vi和vj之间有且仅有一条弧,不妨设vivj∈A(t).令M={vi,vj}.容易看出,M中不存在顶点v使得vi→v.由全控制集的定义可知,M不是T的一个全控制集,再由vi,vj的任意性,可知γt(D)≥3.
定理2若一个n阶的圆的竞赛图D是强连通的,v1,v2,…,vn满足圆序,则{vi,vj,vk}⊆V(D)是D的最小全控制集,当且仅当vi→vj→vk→vi,且所有顶点的下标均是模n的。
证明(必要性)任取顶点子集M′={x,y,z}⊆V(D),且x,y,z不构成D中的3圈,由D是一个竞赛图可知,M′中必有一个顶点被其它两个顶点控制。不失一般性,设y→x,z→x.显然,由全控制集的定义易知,M′中不存在顶点被点x控制,因此M′不是D的全控制集,(如图1)。因为D是一个竞赛图,所以由引理1可得到γt(D)≥3.
图1 D是强连通的圆的竞赛图n=14
(充分性)因为定理1可知,D中存在3圈。任取D中的一个3圈,记作vi,vj,vk,vi,假设M={vi,vj,vk},下面可证M是D的一个最小的全控制集。由vi→vj以及D是一个圆的有向图可知,v∂→vj,其中∂∈{i+1,i+2,…,j-1},又由于vj→vk,同理可知vβ→vk,其中β∈{j+1,j+2,…,k-1},又因为vk→vi,同时有vγ→vi,γ∈{k+1,k+2,…,i-1}.这样,M就是D的一个最小全控制集。
定理3设一个有n个顶点v1,v2,…,vn的非强连通圆的有向图D,其中v1,v2,…,vn满足圆序,则D的全控制集是空集,全控制数:γt(D)=0,且所有下标均是模n的。
证明因为有向图D是非强连通的圆的有向图,故在D中没有圈,由全控制集的定义可知,n阶的非强连通圆的有向图没有全控制集,那么其全控制集是空集,全控制数:γt(D)=0.
纯粹的局部竞赛图是局部竞赛图中除去竞赛图的剩余图类,考虑到圆的有向图中的纯粹局部竞赛图的结构,给出以下定义。
有向图D中,其中P=v1…vn作为D的一条有向路。如果存在vsvr∈A(D)满足r-s≥2(s,r∈{1,2,…,n}),那么称弧vsvr为路P上的一个跳跃弧,并且称|r-s|为弧vsvr的跳跃度。假如在路P上没有跳跃弧vsαvrα满足关系sα (1)|si+1-ri-1|≥2 (2)若不存在极大跳跃弧vsmvrm满足si+1 (3)si 满足以上定义可称集合H为路P的一个极大跳跃弧闭包,称顶点集{vs1,vs1+1,…,vrt}被H闭覆盖。令Pm是P中一条子路,如果任何极大跳跃弧闭包不能覆盖Pm上的所有顶点,则Pm是P的一个纯粹的子路。Pm为P的一条极大的纯粹的子路时,是当没有vα∈V(P)满足D〈V(Pm)∪{vα}〉是P的纯粹的子路,则Pm覆盖V(Pm)中的所有顶点。 引理2设强连通圆的纯粹局部竞赛图D=v1v2…vnv1是一个圈,如果只存在一条跳跃弧vsvr∈A(D),那么D的最小全控制集 {vs,vr,vr+1…,vs-1}∈V(D), 全控制数:γt(D)=n-|r-s|+1,且所有下标均模n. 证明如果在一个强连通纯粹局部竞赛图中D=v1v2…vnv1是一个圈,存在一条跨弧vsvr,vs→vr,并且满足r-s≥2(s,r∈{1,2,…,n})。假设M={vs,vr,vr+1,…,vs-1},下面可证M是D的一个最小全控制集。由vs→vr,且D是一个圆的有向图知,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的一个最小全控制集。 图2 有一条跳跃弧闭包{vsvr}的14阶强连通圆竞赛图D 任取顶点子集M′={vs,vr,vr+1…,vs-2}∈V(D)且此集合不构成vs→vr→vr+1→vr+2…→vs-1→vs的一个圈,但不能在M′中找到被vs-2控制的点,不符合全控制集的定义,所以M′中必然至少再存在一点被vs-2控制。不失一般性,有vs-2→vs-1.显然知M′不是D的全控制集,那么全控制数:γt(D)=n-|r-s|+1,显然是D中最短圈的长。 |s1-v1|,且所有的下标均是模n的。 证明在一个强连通的纯粹局部竞赛图D中,C=v1v2…vnv1是D中的一个圈,若在圈C上存在一个极大跳跃弧闭包H={vsivri|i=1,2…,p},且任意vsi与vri都不重合,由圆的有向图的定义可知,在圈C上只有v1→v2→…vn-1→vn→v1这样的一个哈密尔顿圈,因为存在vsi→vri,所以任取D中的一个圈,记为vsi→vri→vri+1→…→vsi-1→vsi,则V0={vs1,vr1,vr1+1,…,vs2-1,vs2,…,vsi,vri,vri+1…,si-1},再证V0是D的一个最小全控制集。 因为D中存在i条跳跃弧vsvr,并且都有vsi→vri,v∂→vri,且α∈{si,si+1,si+2,…,ri-1},同时满足r-s≥2(s,r∈{1,2,…,n}),且任意vsi与vri都不相重合,跳跃弧之间均没有交叉,又由于vs→vr且D是一个圆的有向图知,有vr→vr+1及vi→vi+1→vi+2…→vi,(i,r∈{1,2,…,n}).这样就有,V0成为D的一个最小全控制集。 γt(D)= (如图3). 图3 有两条跳跃弧的强连通圆纯粹局部竞赛图 证明在一个强连通的圆的纯粹局部竞赛图中,C=v1v2…vnv1是一个圈,若在圈C上存在一个极大跳跃弧闭包H={vsivri|i=1,2…,p},且任意vsi+1与vri重合,即跳跃弧是依次连接的,当vn与vrn不重合时,根据圆的有向图定义知,在圈C上存在这样v1→v2→…vn-1→vn→v1仅有的一个哈密尔顿圈,因为存在vsi→vri,所以任意取D中的一个圈,记为vsi→vri→vri+1→…→vsi-1→vsi,则可以让V0={vs1,vs2,…,vsi,vsi+1…,vs1-1},再证V0是D的最小全控制集。因为D中存在i条跳跃弧vsvr,并且有vsi→vri,同时有v∂→vri,α∈{si,si+1,si+2,,…,ri-1},且满足r-s≥2(s,r∈{1,2,…,n}),构成一个极大跳跃弧闭包H={vsivri|i=1,2,…,t},且任意vsi+1与vri都重合,跳跃弧之间均不存在交叉,由于vs→vr且D是一个圆的有向图可知,得到v∂→vri(∂∈{si,si+1,si+2,…,ri-1}),(s,r∈{1,2,…,n-1}),那么D的最小全控制集是V0. 当vn与vrn重合时,有v∂→vri,(∂∈{si,si+1,si+2,…ri}),(i∈{1,2,…,n}),同理可得,D的全控制数γt(D)=i.(如图4). 图4 一个圆的纯粹局部竞赛图D是强连通的,{v2v4}{v4v7}{v7v10}是其跳跃弧 引理5若D是一个n阶的强连通圆的纯粹局部竞赛图,其顶点集{v1,…,vn}满足圆序。C=v1…vnv1作为D中的一个哈密尔顿圈。 如果圈C上存在一个极大跳跃弧闭包H={vsivri|i=1,2,…,t},其中跳跃弧vsi与vri之间是相互交叉的,且vsi+mi是只能被vsivri闭包的下标最小的顶点,那么D的全控制数: |n-rn|+|s1-v1|,i∈{1,2,…,n}, 且所有下标均是模n的。 证明由引理3的证明可知,当一个n阶强连通圆的纯粹局部竞赛图存在跳跃弧交叉的情况下,对其进行讨论,(如图5).这样即得D的全控制数: 图5 存在交叉跳跃弧{vsivri}的圆纯粹局部竞赛图D且是强连通的 γt(D)= 定理4如果D是一个包含n个顶点的强连通圆的纯粹局部竞赛图,v1,v2,…,vn满足圆序。D的一个哈密尔顿圈记为C=v1v2…vnv1. 如果圈C上存在h个极大跳跃弧闭包Hi={vsiavria|i=1,2,…,h;a=1,2,…,ti}.那么,D的全控制数: γt(D)= 其中vsia+mia是只能被极大跳跃弧vsiavria覆盖的全部顶点的下标最小的顶点,且所有的下标均是模n的。 证明在一个强连通的纯粹的局部竞赛图中,C=v1v2…vnv1是一个圈,若在圈C上存在一个极大跳跃弧闭包H={vsivri|i=1,2…,p},根据引理2-5中的几种跳跃弧类型构成的不同跳跃弧闭包,图形的结构有所不同,但都有vsi→vri,以及v∂→vri且α∈{si,si+1,si+2,…,ri-1}且满足r-s≥2(s,r∈{1,2,…,n}),由于vs→vr且D是一个圆有向图可知,v∂→vri,(∂∈{si,si+1,si+2,…ri-1}),(s,r∈{1,2,…,n-1}),这样可得出D的一个最小全控制集是V0. γt(D)= 得证。 因为圆的非局部竞赛图至少有一点的内邻或外邻不构成竞赛图,所以一定有2圈,那么可知这类图是强连通的。 定理5若D是一个包含n个顶点的强连通圆的非局部的竞赛图,顶点集{v1,v2,…,vn}满足D的圆序,且存在vivjvi这样的2圈。那么,全控制数:γt(D)=g(D)=2.其中,i,j∈{0,1,…,n-1,n},并且所有下标均是模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的最小全控制集。任取顶点子集M′={p,q}⊆V(D)且p,q不构成D中的其他2圈,又因为D是强连通的非局部竞赛图,M′中一定存在一点被其它的一个顶点控制。不失一般性,设p→q,q→p.显然,由全控制集的定义可知,M′中的两个顶点不能互相控制,因此M′不是D的全控制集。再由引理2可知,D的全控制数:γt(D)=g(D)=2.(如图6). 图6 强连通圆的非局部的竞赛图D(n=13) 定理6(Caccetta-Häggkvist猜想) 设G是一个图,那么γt(G)≥g(G)[13],其中γt(G)是图G的全控制数,g(G)表示图G的围长。 根据上面研究的结论可知,对于非强连通的圆的有向图的全控制数:γt(D)=0;对于强连通的圆的有向图来说,其全控制数是它的围长,这就说明对于这一图类来说,Caccetta-Häggkvist猜想所刻画的界是紧的。 推荐访问:控制
