本原不可幂广义符号矩阵的若干结构指数的界

黄宇飞

黄宇飞. 本原不可幂广义符号矩阵的若干结构指数的界[J]. 华南师范大学学报(自然科学版), 2020, 52(1): 91-99. DOI: 10.6054/j.jscnun.2020014
引用本文: 黄宇飞. 本原不可幂广义符号矩阵的若干结构指数的界[J]. 华南师范大学学报(自然科学版), 2020, 52(1): 91-99. DOI: 10.6054/j.jscnun.2020014
HUANG Yufei. Bounds on the Structural Indices of Primitive Non-powerful Generalized Sign Pattern Matrices[J]. Journal of South China Normal University (Natural Science Edition), 2020, 52(1): 91-99. DOI: 10.6054/j.jscnun.2020014
Citation: HUANG Yufei. Bounds on the Structural Indices of Primitive Non-powerful Generalized Sign Pattern Matrices[J]. Journal of South China Normal University (Natural Science Edition), 2020, 52(1): 91-99. DOI: 10.6054/j.jscnun.2020014

本原不可幂广义符号矩阵的若干结构指数的界

基金项目: 

国家自然科学基金项目 11501139

广航院国家自然科学基金校级重点培育项目 18X0429

详细信息
    通讯作者:

    黄宇飞, 副教授, Email:fayger@qq.com

  • 中图分类号: O151.21

