黄宇飞

(广州民航职业技术学院人文社科学院, 广州 510403)

组合矩阵论[1]的核心是对矩阵中元素的位置而非数值的研究,即矩阵的组合性质. 本文定义集合{0,1,-1,#}中元素的加法和乘法为:

其中，“#”表示符号不确定的元素(又称模糊符号)[2]. 本文把元素分别取自于集合{0,1}、{0,1,-1}和{0,1,-1,#}的矩阵分别称为(0,1)矩阵、符号矩阵和广义符号矩阵. 基于上述定义,(广义)符号方阵A可分为2类[1]:如果A的幂序列A,A2,…均不含模糊符号#,那么A称为可幂的;否则,A称为不可幂的.

一个n阶(0,1)方阵A是本原的当且仅当存在正整数t使得At=Jn,其中Jn是所有元素均为1的n阶方阵[1]. 把一个(广义)符号矩阵A的所有非零元都换成1,所得的(0,1)矩阵记为|A|. 那么,|A|完全决定了(广义)符号矩阵A的零位模式. 进而,称(广义)符号方阵A是本原的,如果|A|是本原的.

考察一个n阶(广义)符号方阵A的幂序列:A,A2,A3,…,因为(广义)符号方阵对于乘法成一个有限半群,所以A的幂序列中必然会出现相同的项. 记最先重复出现的是Ab=Ab+p,其中b和p都是正整数. 称p=p(A)为A的周期,b=b(A)为A的基指数[3]. 文献[4]证明了:一个n阶本原不可幂(广义)符号方阵A的基指数b(A)=min{t|At=#Jn},周期p(A)=1,其中#Jn表示所有元素均为#的n阶方阵. 易见,本原不可幂(广义)符号方阵A的幂序列中,Ab(A)是具有结构性质“所有元素都是#”的最小指数幂. 于是,受此启发并考虑到本原不可幂(广义)符号方阵幂序列中#元位置结构更精细的刻画, 若干文献分别定义了k点-基指数[5]、k点-同位基指数[5]、第k重下-基指数[5]、第k重上-基指数[5]、ω-不可分基指数[6]. 文献[7-8]将上述指数归纳统称为本原不可幂(广义)符号矩阵的结构指数,并指出了它们在非记忆通讯系统中的若干应用.

众所周知,一个n阶(广义)符号矩阵A=(aij)可以和一个n阶(广义)带号有向图S=(V,E)一一对应:有向弧vivj存在与否取决于aij是否非零;而有向弧vivj若存在则其符号取决于元素aij的值,即有向弧vivj的符号sgn(vivj)=aij,其中顶点集V={v1，v2，…，vn},且1≤i,j≤n. 称A为S邻接(广义)符号矩阵,S为A的伴随(广义)带号有向图. 为方便起见,称一个(广义)带号有向图是本原的/不可幂的,如果其邻接(广义)符号矩阵是本原的/不可幂的;并且后文将直接采用“本原不可幂(广义)带号有向图的某结构指数”的表述形式.

鉴于“环”在结构指数问题研究中的特殊功效,本文定义了2类特殊的广义带号有向图:含交圈结构/含违规交圈结构的本原不可幂广义带号有向图,主要研究k点-基指数、k点-同位基指数、第k重下-基指数、第k重上-基指数及ω-不可分基指数分别在含交圈结构/含违规交圈结构的本原不可幂广义带号有向图类限制下的上界估值问题.

1 概念与定义

设A是n阶本原不可幂的(广义)符号方阵, 且k,,l{1,2,…,n}.

(i)A的k点-基指数[5],记为l(A,k),是最小的正整数t,使得At中存在每行至少有个#元的k×n子阵. 特别地,k点n-基指数又称为k点基指数[9-11],n点n-基指数(即n点基指数)正是上文已定义的基指数[2].

(ii)A的k点-同位基指数[5],记为φ(A,k), 是最小的正整数t,使得At中存在所有元素都是#的k×子阵. 特别地,k点n-同位基指数也恰是k点基指数[9-11], 从而n点n-同位基指数也是基指数[2].

(iii)A的第k重下-基指数[5],记为ψ(A,k),是最小的正整数t,使得At中存在有列含#元的k×n子阵. 特别地,第k重下n-基指数又称为第k重下基指数[12].

(iv)A的第k重上-基指数[5],记为L(A,k), 是最小的正整数t,使得At中任意k×n子阵均有列含#元. 特别地,第k重上n-基指数又称为第k重上基指数[13],而第1重上-基指数恰好是上述的n点-基指数[5].

(v)A的ω-不可分基指数[6],记为εω(A),是最小的正整数t,使得At中任一满足k+l=n-ω+1的k×l子阵皆含#元,其中ω{0,1,…,n-1}. 特别地,0-不可分基指数又称为Hall基指数[6],1-不可分基指数又称为完全不可分基指数[6],而(n-1)-不可分基指数恰是基指数[2].

不难发现,n阶本原不可幂(广义)符号方阵A的基指数的存在性[4]保证了上述5类指数均是有意义的(必为有限值).

设SRt(X)表示从点子集X中的任意点出发,经过长为t的SSSD途径对(或符号为“#”的途径)所能到达的所有点的集合,又称其为模糊可达集[5]. 根据上述5类结构指数的定义,有如下关于它们的图论刻画.

命题1[5-6]设S是n阶本原不可幂(广义)带号有向图,且k,{1,2,…,n}，则

(i)S的k点-基指数l(S,k)是最小的正整数t,使得存在k点子集X⊆V(S)，满足∀xX均有|SRt({x})|≥.

(ii)S的k点-同位基指数φ(S,k)是最小的正整数t,使得存在k点子集X⊆V(S)及{v1,v2,…,v}⊆V(S),满足∀xX均有SRt({x})⊇{v1,v2,…,v}.

(iii)S的第k重下-基指数ψ(S,k)是最小的正整数t,使得存在k点子集X⊆V(S)，满足|SRt(X)|≥.

(iv)S的第k重上-基指数L(S,k)是最小的正整数t,使得对于任意的k点子集X⊆V(S)，均满足|SRt(X)|≥.

(v)S的ω-不可分基指数εω(S)是最小的正整数t,使得对于任一满足 1≤|X|=k≤min{n,n-ω}的k点子集X，都有|SRt(X)|≥k+ω,其中,ω{0,1,…,n-1}.

命题2[7]设S是n阶本原不可幂(广义)带号有向图,且k,{1,2,…,n},则

(i)l(S,1)=φ(S,1)=ψ(S,1),l(S,n)=L(S,1),ψ(S,n)=L(S,n).

(ii)ln(S,k)=φn(S,k).

(iii)ln(S,n)=φn(S,n)=Ln(S,1)=εn-1(A)=b(S).

(iv)ψ(S,n-k+1)≤L(S,n-k+1)≤l(S,k)≤φ(S,k).

记n阶本原不可幂广义带号有向图的集合为PSn,又记恰含d个环的n阶本原不可幂广义带号有向图的集合为PSn(d),其中d{1,2,…,n}. 考虑到上述提到的若干结构指数几乎都解决了其在图类PSn(d)限制下的上界估值问题,究其原因主要在于环点的特殊功效. 又注意到:一个n阶广义带号有向图S是本原的当且仅当它的底图D是n阶强连通有向图,且D中所有不同圈长的最大公因数等于1(这里,一个广义带号有向图的底图是指把广义带号有向图每条弧的符号均舍去后所得的一般有向图)[1,7]. 因此,对图类PSn(d)进行推广,定义了如下的广义带号有向图类.

定义1设S是本原不可幂广义带号有向图,且C={C1,C2,…,Cs} (s≥2)是S中若干不同长度的有向圈构成的一个集合. 记有向圈Cq的长度为cq(q=1,2,…,s),不妨设c1>c2>…>cs≥1. 记={c1,c2,…,cs},若g.c.d.()∶=g.c.d.(c1,c2,…,cs)=1 (这里,g.c.d.是最大公因数的缩写,后文均默认采用此记号),且则称S为含交圈结构的本原不可幂广义带号有向图.

下述关于本原不可幂(广义)带号有向图的刻画是研究若干结构指数的重要工具之一.

引理1[4]设S是本原带号有向图,则S是不可幂的当且仅当S包含2个有向圈C1和C2,其长度分别记为p1和p2,满足以下2个条件之一:

(B1)p1是偶数,p2是奇数,且sgn(C1)=-1;

(B2)p1和p2都是奇数,且sgn(C1)=-sgn(C2).

我们称这样一对满足条件(B1)或(B2)的有向圈C1和C2为“违规圈对”. 由此还可推出:途径对W1=p2C1和W2=p1C2的长度均为p1p2,但符号相异,即 (sgn(C1))p2=-[(sgn(C2))p1].

进一步地,设S是本原广义带号有向图. 那么,S是不可幂的当且仅当S包含违规圈对,或者S含有符号为“#”的弧.

注1根据引理1,在研究本原不可幂广义带号有向图S时需要考虑2种情况:(1)S包含违规圈对；(2)S含有符号为“#”的弧. 在研究本原不可幂带号有向图时仅需考虑情况(1)，因此,为了行文清晰,下文在阐述有关结果时的描述对象仅限于本原不可幂广义带号有向图,但实际上，本原不可幂带号有向图的有关结果已包含其中.

考虑到引理1关于本原不可幂广义带号有向图的刻画,进一步对定义1的条件加以限制,定义了另一广义带号有向图类.

定义2设S是本原不可幂广义带号有向图,且C={C1,C2,…,Cs} (s≥2)是S中若干不同长度的有向圈构成的一个集合,记有向圈Cq的长度为cq(q=1,2,…,s),不妨设c1>c2>…>cs≥1. 记={c1,c2,…,cs},若g.c.d.()含有违规圈对或符号为“#”的有向圈,则称S为含违规交圈结构的本原不可幂广义带号有向图.

注3设S因为g.c.d.(c1,c2,…,cs)=1,所以C中必然存在一个奇有向圈,不妨记之为C′. 因为s≥2,根据定义2并结合违规圈对的定义, 可设C中含满足以下2个条件之一的有向圈C*: (1)C*与C′构成违规圈对(若C中含有满足引理1的条件(B1)的违规圈对C1和C2，令C*为违规圈对中符号为负的偶有向圈C1,则C*与C′将再次构成违规圈对;若C中含有满足引理1的条件(B2)的违规圈对C1和C2,由于C1和C2符号相异,不失一般性,不妨设C2与C′符号相异,令C*为C2,注意到此时C*与C′均为奇有向圈,则C*与C′再次构成违规圈对). (2)C*的符号为“#”(此时C*和C′可以是同一个有向圈).

注4设SCIPSn. 因为g.c.d.(c1,c2,…,cs)=1 (s≥2),所以C中必然存在一个奇有向圈,不妨记之为C′. 类似于注3的说明,再根据定义1并结合违规圈对的定义,可设S中(不一定在C中)含满足以下2个条件之一的有向圈C*:(1)C*与C′构成违规圈对;(2)C*的符号为“#”.

为简略起见,后文有关叙述(包括定理及其证明)中若假设S或SCIPSn),默认采用定义2(或定义1)中的有关记号而不再赘述;另外,默认k,{1,2,…,n},且ω{0,1,…,n-1}.

2 主要结果及其证明

为了刻画本文的主要结论,下面先阐述若干通用的工具引理. 设SPSn,={c1,c2,…,cs} (s≥2)是S中若干不同圈长之集,记从点u到点v且与中每种长度的有向圈均有交的最短途径之长为d(u,v). 若g.c.d.()=1,以φ()∶=φ(c1,c2,…,cs)表示互质正整数c1,c2,…,cs的Frobenius数[1]. Frobenius数的2个重要结论如下:

引理2[1]若c1和c2是互质的正整数,则φ(c1,c2)=(c1-1)(c2-1).

引理3[1]设D是本原有向图,={c1,c2,…,cs} (s≥2)是D中若干不同圈长之集, 且g.c.d.()=1. 那么,对于满足t≥d(x,y)+φ()的非负整数t,必然存在一条从点x到点y的长为t的途径.

设Rt(X)表示从点子集X中的任意点出发经过长为t的途径所能到达的所有点的集合,简称可达集.

结合可达集与模糊可达集的定义,有如下结论.

引理5设SPSn,且∅≠X⊆V(S)，则

Ri(SRj(X))⊆SRi+j(X),

其中,i是非负整数,j是正整数.

证明对于任意的点zRi(SRj(X)),必有一点ySRj(X),使得存在从点y到点z长为i的途径,记为P. 进一步地,必有一点xX,使得存在从点x到点y长为j的SSSD途径对,记为W1和W2(或从点x到点y长为j且符号为“#”的途径,记为W*). 那么,W1+P和W2+P是从点xX到点z长为j+i的SSSD途径对 (或W*+P是从点xX到点z长为j+i且符号为“#”的途径),从而zSRi+j(X). 故Ri(SRj(X))⊆SRi+j(X).

引理6设SPSn,={c1,c2,…,cs} (s≥2)是S中若干不同圈长之集,且g.c.d.()=1. 若S中存在从点u到点v(u和v可以相同)长为ru,v的SSSD途径对W1和W2或符号为“#”的途径W*,则对于满足t*≥ru,v+d(v,y)+φ()的正整数t*,必然存在从点u到点y的长为t*的SSSD途径对或符号为“#”的途径.

证明因为t*≥ru,v+d(v,y)+φ(),所以t*-ru,v≥d(v,y)+φ(). 根据引理3,必然存在一条从点v到点y长为t*-ru,v的途径,记为P. 那么,W1+P和W2+P是S中从点u到点y长为t*的SSSD途径对,或W*+P是S中从点u到点y长为t*且符号为“#”的途径.

引理7设SPSn,={c1,c2,…,cs} (s≥2)是S中若干不同圈长之集,且g.c.d.()=1. 若S中存在从点u到点v(u和v可以相同)长为ru,v的SSSD途径对或符号为“#”的途径,则对于满足t≥ru,v+d(v,y)+φ()+(p-1)的正整数其中p是正整数.

证明对于非负整数i=0,1,…,p-1, 因为t-i≥ru,v+d(v,y)+φ(),根据引理6,必然存在从点u到点y的长为t-i的SSSD途径对或符号为“#”的途径,即SRt-i({u})⊇{y}. 结合引理5,对于非负整数i=0,1,…,p-1,SRt({u})⊇Ri(SRt-i({u}))⊇Ri({y}),进而

引理8设SPSn,={c1,c2,…,cs} (s≥2)是S中若干不同圈长之集,且g.c.d.()=1. 若S中存在点子集X满足:∀xX，均有从点x到自身长为rx≤r的SSSD途径对或符号为“#”的途径,且d(x,x)=0,则对于满足t≥r+φ()+(p-1)的正整数其中p是正整数.

证明∀xX,注意到d(x,x)=0. 对于非负整数i(i=0,1,…,p-1),因为t-i≥r+φ()≥rx+d(x,x)+φ(),由引理6可知:必然存在从点x到自身的长为t-i的SSSD途径对或符号为“#”的途径,即SRt-i({x})⊇{x},从而SRt-i(X)⊇X. 结合引理5,对于非负整数i(i=0,1,…,p-1),SRt(X)⊇Ri(SRt-i(X))⊇Ri(X),进而

下文将研究5类结构指数分别在含交圈结构/含违规交圈结构的本原不可幂广义带号有向图类 限制下的上界估值问题.

2.1 k点-基指数

定理1设S其中|Z|=m,且g是中的最小奇数,则

l(S,k)≤max{0,k-m}+-1+gc1+φ().

证明若k≤m,取非空k点子集X⊆Z;若k>m,因为S是本原的从而是强连通的,故可取非空k点子集X⊇Z,使得∀xX-Z均有长度为dx≤k-m的途径可达Z. 因此,对于上述2种情形均有:∀x

X,存在从点x出发通过长为dx≤max{0,k-m}的途径Px可达Z(不妨设所达的点为zxZ;特别地,zx和x可表示同一点). 另外,根据注3,记C中的最小奇有向圈为C′且其长度为g,并且C中含满足以下2种情形之一的有向圈C*(设其长度为c*):

情形1:C*与C′构成违规圈对. 因为zxZ,所以gC*与c*C′是从点zx到自身长为gc*的SSSD途径对,进而Px+gC*与Px+c*C′是从点x到点zx长为dx+gc*的SSSD途径对.

情形2:C*的符号为“#”(此时C*和C′可以是同一个有向圈). 同样由于zxZ,故C*是从点zx到自身长为c*且符号为“#”的途径,进而Px+C*是从点x到点zx长为dx+c*且符号为“#”的途径.

无论上述哪种情形,∀xX,总存在从点x到点zxZ长为rx,zx的SSSD途径对或符号为“#”的途径,其中

rx,zx≤max{dx+gc*,dx+c*}=dx+max{gc*,c*}≤

max{0,k-m}+gc1.

再次注意到:zx故d(zx,zx)=0. 令t=max{0,k-m}+gc1+φ()+(-1). 因为t≥rx,zx+d(zx,zx)+φ()+(-1),根据引理7,有结合引理4可得:,由命题1(i)可知定理得证.

推论1设SPSn,C1和C2是S中长度分别为c1和c2的有向圈,c1>c2≥1,g.c.d.(c1,c2)=1,且|V(C1)∩V(C2)|=m(m是正整数). 若C1和C2是违规圈对或它们二者之一的符号为“#”,则

l(S,k)≤max{0,k-m}++2c1c2-c1-c2.

证明易见S则由定理1和引理2即得所需结论.

2.2 k点-同位基指数

定理2设S且g是中的最小奇数，则

φ(S,k)≤k+-2+gc1+φ().

证明由于Z≠∅,不妨设zZ. 因为S是本原的从而是强连通的,故可取非空k点子集X⊇{z},使得∀xX,均有长度为dx≤k-1的途径Px可达点z(注意:z和x可以是同一点). 根据注3,可设C中的最小奇有向圈为C′且其长度为g,且C中含满足以下2种情形之一的有向圈C*(设其长度为c*):

情形1:C*与C′构成违规圈对. 因为z所以gC*与c*C′是从点z到自身长为gc*的SSSD途径对. 进而∀xX,Px+gC*与Px+c*C′是从点x到点z长为dx+gc*的SSSD途径对.

情形2:C*的符号为“#”(此时C*和C′可以是同一个有向圈). 同样因为z所以C*是从点z到自身长为c*且符号为“#”的途径,进而∀xX,Px+C*是从点x到点z长为dx+c*且符号为“#”的途径.

无论上述哪种情形,∀xX,总存在从点x到点z长为rx,z的SSSD途径对或符号为“#”的途径,其中

rx,z≤max{dx+gc*,dx+c*}=dx+max{gc*,c*}≤

(k-1)+gc1.

又再注意到z故d(z,z)=0. 另外,由引理4可知:,不妨设令

t=(k-1)+gc1+φ()+(-1).

∀xX,由于t≥rx,z+d(z,z)+φ()+(-1),由引理7可得:由命题1(ii)可知定理得证.

推论2设SPSn,C1和C2是S中长度分别为c1和c2的有向圈,c1>c2≥1,g.c.d.(c1,c2)=1,且V(C1)∩V(C2)≠∅. 若C1和C2是违规圈对或它们二者之一的符号为“#”,则

φ(S,k)≤k+-1+2c1c2-c1-c2.

证明易见S则由定理2和引理2即得所需结论.

定理3设SCIPSn,且g是中的最小奇数,则

l(S,k)≤φ(S,k)≤k+-2+ng+φ().

证明首先,由命题2(iv)可知:l(S,k)≤φ(S,k). 再者,根据注4,可设C中的最小奇有向圈为C′且其长度为g,S中含满足以下2个条件之一的有向圈C*(设其长度为c*):(1)C*与C′构成违规圈对;(2)C*的符号为“#”. 由于不妨设|Z|=m,其中m是正整数.

情形1:V(C*)∩Z=∅. 此时,c*+m≤n. 设从C*出发到Z的最短途径为P(不妨设从uV(C*)出发到vZ),记其长度为p,易见:p≤n+1-c*-m. 由于S是强连通的,故可取非空k点子集X⊇{u},使得∀xX，均有长度为dx≤k-1的途径Px可达点u(注意:u和x可以是同一点). 从而,Px+gC*+P与Px+P+c*C′是从点x到点v长为dx+p+gc*的SSSD途径对,或Px+C*+P是从点x到点v长为dx+c*+p且符号为“#”的途径,且

max{dx+p+gc*,dx+c*+p}≤(k-1)+(n+1-c*-m)+gc*≤

(k-1)+n-m+(g-1)(n-m)+1≤k-1+ng.

情形2:V(C*)∩Z≠∅. 取vV(C*)∩Z. 同样根据S的强连通性,可取非空k点子集X⊇{v},使得∀xX,均有长度为dx≤k-1的途径Px可达点v(v和x可以相同). 从而,Px+gC*与Px+c*C′是从点x到点v长为dx+gc*的SSSD途径对,或Px+C*是从点x到点v长为dx+c*且符号为“#”的途径,且

max{dx+gc*,dx+c*}≤(k-1)+gc*≤k-1+ng.

无论上述哪种情形,∀xX,总存在从点x到点vZ长为rx,v的SSSD途径对或符号为“#”的途径,其中

rx,v≤k-1+ng.

又因为v故d(v,v)=0. 由引理4可知:,不妨设令

t=(k-1+ng)+φ()+(-1).

∀xX,由于t≥rx,v+d(v,v)+φ()+(-1),由引理7可得:由命题1(ii)即证得所需结论.

2.3 第k重下-基指数

定理4设S其中|Z|=m,且g是中的最小奇数，则

ψ(S,k)≤max{0,-min{k,m}}+gc1+φ().

证明若k≤m,取非空k点子集X⊆Z;若k>m,取非空k点子集X⊇Z. 显然,X∩Z⊆Z且|X∩Z|=min{k,m}. 由于∀x故d(x,x)=0. 另外,根据注3,记C中的最小奇有向圈为C′且其长度为g,并且C中含满足以下2种情形之一的有向圈C*(设其长度为c*):

情形1:C*与C′构成违规圈对. 因为∀xX∩Z,所以gC*与c*C′是从点x到自身长为gc*的SSSD途径对.

情形2:C*的符号为“#”(此时C*和C′可以是同一个有向圈). 同样∀xX∩Z,故C*是从点x到自身长为c*且符号为“#”的途径.

无论上述哪种情形,∀xX∩Z,总存在从点x到自身长为rx的SSSD途径对或符号为“#”的途径,其中rx≤max{gc*,c*}≤gc1. 令

t=gc1+φ()+max{0,-min{k,m}}.

从而由命题1(iii)可知定理得证.

推论3设SPSn,C1和C2是S中长度分别为c1和c2的有向圈,c1>c2≥1,g.c.d.(c1,c2)=1,且|V(C1)∩V(C2)|=m(m是正整数). 若C1和C2是违规圈对或它们二者之一的符号为“#”,则

ψ(S,k)≤max{0,-min{k,m}}+1+2c1c2-c1-c2.

证明易见S则由定理4和引理2即得所需结论.

定理5设SCIPSn,且g是中的最小奇数,则

ψ(S,k)≤-1+ng+φ().

证明根据注4,可设C中的最小奇有向圈为C′且其长度为g,S中含满足以下2个条件之一的有向圈C*(设其长度为c*): (1)C*与C′构成违规圈对;(2)C*的符号为“#”. 因为Z≠∅,不妨设|Z|=m,其中m是正整数.

情形1:V(C*)∩Z=∅. 此时,c*+m≤n. 设从C*出发到Z的最短途径为P(不妨设从xV(C*)出发到vZ),记其长度为p,易见:p≤n+1-c*-m. 那么,gC*+P与P+c*C′是从点x到点v长为p+gc*的SSSD途径对,或者C*+P是从点x到点v长为c*+p且符号为“#”的途径,且

max{p+gc*,c*+p}≤(n+1-c*-m)+gc*≤

n-m+(g-1)(n-m)+1≤ng.

情形2:V(C*)∩Z≠∅. 令xV(C*)∩Z. 从而,gC*与c*C′是从点x到点x长为gc*的SSSD途径对,或C*是从点x到点x长为c*且符号为“#”的途径,且

max{gc*,c*}≤gc*≤ng.

无论哪种情形,必有从点x到某点vZ(v和x可以相同)长为rx,v的SSSD途径对或符号为“#”的途径,其中rx,v≤ng. 又因为v故d(v,v)=0. 令

t=ng+φ()+(-1).

取X⊇{x},由于t≥rx,v+d(v,v)+φ()+(-1),由引理7，有因此,结合引理4可得:,由此根据命题1(iii)即证得所需结论.

2.4 第k重上-基指数

定理6设S其中|Z|=m,且g是中的最小奇数，则

L(S,k)≤max{0,n-m-k+}+gc1+φ().

证明根据注3,记C中的最小奇有向圈为C′且其长度为g,C中含有向圈C*(设其长度为c*). 对于任意的非空k点子集X,分别考虑以下2种情形.

情形1:n-m-k<0. 易见,X∩Z≠∅且|X∩Z|≥k+m-n≥1. 由于∀x故d(x,x)=0.

子情形1.1:C*与C′构成违规圈对. 因为∀xX∩Z,所以gC*与c*C′是从点x到自身长为gc*的SSSD途径对.

子情形1.2:C*的符号为“#”(此时C*和C′可以是同一个有向圈). 同样∀xX∩Z,故C*是从点x到自身长为c*且符号为“#”的途径.

无论上述哪种子情形,∀xX∩Z,总存在从点x到自身长为rx的SSSD途径对或符号为“#”的途径,其中rx≤max{gc*,c*}≤gc1. 令

t=gc1+φ()+max{0,n-m-k+}.

情形2:n-m-k≥0. 记从X(不妨设为点xX)出发到Z(不妨设为点zZ)的最短途径为W,则W的长度d≤n+1-k-m.

子情形2.1:C*与C′构成违规圈对. 因为zZ,所以gC*与c*C′是从点z到自身长为gc*的SSSD途径对,进而W+gC*与W+c*C′是从点x到点z长为d+gc*的SSSD途径对.

子情形2.2:C*的符号为“#”(此时C*和C′可以是同一个有向圈). 同样由于zZ,故C*是从点z到自身长为c*且符号为“#”的途径,进而W+C*是从点x到点z长为d+c*且符号为“#”的途径.

无论上述哪种子情形,总存在从点x到点zZ长为rx,z的SSSD途径对或符号为“#”的途径,其中

rx,z≤max{d+gc*,d+c*}≤(n+1-k-m)+max{gc*,c*}≤

(n+1-k-m)+gc1.

又因为z故d(z,z)=0. 令

t=max{0,n-m+-k}+gc1+φ().

由于n-m+-k≥0,从而

t=(n-m-k+)+gc1+φ()=

(n+1-k-m)+gc1+φ()+(-1)≥

rx,z+d(z,z)+φ()+(-1),

综上2种情形,由命题1(iv)可得所需结论.

推论4设SPSn,C1和C2是S中长度分别为c1和c2的有向圈,c1>c2≥1,g.c.d.(c1,c2)=1,且|V(C1)∩V(C2)|=m(m是正整数). 若C1和C2是违规圈对或它们二者之一的符号为“#”,则

L(S,k)≤max{0,n-m-k+}+1+2c1c2-c1-c2.

证明易见S则由定理6和引理2即得所需结论.

定理7设SCIPSn,且g是中的最小奇数，则

L(S,k)≤n+-k-1+ng+φ().

证明根据注4,可设C中的最小奇有向圈为C′且其长度为g,S中含满足以下2个条件之一的有向圈C*(设其长度为c*):(1)C*与C′构成违规圈对;(2)C*的符号为“#”. 由于Z≠∅,不妨设|Z|=m,其中m是正整数.

情形1:V(C*)∩Z=∅. 此时,c*+m≤n. 设从C*出发到Z的最短途径为P(不妨设从uV(C*)出发到vZ),记其长度为p,易见:p≤n+1-c*-m. 对于任意的非空k点子集X,记从X(不妨设为点xX)出发到点u的最短途径为W,其长度w≤n-k. 那么,W+gC*+P与W+P+c*C′是从点x到点v长为w+p+gc*的SSSD途径对,或者W+C*+P是从点x到点v长为w+c*+p且符号为“#”的途径,且

max{w+p+gc*,w+c*+p}≤(n-k)+(n+1-c*-m)+gc*≤

(n-k)+n-m+(g-1)(n-m)+1≤(n-k)+ng.

情形2:V(C*)∩Z≠∅. 令vV(C*)∩Z. 对于任意的非空k点子集X,记从X(不妨设为点xX) 出发到点v的最短途径为W,其长度w≤n-k. 从而,W+gC*与W+c*C′是从点x到点v长为w+gc*的SSSD途径对,或W+C*是从点x到点v长为w+c*且符号为“#”的途径,且

max{w+gc*,w+c*}≤(n-k)+gc*≤(n-k)+ng.

无论上述哪种情形,对于任意的非空k点子集X,必有从点xX到某点vZ长为rx,v的SSSD途径对或符号为“#”的途径,其中rx,v≤(n-k)+ng. 又因为v故d(v,v)=0. 令

t=(n-k)+ng+φ()+(-1).

由于t≥rx,v+d(v,v)+φ()+(-1),由引理7可得:因此,结合引理4可得:

由此,根据命题1(iv)即证得所需结论.

2.5 ω-不可分基指数

定理8设S其中|Z|=m,且g是中的最小奇数,则

εω(S)≤n-m+ω+gc1+φ().

证明根据注3,记C中的最小奇有向圈为C′且其长度为g,并且C中含有向圈C*(设其长度为c*). 对于任一满足 1≤|X|=k≤min{n,n-ω}的k点子集X,分别讨论以下2种情形.

情形1:n-m-k<0. 易见,X∩Z≠∅且|X∩Z|≥k+m-n≥1. 由于∀x故d(x,x)=0.

子情形1.1:C*与C′构成违规圈对. ∀xX∩Z,gC*与c*C′是从点x到自身长为gc*的SSSD途径对.

子情形1.2:C*的符号为“#”(此时C*和C′可以是同一个有向圈). 同样∀xX∩Z,总存在从点x到自身长为c*且符号为“#”的途径C*.

无论上述哪种子情形,∀xX∩Z,总存在从点x到自身长为rx的SSSD途径对或符号为“#”的途径,其中rx≤max{gc*,c*}≤gc1. 令

t=gc1+φ()+(n-m+ω).

情形2:n-m-k≥0. 记从X(不妨设为点xX) 出发到Z(不妨设为点zZ)的最短途径为W,则W的长度d≤n+1-k-m.

子情形2.1:C*与C′构成违规圈对. 因为zZ,所以gC*与c*C′是从点z到自身长为gc*的SSSD途径对,进而W+gC*与W+c*C′是从点x到点z长为d+gc*的SSSD途径对.

子情形2.2:C*的符号为“#”(此时C*和C′可以是同一个有向圈). 同样由于zZ,故C*是从点z到自身长为c*且符号为“#”的途径,进而W+C*是从点x到点z长为d+c*且符号为“#”的途径.

无论上述哪种情形,总存在从点x到点zZ长为rx,z的SSSD途径对或符号为“#”的途径,其中

rx,z≤max{d+gc*,d+c*}≤(n+1-k-m)+max{gc*,c*}≤

(n+1-k-m)+gc1.

又因为z故d(z,z)=0. 令

t=(n+1-m-k)+gc1+φ()+(k+ω-1).

因为t≥rx,z+d(z,z)+φ()+(k+ω-1),由引理7,有结合引理4可得:

综上2种情形,根据命题1(v)可得所需结论.

推论5设SPSn,C1和C2是S中长度分别为c1和c2的有向圈,c1>c2≥1,g.c.d.(c1,c2)=1,且|V(C1)∩V(C2)|=m(m是正整数). 若C1和C2是违规圈对或它们二者之一的符号为“#”,则

εω(S)≤n-m+ω+1+2c1c2-c1-c2.

证明易见S则由定理8和引理2即得所需结论.

定理9设SCIPSn,且g是中的最小奇数,则

εω(S)≤n+ω-1+ng+φ().

证明根据注4,可设C中的最小奇有向圈为C′且其长度为g,S中含满足以下2个条件之一的有向圈C*(设其长度为c*):(1)C*与C′构成违规圈对;(2)C*的符号为“#”. 由于Z≠∅,不妨设|Z|=m,其中m是正整数.

情形1:V(C*)∩Z=∅. 此时,c*+m≤n. 设从C*出发到Z的最短途径为P(不妨设从uV(C*)出发到vZ),记其长度为p,易见:p≤n+1-c*-m. 对于任意的非空k点子集X,记从X(不妨设为点xX)出发到点u的最短途径为W,其长度w≤n-k. 那么,W+gC*+P与W+P+c*C′是从点x到点v长为w+p+gc*的SSSD途径对,或者W+C*+P是从点x到点v长为w+c*+p且符号为“#”的途径,且

max{w+p+gc*,w+c*+p}≤(n-k)+(n+1-c*-m)+gc*≤

(n-k)+n-m+(g-1)(n-m)+1≤(n-k)+ng.

情形2:V(C*)∩Z≠∅. 令vV(C*)∩Z. 对于任意的非空k点子集X,记从X(不妨设为点xX) 出发到点v的最短途径为W,其长度w≤n-k. 从而,W+gC*与W+c*C′是从点x到点v长为w+gc*的SSSD途径对,或W+C*是从点x到点v长为w+c*且符号为“#”的途径,且

max{w+gc*,w+c*}≤(n-k)+gc*≤(n-k)+ng.

无论上述哪种情形,对于任意的非空k点子集X,必有从点xX到某点vZ长为rx,v的SSSD途径对或符号为“#”的途径,其中rx,v≤(n-k)+ng. 又因为v故d(v,v)=0. 令

t=(n-k)+ng+φ()+(k+ω-1).

由于t≥rx,v+d(v,v)+φ()+(k+ω-1),由引理7可得:因此,结合引理4可得:

由此根据命题1(v)即证得所需结论.

l(n,1,k)=n+k+-2,

φ(n,1,k)=n+k+-2,

ψ(n,1,k)=n+-1,

L(n,1,k)=2n+-k-1,

若SLPSn,即S含有环(记为L),由S的强连通性可知:环点必落于另一有向圈C中,令C={C,L},则由定理3、定理5、 定理7和定理9可得如下推论,即含有环的n阶本原不可幂广义带号有向图类LPSn的5类结构指数(k点-基指数、k点-同位基指数、 第k重下-基指数、 第k重上-基指数及ω-不可分基指数)的确界刻画.

推论6设SLPSn,则

l(S,k)≤n+k+-2,

(1)

φ(S,k)≤n+k+-2,

(2)

ψ(S,k)≤n+-1,

(3)

L(S,k)≤2n+-k-1,

(4)

εω(S)≤2n+ω-1,

(5)