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

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

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

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

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

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

1.   概念与定义

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

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

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

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

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

(ⅴ)A的ω-不可分基指数^[6], 记为ε_ω(A), 是最小的正整数t, 使得A^t中任一满足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=v₀x₁v₁…x_kv_k的符号sgn(W)可定义为该途径中所有弧的符号之积, 即${\mathop{\rm sgn}} (W) = \prod\nolimits_{i = 1}^k {{\mathop{\rm sgn}} } \left( {{x_i}} \right)$, 其中, v₀∈V, v_i∈V, x_i∈E且x_i=v_i－1v_i (i=1, 2, …, k).同理, 可定义(广义)带号有向图中路、圈、环等的符号.对于(广义)带号有向图中的2条途径W₁和W₂, 如果它们有相同的起点、相同的终点、相同的长度, 但符号相异(即“1”与“－1”), 称W₁和W₂为三同一异途径对(简称SSSD途径对)^[4].本文中有关图论的定义和记号还可参见文献[14].

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

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

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

(ⅱ)S的k点τ-同位基指数φ_τ(S, k)是最小的正整数t, 使得存在k点子集X⊆V(S)及{v₁, v₂, …, v_τ}⊆V(S), 满足∀x∈X均有SR_t({x})⊇{v₁, v₂, …, v_τ}.

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

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

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

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

(ⅰ)l_τ(S, 1)=φ_τ(S, 1)=ψ_τ(S, 1), l_τ(S, n)=L_τ(S, 1), ψ_τ(S, n)=L_τ(S, n).

(ⅱ)l_n(S, k)=φ_n(S, k).

(ⅲ)l_n(S, n)=φ_n(S, n)=L_n(S, 1)=ε_n－1(A)=b(S).

(ⅳ)ψ_τ(S, n－k+1)≤L_τ(S, n－k+1)≤l_τ(S, k)≤φ_τ(S, k).

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

定义1  设S是本原不可幂广义带号有向图, 且$\mathscr{C}$={C₁, C₂, …, C_s} (s≥2)是S中若干不同长度的有向圈构成的一个集合.记有向圈C_q的长度为c_q(q=1, 2, …, s), 不妨设c₁>c₂>…>c_s≥1.记${\cal C}$={c₁, c₂, …, c_s}, 若g.c.d.(${\cal C}$):=g.c.d.(c₁, c₂, …, c_s)=1 (这里, g.c.d.是最大公因数的缩写, 后文均默认采用此记号), 且$Z = \bigcap\nolimits_{q = 1}^s V \left( {{C_q}} \right) \ne \emptyset$, 则称S为含交圈结构的本原不可幂广义带号有向图.

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

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

(B₁)p₁是偶数, p₂是奇数, 且sgn(C₁)=－1;

(B₂)p₁和p₂都是奇数, 且sgn(C₁)=－sgn(C₂).

我们称这样一对满足条件(B₁)或(B₂)的有向圈C₁和C₂为“违规圈对”.由此还可推出:途径对W₁=p₂C₁和W₂=p₁C₂的长度均为p₁p₂, 但符号相异, 即(sgn(C₁))^p₂=－[(sgn(C₂))^p₁].

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

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

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

定义2  设S是本原不可幂广义带号有向图, 且$\mathscr{C}$={C₁, C₂, …, C_s} (s≥2)是S中若干不同长度的有向圈构成的一个集合, 记有向圈C_q的长度为c_q (q=1, 2, …, s), 不妨设c₁>c₂>…>c_s≥1.记${\cal C}$={c₁, c₂, …, c_s}, 若g.c.d.(${\cal C}$)=1, $Z = \bigcap\nolimits_{q = 1}^s V \left( {{C_q}} \right) \ne \emptyset$, 且$\mathscr{C}$中含有违规圈对或符号为“#”的有向圈, 则称S为含违规交圈结构的本原不可幂广义带号有向图.

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

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

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

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

2.   主要结果及其证明

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

引理2^[1]  若c₁和c₂是互质的正整数, 则ϕ(c₁, c₂)=(c₁－1)(c₂－1).

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

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