Bounds on the Structural Indices of Primitive Non-powerful Generalized Sign Pattern Matrices

  • 摘要: 鉴于“环”在结构指数问题研究中的特殊功效, 定义了2类特殊的广义带号有向图:含交圈结构/含违规交圈结构的本原不可幂广义带号有向图.利用有向图的模拟、模糊可达集的分析以及Frobenius数的若干性质, 研究了kτ-基指数、kτ-同位基指数、第k重下τ-基指数、第k重上τ-基指数及ω-不可分基指数等结构指数分别在含交圈结构/含违规交圈结构的本原不可幂广义带号有向图类限制下的上界估值问题.
    Abstract: In view of the special effects of "loop" in the study of structural index problems, two classes of special generalized signed digraphs are defined: primitive non-powerful generalized signed digraphs with intersecting cycles structure and that with distinguished intersecting cycles structure, respectively. With restriction on primitive non-powerful generalized signed digraphs with intersecting cycles structure and those with distinguished intersecting cycles structure, upper bounds on the structural indices, e.g. kth local τ-base, kth same τ-base, kth lower τ-base, kth upper τ-base and ω-indecomposable base, are discussed by imitating the digraphs, analyzing the ambiguous reachable set and using the properties of Frobenius numbers, respectively.
  • 组合矩阵论[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, 其中bp都是正整数.称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={v1v2,…,vn}, 且1≤i, jn.称AS邻接(广义)符号矩阵, SA的伴随(广义)带号有向图.为方便起见, 称一个(广义)带号有向图是本原的/不可幂的, 如果其邻接(广义)符号矩阵是本原的/不可幂的; 并且后文将直接采用“本原不可幂(广义)带号有向图的某结构指数”的表述形式.

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

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

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

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

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

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

    (ⅴ)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类指数均是有意义的(必为有限值).

    (广义)带号有向图S=(V, E)中一条有向途径W=v0x1v1xkvk的符号sgn(W)可定义为该途径中所有弧的符号之积, 即sgn(W)=ki=1sgn(xi), 其中, v0V, viV, xiExi=vi-1vi (i=1, 2, …, k).同理, 可定义(广义)带号有向图中路、圈、环等的符号.对于(广义)带号有向图中的2条途径W1W2, 如果它们有相同的起点、相同的终点、相同的长度, 但符号相异(即“1”与“-1”), 称W1W2为三同一异途径对(简称SSSD途径对)[4].本文中有关图论的定义和记号还可参见文献[14].

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

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

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

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

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

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

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

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

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

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

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

    (ⅳ)ψτ(S, nk+1)≤Lτ(S, nk+1)≤lτ(S, k)≤φτ(S, k).

    n阶本原不可幂广义带号有向图的集合为PSn, 又记恰含d个环的n阶本原不可幂广义带号有向图的集合为PSn(d), 其中d∈{1, 2, …, n}.考虑到上述提到的若干结构指数几乎都解决了其在图类PSn(d)限制下的上界估值问题, 究其原因主要在于环点的特殊功效.又注意到:一个n阶广义带号有向图S是本原的当且仅当它的底图Dn阶强连通有向图, 且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.记C={c1, c2, …, cs}, 若g.c.d.(C):=g.c.d.(c1, c2, …, cs)=1 (这里, g.c.d.是最大公因数的缩写, 后文均默认采用此记号), 且Z=sq=1V(Cq), 则称S为含交圈结构的本原不可幂广义带号有向图.

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

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

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

    (B2)p1p2都是奇数, 且sgn(C1)=-sgn(C2).

    我们称这样一对满足条件(B1)或(B2)的有向圈C1C2为“违规圈对”.由此还可推出:途径对W1=p2C1W2=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.记C={c1, c2, …, cs}, 若g.c.d.(C)=1, Z=sq=1V(Cq), 且C中含有违规圈对或符号为“#”的有向圈, 则称S为含违规交圈结构的本原不可幂广义带号有向图.

    注2  记含交圈结构的n阶本原不可幂广义带号有向图的集合为CIPSn,记含违规交圈结构的n阶本原不可幂广义带号有向图的集合为CIPSn*.易见, CIPSn*⊆CIPSn⊆PSn.另外, 记含有环的n阶本原不可幂广义带号有向图类为LPSn.

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

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

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

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

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

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

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

    引理4[15]  设D是本原有向图, 且X是非空点子集, 即XV(D), 则对于任意非负整数t, 有|ti=0Ri(X)|min{n,|X|+t}.

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

    引理5  设S∈PSn, 且Ø≠XV(S),则

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

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

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

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

    证明  因为t*ru, v+dC(v, y)+ϕ(C), 所以t*ru, vdC(v, y)+ϕ(C).根据引理3, 必然存在一条从点v到点y长为t*ru, v的途径, 记为P.那么, W1+PW2+PS中从点u到点y长为t*的SSSD途径对, 或W*+PS中从点u到点y长为t*且符号为“#”的途径.

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

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

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

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

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

    定理1  设S∈CIPSn*, 其中|Z|=m, 且gC中的最小奇数, 则

    lτ(S,k)max{0,km}+τ1+gc1+ϕ(C).

    证明  若km, 取非空k点子集XZ; 若k>m, 因为S是本原的从而是强连通的, 故可取非空k点子集XZ, 使得∀xXZ均有长度为dxkm的途径可达Z.因此, 对于上述2种情形均有:∀xX, 存在从点x出发通过长为dx≤max{0, km}的途径Px可达Z(不妨设所达的点为zxZ; 特别地, zxx可表示同一点).另外, 根据注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,zxmax{dx+gc,dx+c}=dx+max{gc,c}max{0,km}+gc1.

    再次注意到:zxZ=sq=1V(Cq), 故dC(zx, zx)=0.令t=max{0, km}+gc1+ϕ(C)+(τ-1).因为trx, zx+dC(zx, zx)+ϕ(C)+(τ-1), 根据引理7, 有SRt({x})⊇τ1i=0Ri({zx}).结合引理4可得:|SRt({x})|≥|τ1i=0Ri({zx})|≥τ, 由命题1(ⅰ)可知定理得证.

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

    lτ(S,k)max{0,km}+τ+2c1c2c1c2.

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

    定理2  设S∈CIPSn*, 且gC中的最小奇数,则

    φτ(S,k)k+τ2+gc1+ϕ(C).

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

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

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

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

    rx,zmax{dx+gc,dx+c}=dx+max{gc,c}(k1)+gc1.

    又再注意到zsq=1V(Cq), 故dC(z, z)=0.另外, 由引理4可知:|τ1i=0Ri({z})|≥τ, 不妨设τ1i=0Ri({z})⊇{v1, v2, …, vτ}.令

    t=(k1)+gc1+ϕ(C)+(τ1).

    xX, 由于trx, z+dC(z, z)+ϕ(C)+(τ-1), 由引理7可得:SRt({x})⊇τ1i=0Ri({z})⊇{v1, v2, …, vτ}, 由命题1(ⅱ)可知定理得证.

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

    φτ(S,k)k+τ1+2c1c2c1c2.

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

    定理3  设S∈CIPSn, 且gC中的最小奇数, 则

    lτ(S,k)φτ(S,k)k+τ2+ng+ϕ(C).

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

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

    max{dx+p+gc,dx+c+p}(k1)+(n+1cm)+gc(k1)+nm+(g1)(nm)+1k1+ng.

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

    max{dx+gc,dx+c}(k1)+gck1+ng.

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

    rx,vk1+ng.

    又因为vZ=sq=1V(Cq), 故dC(v, v)=0.由引理4可知:|τ1i=0Ri({v})|≥τ, 不妨设τ1i=0Ri({v})⊇{v1, v2, …, vτ}.令

    t=(k1+ng)+ϕ(C)+(τ1).

    xX, 由于trx, v+dC(v, v)+ϕ(C)+(τ-1), 由引理7可得:SRt({x})⊇τ1i=0Ri({v})⊇{v1, v2, …, vτ}, 由命题1(ⅱ)即证得所需结论.

    定理4  设S∈CIPSn*, 其中|Z|=m, 且gC中的最小奇数,则

    ψτ(S,k)max{0,τmin{k,m}}+gc1+ϕ(C).

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

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

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

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

    t=gc1+ϕ(C)+max{0,τmin{k,m}}.

    由引理8, 有SRt(XZ)⊇max{0,τmin{k,m}}i=0Ri(XZ).结合引理4可得:

    |SRt(X)||SRt(XZ)||max{0,τmin{k,m}}i=0Ri(XZ)|τ,

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

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

    ψτ(S,k)max{0,τmin{k,m}}+1+2c1c2c1c2.

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

    定理5  设S∈CIPSn, 且gC中的最小奇数, 则

    ψτ(S,k)τ1+ng+ϕ(C).

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

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

    max{p+gc,c+p}(n+1cm)+gcnm+(g1)(nm)+1ng.

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

    max{gc,c}gcng.

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

    t=ng+ϕ(C)+(τ1).

    X⊇{x}, 由于trx, v+dC(v, v)+ϕ(C)+(τ-1), 由引理7,有SRt(X)⊇SRt({x})⊇τ1i=0Ri({v}), 因此, 结合引理4可得:|SRt(X)|≥|τ1i=0Ri({v})|≥τ, 由此根据命题1(ⅲ)即证得所需结论.

    定理6  设S∈CIPSn*, 其中|Z|=m, 且gC中的最小奇数,则

    Lτ(S,k)max{0,nmk+τ}+gc1+ϕ(C).

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

    情形1:nmk < 0.易见, XZ≠Ø且|XZ|≥k+mn≥1.由于∀xXZZ=sq=1V(Cq), 故dC(x, x)=0.

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

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

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

    t=gc1+ϕ(C)+max{0,nmk+τ}.

    由引理8, 有SRt(X)⊇SRt(XZ)⊇max{0,nmk+τ}i=0Ri(XZ).再结合引理4可得:

    |SRt(X)||SRt(XZ)||max{0,nmk+τ}i=0Ri(XZ)|τ.

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

    子情形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,zmax{d+gc,d+c}(n+1km)+max{gc,c}(n+1km)+gc1.

    又因为zZ=sq=1V(Cq), 故dC(z, z)=0.令

    t=max{0,nm+τk}+gc1+ϕ(C).

    由于nm+τk≥0, 从而

    t=(nmk+τ)+gc1+ϕ(C)=(n+1km)+gc1+ϕ(C)+(τ1)rx,z+dC(z,z)+ϕ(C)+(τ1),

    由引理7, 有SRt(X)⊇SRt({x})⊇τ1i=0Ri({z}).结合引理4可得:

    |SRt(X)||SRt({x})||τ1i=0Ri({z})|τ.

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

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

    Lτ(S,k)max{0,nmk+τ}+1+2c1c2c1c2.

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

    定理7  设S∈CIPSn, 且gC中的最小奇数,则

    Lτ(S,k)n+τk1+ng+ϕ(C).

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

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

    max{w+p+gc,w+c+p}(nk)+(n+1cm)+gc(nk)+nm+(g1)(nm)+1(nk)+ng.

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

    max{w+gc,w+c}(nk)+gc(nk)+ng.

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

    t=(nk)+ng+ϕ(C)+(τ1).

    由于trx, v+dC(v, v)+ϕ(C)+(τ-1), 由引理7可得:SRt(X)⊇SRt({x})⊇τ1i=0Ri({v}).因此, 结合引理4可得:

    |SRt(X)||SRt({x})||τ1i=0Ri({v})|τ,

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

    定理8  设S∈CIPSn*, 其中|Z|=m, 且gC中的最小奇数, 则

    εω(S)nm+ω+gc1+ϕ(C).

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

    情形1:nmk < 0.易见, XZ≠Ø且|XZ|≥k+mn≥1.由于∀xXZZ=sq=1V(Cq), 故dC(x, x)=0.

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

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

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

    t=gc1+ϕ(C)+(nm+ω).

    由引理8, 有SRt(X)⊇SRt(XZ)⊇nm+ωi=0Ri(XZ).再由引理4可得:

    |SRt(X)||SRt(XZ)||nm+ωi=0Ri(XZ)|k+ω.

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

    子情形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,zmax{d+gc,d+c}(n+1km)+max{gc,c}(n+1km)+gc1.

    又因为zZ=sq=1V(Cq), 故dC(z, z)=0.令

    t=(n+1mk)+gc1+ϕ(C)+(k+ω1).

    因为trx, z+dC(z, z)+ϕ(C)+(k+ω-1), 由引理7, 有SRt(X)⊇SRt({x})⊇k+ω1i=0Ri({z}).结合引理4可得:

    |SRt(X)||SRt({x})||k+ω1i=0Ri({z})|k+ω.

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

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

    εω(S)nm+ω+1+2c1c2c1c2.

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

    定理9  设S∈CIPSn, 且gC中的最小奇数, 则

    εω(S)n+ω1+ng+ϕ(C).

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

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

    max{w+p+gc,w+c+p}(nk)+(n+1cm)+gc(nk)+nm+(g1)(nm)+1(nk)+ng.

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

    max{w+gc,w+c}(nk)+gc(nk)+ng.

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

    t=(nk)+ng+ϕ(C)+(k+ω1).

    由于trx, v+dC(v, v)+ϕ(C)+(k+ω-1), 由引理7可得:SRt(X)⊇SRt({x})⊇k+ω1i=0Ri({v}), 因此, 结合引理4可得:

    |SRt(X)||SRt({x})||k+ω1i=0Ri({v})|k+ω,

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

    上文给出了本原不可幂广义带号有向图类CIPSn*和CIPSn的5类结构指数的界.从有关定理或推论的刻画上看来, 并未描述这些界是否可达.但实际上, 这仅仅是因为本原不可幂广义带号有向图类CIPSn*和CIPSn在定义上具有一定的广泛性(换句话说, 大多数本原不可幂广义带号有向图S∈PSn总能找到交圈结构).因此, 只要对CIPSn*和CIPSn在交圈结构上给出更明确的要求, 根据本文的有关结论并结合相应极图的刻画, 通常可以得到5类结构指数的确界.作为举例, 下面将给出含有环的n阶本原不可幂广义带号有向图类LPSn的5类结构指数的确界.

    Ln, 1表示点集为V={v1, v2, …, vn}, 弧集为E={(vi, vi+1)|1≤in-1}∪{(vn, vn), (vn, v1)}的有向图.又设˜Sn, 1是以Ln, 1为底图的本原不可幂带号有向图.显然, ˜Sn, 1∈LPSn.由于˜Sn, 1仅有1个长为n的有向圈和1个长为1的环, 根据引理1, 它们必然构成违规圈对.从而由命题1可得:

    lτ(˜Sn,1,k)=n+k+τ2,φτ(˜Sn,1,k)=n+k+τ2,ψτ(˜Sn,1,k)=n+τ1,Lτ(˜Sn,1,k)=2n+τk1,εω(˜Sn,1)=2n+ω1.

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

    推论6  设S∈LPSn, 则

    lτ(S,k)n+k+τ2,
    (1)
    φτ(S,k)n+k+τ2,
    (2)
    ψτ(S,k)n+τ1,
    (3)
    Lτ(S,k)2n+τk1,
    (4)
    εω(S)2n+ω1,
    (5)

    这些上界均可达且˜Sn, 1是极图之一, 其中,式(2)、(3)是文献[5]的结论.

  • [1] 柳柏濂.组合矩阵论[M].北京:科学出版社, 2005.
    [2]

    LI Z S, HALL F, ESCHENBACH C. On the period and base of a sign pattern matrix[J]. Linear Algebra and its Applications, 1994, 212/213:101-120. doi: 10.1016/0024-3795(94)90398-0

    [3]

    LIU B L, YOU L H. Bounds on the base of primitive nearly reducible sign pattern matrices[J]. Linear Algebra and its Applications, 2006, 418:863-881. doi: 10.1016/j.laa.2006.03.024

    [4]

    YOU L H, SHAO J Y, SHAN H Y. Bounds on the bases of irreducible generalized sign pattern matrices[J]. Linear Algebra and its Applications, 2007, 427:285-300. doi: 10.1016/j.laa.2007.07.019

    [5]

    HUANG Y F, LIU B L, CHEN S Y. The generalized τ-bases of primitive non-powerful signed digraphs with d loops[J]. Graphs and Combinatorics, 2012, 28:227-242. doi: 10.1007/s00373-011-1036-z

    [6] 黄宇飞, 柳柏濂.本原不可幂符号矩阵的完全不可分基指数[J].华南师范大学学报(自然科学版), 2016, 48(4):88-94. doi: 10.6054/j.jscnun.2016.05.038

    HUANG Y F, LIU B L. Fully indecomposable bases of primitive non-powerful sign pattern matrices[J]. Journal of South China Normal University(Natural Science Edition), 2016, 48(4):88-94. doi: 10.6054/j.jscnun.2016.05.038

    [7] 柳柏濂, 黄宇飞.组合矩阵的结构指数[M].北京:科学出版社, 2015.
    [8] 黄宇飞, 柳柏濂.组合矩阵的结构指数——组合矩阵指数的系统化[J].数学进展, 2016, 45(2):161-175. http://d.old.wanfangdata.com.cn/Conference/8986853

    HUANG Y F, LIU B L. Structural indices of combinatorial matrix——the systematization of combinatorial matrix indices[J]. Advances in Mathematics, 2016, 45(2):161-175. http://d.old.wanfangdata.com.cn/Conference/8986853

    [9]

    LI Q, LIU B L. Bounds on the kth multi-g base index of nearly reducible sign pattern matrices[J]. Discrete Mathe-matics, 2008, 308:4846-4860. doi: 10.1016/j.disc.2007.09.004

    [10]

    WANG L Q, MIAO Z K, YAN C. Local bases of primitive non-powerful signed digraphs[J]. Discrete Mathematics, 2009, 309:748-754. doi: 10.1016/j.disc.2008.01.012

    [11]

    GAO Y B, SHAO Y L, SHEN J. Bounds on the local bases of primitive nonpowerful nearly reducible sign patterns[J]. Linear and Multilinear Algebra, 2009, 57(2):205-215. doi: 10.1080/03081080701763433

    [12]

    LIANG C H, LIU B L, HUANG Y F. The kth lower bases of primitive non-powerful signed digraphs[J]. Linear Algebra and its Applications, 2010, 432:1680-1690. doi: 10.1016/j.laa.2009.11.023

    [13]

    SHAO Y L, SHEN J, GAO Y B. The kth upper bases of primitive non-powerful signed digraphs[J]. Discrete Mathematics, 2009, 309:2682-2686. doi: 10.1016/j.disc.2008.06.039

    [14]

    BONDY J A, MURTY U S R. Graph theory with applications[M]. London:The Macmillan Press Ltd, 1976.

    [15]

    LIU B L. On fully indecomposable exponent for primitive Boolean matrices with symmetric ones[J]. Linear and Multilinear Algebra, 1992, 31(1/2/3/4):131-138. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=10.1080/03081089208818129

  • 期刊类型引用(1)

    1. 王正家,曾雨晴,徐欣犀,徐佑犀,王超. 基于多传感器的机器人夹取系统研究. 机床与液压. 2023(11): 27-33 . 百度学术

    其他类型引用(0)

计量
  • 文章访问数:  1931
  • HTML全文浏览量:  834
  • PDF下载量:  37
  • 被引次数: 1
出版历程
  • 收稿日期:  2019-01-24
  • 网络出版日期:  2021-03-21
  • 刊出日期:  2020-02-24

目录

/

返回文章
返回