引理4^[15]  设D是本原有向图, 且X是非空点子集, 即$\emptyset \ne X \subseteq V(D)$, 则对于任意非负整数t, 有$\left| {\bigcup\nolimits_{i = 0}^t {{R_i}} (X)} \right| \ge \min \{ n, |X| + t\}$.

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

引理5  设S∈PS_n, 且Ø≠X⊆V(S)，则

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

证明  对于任意的点z∈R_i(SR_j(X)), 必有一点y∈SR_j(X), 使得存在从点y到点z长为i的途径, 记为P.进一步地, 必有一点x∈X, 使得存在从点x到点y长为j的SSSD途径对, 记为W₁和W₂ (或从点x到点y长为j且符号为“#”的途径, 记为W^*).那么, W₁+P和W₂+P是从点x∈X到点z长为j+i的SSSD途径对(或W^*+P是从点x∈X到点z长为j+i且符号为“#”的途径), 从而z∈SR_i+j(X).故R_i(SR_j(X))⊆SR_i+j(X).

引理6  设S∈PS_n, ${\cal C}$={c₁, c₂, …, c_s} (s≥2)是S中若干不同圈长之集, 且g.c.d.(${\cal C}$)=1.若S中存在从点u到点v (u和v可以相同)长为r_{u, v}的SSSD途径对W₁和W₂或符号为“#”的途径W^*, 则对于满足t^*≥r_{u, v}+d_{${\cal C}$}(v, y)+ϕ(${\cal C}$)的正整数t^*, 必然存在从点u到点y的长为t^*的SSSD途径对或符号为“#”的途径.

证明  因为t^*≥r_{u, v}+d_{${\cal C}$}(v, y)+ϕ(${\cal C}$), 所以t^*－r_{u, v}≥d_{${\cal C}$}(v, y)+ϕ(${\cal C}$).根据引理3, 必然存在一条从点v到点y长为t^*－r_{u, v}的途径, 记为P.那么, W₁+P和W₂+P是S中从点u到点y长为t^*的SSSD途径对, 或W^*+P是S中从点u到点y长为t^*且符号为“#”的途径.

引理7  设S∈PS_n, ${\cal C}$={c₁, c₂, …, c_s} (s≥2)是S中若干不同圈长之集, 且g.c.d.(${\cal C}$)=1.若S中存在从点u到点v (u和v可以相同)长为r_{u, v}的SSSD途径对或符号为“#”的途径, 则对于满足t≥r_{u, v}+d_{${\cal C}$}(v, y)+ϕ(${\cal C}$)+(p－1)的正整数t, SR_t({u})⊇$\bigcup\nolimits_{i = 0}^{p - 1} {}$R_i({y}), 其中p是正整数.

证明  对于非负整数i=0, 1, …, p－1, 因为t－i≥r_{u, v}+d_{${\cal C}$}(v, y)+ϕ(${\cal C}$), 根据引理6, 必然存在从点u到点y的长为t－i的SSSD途径对或符号为“#”的途径, 即SR_t－i({u})⊇{y}.结合引理5, 对于非负整数i=0, 1, …, p－1, SR_t({u})⊇R_i(SR_t－i({u}))⊇R_i({y}), 进而SR_t({u})⊇$\bigcup\nolimits_{i = 0}^{p - 1} {}$R_i({y}).

引理8  设S∈PS_n, ${\cal C}$={c₁, c₂, …, c_s} (s≥2)是S中若干不同圈长之集, 且g.c.d.(${\cal C}$)=1.若S中存在点子集X满足:∀x∈X，均有从点x到自身长为r_x≤r的SSSD途径对或符号为“#”的途径, 且d_{${\cal C}$}(x, x)=0, 则对于满足t≥r+ϕ(${\cal C}$)+(p－1)的正整数t, SR_t(X)⊇$\bigcup\nolimits_{i = 0}^{p - 1} {}$R_i(X), 其中p是正整数.

证明  ∀x∈X, 注意到d_{${\cal C}$}(x, x)=0.对于非负整数i(i=0, 1, …, p－1), 因为t－i≥r+ϕ(${\cal C}$)≥r_x+d_{${\cal C}$}(x, x)+ϕ(${\cal C}$), 由引理6可知:必然存在从点x到自身的长为t－i的SSSD途径对或符号为“#”的途径, 即SR_t－i({x})⊇{x}, 从而SR_t－i(X)⊇X.结合引理5, 对于非负整数i(i=0, 1, …, p－1), SR_t(X)⊇R_i(SR_t－i(X))⊇R_i(X), 进而SR_t(X)⊇$\bigcup\nolimits_{i = 0}^{p - 1} {}$R_i(X).

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

2.1   k点τ-基指数

定理1  设S∈CIPS_n^*, 其中|Z|=m, 且g是${\cal C}$中的最小奇数, 则

证明  若k≤m, 取非空k点子集X⊆Z; 若k>m, 因为S是本原的从而是强连通的, 故可取非空k点子集X⊇Z, 使得∀x∈X－Z均有长度为d_x≤k－m的途径可达Z.因此, 对于上述2种情形均有:∀x∈X, 存在从点x出发通过长为d_x≤max{0, k－m}的途径P_x可达Z(不妨设所达的点为z_x∈Z; 特别地, z_x和x可表示同一点).另外, 根据注3, 记$\mathscr{C}$中的最小奇有向圈为C′且其长度为g, 并且$\mathscr{C}$中含满足以下2种情形之一的有向圈C^*(设其长度为c^*):

情形1:C^*与C′构成违规圈对.因为z_x∈Z, 所以gC^*与c^*C′是从点z_x到自身长为gc^*的SSSD途径对, 进而P_x+gC^*与P_x+c^*C′是从点x到点z_x长为d_x+gc^*的SSSD途径对.

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

无论上述哪种情形, ∀x∈X, 总存在从点x到点z_x∈Z长为r_{x, zx}的SSSD途径对或符号为“#”的途径, 其中

再次注意到:z_x∈Z=$\bigcap\nolimits_{q = 1}^s {}$V(C_q), 故d_{${\cal C}$}(z_x, z_x)=0.令t=max{0, k－m}+gc₁+ϕ(${\cal C}$)+(τ－1).因为t≥r_{x, zx}+d_{${\cal C}$}(z_x, z_x)+ϕ(${\cal C}$)+(τ－1), 根据引理7, 有SR_t({x})⊇$\bigcup\nolimits_{i = 0}^{\tau - 1} {}$R_i({z_x}).结合引理4可得:|SR_t({x})|≥|$\bigcup\nolimits_{i = 0}^{\tau - 1} {}$R_i({z_x})|≥τ, 由命题1(ⅰ)可知定理得证.

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

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

2.2   k点τ-同位基指数

定理2  设S∈CIPS_n^*, 且g是${\cal C}$中的最小奇数，则

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

情形1:C^*与C′构成违规圈对.因为z∈$\bigcap\nolimits_{q = 1}^s {}$V(C_q), 所以gC^*与c^*C′是从点z到自身长为gc^*的SSSD途径对.进而∀x∈X, P_x+gC^*与P_x+c^*C′是从点x到点z长为d_x+gc^*的SSSD途径对.

情形2:C^*的符号为“#”(此时C^*和C′可以是同一个有向圈).同样因为z∈$\bigcap\nolimits_{q = 1}^s {}$V(C_q), 所以C^*是从点z到自身长为c^*且符号为“#”的途径, 进而∀x∈X, P_x+C^*是从点x到点z长为d_x+c^*且符号为“#”的途径.

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

又再注意到z∈$\bigcap\nolimits_{q = 1}^s {}$V(C_q), 故d_{${\cal C}$}(z, z)=0.另外, 由引理4可知:|$\bigcup\nolimits_{i = 0}^{\tau - 1} {}$R_i({z})|≥τ, 不妨设$\bigcup\nolimits_{i = 0}^{\tau - 1} {}$R_i({z})⊇{v₁, v₂, …, v_τ}.令

∀x∈X, 由于t≥r_{x, z}+d_{${\cal C}$}(z, z)+ϕ(${\cal C}$)+(τ－1), 由引理7可得:SR_t({x})⊇$\bigcup\nolimits_{i = 0}^{\tau - 1} {}$R_i({z})⊇{v₁, v₂, …, v_τ}, 由命题1(ⅱ)可知定理得证.

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

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

定理3  设S∈CIPS_n, 且g是${\cal C}$中的最小奇数, 则

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

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

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

无论上述哪种情形, ∀x∈X, 总存在从点x到点v∈Z长为r_{x, v}的SSSD途径对或符号为“#”的途径, 其中

又因为v∈Z=$\bigcap\nolimits_{q = 1}^s {}$V(C_q), 故d_{${\cal C}$}(v, v)=0.由引理4可知:|$\bigcup\nolimits_{i = 0}^{\tau - 1} {}$R_i({v})|≥τ, 不妨设$\bigcup\nolimits_{i = 0}^{\tau - 1} {}$R_i({v})⊇{v₁, v₂, …, v_τ}.令

∀x∈X, 由于t≥r_{x, v}+d_{${\cal C}$}(v, v)+ϕ(${\cal C}$)+(τ－1), 由引理7可得:SR_t({x})⊇$\bigcup\nolimits_{i = 0}^{\tau - 1} {}$R_i({v})⊇{v₁, v₂, …, v_τ}, 由命题1(ⅱ)即证得所需结论.

2.3   第k重下τ-基指数

定理4  设S∈CIPS_n^*, 其中|Z|=m, 且g是${\cal C}$中的最小奇数，则

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

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

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

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

由引理8, 有SR_t(X∩Z)⊇$\bigcup\nolimits_{i = 0}^{\max \{ 0, \tau - \min \{ k, m\} \} } {}$R_i(X∩Z).结合引理4可得:

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

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

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

定理5  设S∈CIPS_n, 且g是${\cal C}$中的最小奇数, 则

证明  根据注4, 可设$\mathscr{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 (不妨设从x∈V(C^*)出发到v∈Z), 记其长度为p, 易见:p≤n+1－c^*－m.那么, gC^*+P与P+c^*C′是从点x到点v长为p+gc^*的SSSD途径对, 或者C^*+P是从点x到点v长为c^*+p且符号为“#”的途径, 且

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

无论哪种情形, 必有从点x到某点v∈Z (v和x可以相同)长为r_{x, v}的SSSD途径对或符号为“#”的途径, 其中r_{x, v}≤ng.又因为v∈Z=$\bigcap\nolimits_{q = 1}^s {}$V(C_q), 故d_{${\cal C}$}(v, v)=0.令

取X⊇{x}, 由于t≥r_{x, v}+d_{${\cal C}$}(v, v)+ϕ(${\cal C}$)+(τ－1), 由引理7，有SR_t(X)⊇SR_t({x})⊇$\bigcup\nolimits_{i = 0}^{\tau - 1} {}$R_i({v}), 因此, 结合引理4可得:|SR_t(X)|≥|$\bigcup\nolimits_{i = 0}^{\tau - 1} {}$R_i({v})|≥τ, 由此根据命题1(ⅲ)即证得所需结论.

2.4   第k重上τ-基指数

定理6  设S∈CIPS_n^*, 其中|Z|=m, 且g是${\cal C}$中的最小奇数，则

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

情形1:n－m－k < 0.易见, X∩Z≠Ø且|X∩Z|≥k+m－n≥1.由于∀x∈X∩Z⊆Z=$\bigcap\nolimits_{q = 1}^s {}$V(C_q), 故d_{${\cal C}$}(x, x)=0.

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

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

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

由引理8, 有SR_t(X)⊇SR_t(X∩Z)⊇$\bigcup\nolimits_{i = 0}^{\max \{ 0, n - m - k + \tau \} } {}$R_i(X∩Z).再结合引理4可得:

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

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

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

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

又因为z∈Z=$\bigcap\nolimits_{q = 1}^s {}$V(C_q), 故d_{${\cal C}$}(z, z)=0.令

由于n－m+τ－k≥0, 从而

由引理7, 有SR_t(X)⊇SR_t({x})⊇$\bigcup\nolimits_{i = 0}^{\tau - 1} {}$R_i({z}).结合引理4可得:

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

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

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

定理7  设S∈CIPS_n, 且g是${\cal C}$中的最小奇数，则

证明  根据注4, 可设$\mathscr{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(不妨设从u∈V(C^*)出发到v∈Z), 记其长度为p, 易见:p≤n+1－c^*－m.对于任意的非空k点子集X, 记从X(不妨设为点x∈X)出发到点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且符号为“#”的途径, 且

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

无论上述哪种情形, 对于任意的非空k点子集X, 必有从点x∈X到某点v∈Z长为r_{x, v}的SSSD途径对或符号为“#”的途径, 其中r_{x, v}≤(n－k)+ng.又因为v∈Z=$\bigcap\nolimits_{q = 1}^s {}$V(C_q), 故d_{${\cal C}$}(v, v)=0.令

由于t≥r_{x, v}+d_{${\cal C}$}(v, v)+ϕ(${\cal C}$)+(τ－1), 由引理7可得:SR_t(X)⊇SR_t({x})⊇$\bigcup\nolimits_{i = 0}^{\tau - 1} {}$R_i({v}).因此, 结合引理4可得:

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

2.5   ω-不可分基指数

定理8  设S∈CIPS_n^*, 其中|Z|=m, 且g是${\cal C}$中的最小奇数, 则

证明  根据注3, 记$\mathscr{C}$中的最小奇有向圈为C′且其长度为g, 并且$\mathscr{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∈X∩Z⊆Z=$\bigcap\nolimits_{q = 1}^s {}$V(C_q), 故d_{${\cal C}$}(x, x)=0.

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

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

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

由引理8, 有SR_t(X)⊇SR_t(X∩Z)⊇$\bigcup\nolimits_{i = 0}^{n - m + \omega } {}$R_i(X∩Z).再由引理4可得:

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

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

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

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

又因为z∈Z=$\bigcap\nolimits_{q = 1}^s {}$V(C_q), 故d_{${\cal C}$}(z, z)=0.令

因为t≥r_{x, z}+d_{${\cal C}$}(z, z)+ϕ(${\cal C}$)+(k+ω－1), 由引理7, 有SR_t(X)⊇SR_t({x})⊇$\bigcup\nolimits_{i = 0}^{k + \omega - 1} {}$R_i({z}).结合引理4可得:

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

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

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

定理9  设S∈CIPS_n, 且g是${\cal C}$中的最小奇数, 则

证明  根据注4, 可设$\mathscr{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(不妨设从u∈V(C^*)出发到v∈Z), 记其长度为p, 易见:p≤n+1－c^*－m.对于任意的非空k点子集X, 记从X(不妨设为点x∈X)出发到点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且符号为“#”的途径, 且

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

无论上述哪种情形, 对于任意的非空k点子集X, 必有从点x∈X到某点v∈Z长为r_{x, v}的SSSD途径对或符号为“#”的途径, 其中r_{x, v}≤(n－k)+ng.又因为v∈Z=$\bigcap\nolimits_{q = 1}^s {}$V(C_q), 故d_{${\cal C}$}(v, v)=0.令

由于t≥r_{x, v}+d_{${\cal C}$}(v, v)+ϕ(${\cal C}$)+(k+ω－1), 由引理7可得:SR_t(X)⊇SR_t({x})⊇$\bigcup\nolimits_{i = 0}^{k + \omega - 1} {}$R_i({v}), 因此, 结合引理4可得:

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

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

以L_{n, 1}表示点集为V={v₁, v₂, …, v_n}, 弧集为E={(v_i, v_i+1)|1≤i≤n－1}∪{(v_n, v_n), (v_n, v₁)}的有向图.又设$\tilde S$_{n, 1}是以L_{n, 1}为底图的本原不可幂带号有向图.显然, $\tilde S$_{n, 1}∈LPS_n.由于$\tilde S$_{n, 1}仅有1个长为n的有向圈和1个长为1的环, 根据引理1, 它们必然构成违规圈对.从而由命题1可得:

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

推论6  设S∈LPS_n, 则

这些上界均可达且$\tilde S$_{n, 1}是极图之一, 其中，式(2)、(3)是文献[5]的结论.