The Research of Some Point Set Under the Condition of G-equicontinuity
-
摘要:
在映射f是G-等度连续的条件下,研究了G-链回归点、G-非游荡点、G-极限点和G-回归点之间的关系,得到如下结论:(1)RG(f)=WG(f)=ΩG(f); (2)WG(f)=CRG(f)=∞⋂n=1fn(X); (3)f是G-等度连续的当且仅当WG(f)中的所有点都是G-等度连续点。以上结论充实了度量G-空间中G-链回归点、G-非游荡点、G-极限点和G-回归点的理论。
Abstract:The relationship among G-chain recurrent point, G-nonwandering point, G-limit point and G-recurrent point were studied under the condition that the map f is G-equicontinuous. The following conclusions are obtained: (1)RG(f)=WG(f)=ΩG(f); (2)WG(f)=CRG(f)=∞⋂n=1fn(X); (3)f is G-equicontinuous if and only if all point in WG(f) are G-equicontinuous points. The above conclusions enrich the theory of G-chain recurrent point, G-nonwandering point, G-limit point, and G-recurrent point in metric G-space.
-
组合矩阵论[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}.
(ⅰ)A的k点τ-基指数[5], 记为lτ(A, k), 是最小的正整数t, 使得At中存在每行至少有τ个#元的k×n子阵.特别地, k点n-基指数又称为k点基指数[9-11], n点n-基指数(即n点基指数)正是上文已定义的基指数[2].
(ⅱ)A的k点τ-同位基指数[5], 记为φτ(A, k), 是最小的正整数t, 使得At中存在所有元素都是#的k×τ子阵.特别地, k点n-同位基指数也恰是k点基指数[9-11], 从而n点n-同位基指数也是基指数[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=v0x1v1…xkvk的符号sgn(W)可定义为该途径中所有弧的符号之积, 即sgn(W)=∏ki=1sgn(xi), 其中, v0∈V, vi∈V, xi∈E且xi=vi-1vi (i=1, 2, …, k).同理, 可定义(广义)带号有向图中路、圈、环等的符号.对于(广义)带号有向图中的2条途径W1和W2, 如果它们有相同的起点、相同的终点、相同的长度, 但符号相异(即“1”与“-1”), 称W1和W2为三同一异途径对(简称SSSD途径对)[4].本文中有关图论的定义和记号还可参见文献[14].
设SRt(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均有|SRt({x})|≥τ.
(ⅱ)S的k点τ-同位基指数φτ(S, k)是最小的正整数t, 使得存在k点子集X⊆V(S)及{v1, v2, …, vτ}⊆V(S), 满足∀x∈X均有SRt({x})⊇{v1, v2, …, vτ}.
(ⅲ)S的第k重下τ-基指数ψτ(S, k)是最小的正整数t, 使得存在k点子集X⊆V(S),满足|SRt(X)|≥τ.
(ⅳ)S的第k重上τ-基指数Lτ(S, k)是最小的正整数t, 使得对于任意的k点子集X⊆V(S),均满足|SRt(X)|≥τ.
(ⅴ)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}, 则
(ⅰ)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, 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.记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个有向圈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.记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)的违规圈对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 设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}.
2. 主要结果及其证明
为了刻画本文的主要结论, 下面先阐述若干通用的工具引理.设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] 若c1和c2是互质的正整数, 则ϕ(c1, c2)=(c1-1)(c2-1).
引理3[1] 设D是本原有向图, C={c1, c2, …, cs} (s≥2)是D中若干不同圈长之集, 且g.c.d.(C)=1.那么, 对于满足t≥dC(x, y)+ϕ(C)的非负整数t, 必然存在一条从点x到点y的长为t的途径.
设Rt(X)表示从点子集X中的任意点出发经过长为t的途径所能到达的所有点的集合, 简称可达集.
引理4[15] 设D是本原有向图, 且X是非空点子集, 即∅≠X⊆V(D), 则对于任意非负整数t, 有|⋃ti=0Ri(X)|≥min{n,|X|+t}.
结合可达集与模糊可达集的定义, 有如下结论.
引理5 设S∈PSn, 且Ø≠X⊆V(S),则
Ri(SRj(X))⊆SRi+j(X), 其中, i是非负整数, j是正整数.
证明 对于任意的点z∈Ri(SRj(X)), 必有一点y∈SRj(X), 使得存在从点y到点z长为i的途径, 记为P.进一步地, 必有一点x∈X, 使得存在从点x到点y长为j的SSSD途径对, 记为W1和W2 (或从点x到点y长为j且符号为“#”的途径, 记为W*).那么, W1+P和W2+P是从点x∈X到点z长为j+i的SSSD途径对(或W*+P是从点x∈X到点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 (u和v可以相同)长为ru, v的SSSD途径对W1和W2或符号为“#”的途径W*, 则对于满足t*≥ru, v+dC(v, y)+ϕ(C)的正整数t*, 必然存在从点u到点y的长为t*的SSSD途径对或符号为“#”的途径.
证明 因为t*≥ru, v+dC(v, y)+ϕ(C), 所以t*-ru, v≥dC(v, y)+ϕ(C).根据引理3, 必然存在一条从点v到点y长为t*-ru, v的途径, 记为P.那么, W1+P和W2+P是S中从点u到点y长为t*的SSSD途径对, 或W*+P是S中从点u到点y长为t*且符号为“#”的途径.
引理7 设S∈PSn, C={c1, c2, …, cs} (s≥2)是S中若干不同圈长之集, 且g.c.d.(C)=1.若S中存在从点u到点v (u和v可以相同)长为ru, v的SSSD途径对或符号为“#”的途径, 则对于满足t≥ru, v+dC(v, y)+ϕ(C)+(p-1)的正整数t, SRt({u})⊇⋃p−1i=0Ri({y}), 其中p是正整数.
证明 对于非负整数i=0, 1, …, p-1, 因为t-i≥ru, v+dC(v, y)+ϕ(C), 根据引理6, 必然存在从点u到点y的长为t-i的SSSD途径对或符号为“#”的途径, 即SRt-i({u})⊇{y}.结合引理5, 对于非负整数i=0, 1, …, p-1, SRt({u})⊇Ri(SRt-i({u}))⊇Ri({y}), 进而SRt({u})⊇⋃p−1i=0Ri({y}).
引理8 设S∈PSn, C={c1, c2, …, cs} (s≥2)是S中若干不同圈长之集, 且g.c.d.(C)=1.若S中存在点子集X满足:∀x∈X,均有从点x到自身长为rx≤r的SSSD途径对或符号为“#”的途径, 且dC(x, x)=0, 则对于满足t≥r+ϕ(C)+(p-1)的正整数t, SRt(X)⊇⋃p−1i=0Ri(X), 其中p是正整数.
证明 ∀x∈X, 注意到dC(x, x)=0.对于非负整数i(i=0, 1, …, p-1), 因为t-i≥r+ϕ(C)≥rx+dC(x, x)+ϕ(C), 由引理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), 进而SRt(X)⊇⋃p−1i=0Ri(X).
下文将研究5类结构指数分别在含交圈结构/含违规交圈结构的本原不可幂广义带号有向图类限制下的上界估值问题.
2.1 k点τ-基指数
定理1 设S∈CIPSn*, 其中|Z|=m, 且g是C中的最小奇数, 则
lτ(S,k)≤max{0,k−m}+τ−1+gc1+ϕ(C). 证明 若k≤m, 取非空k点子集X⊆Z; 若k>m, 因为S是本原的从而是强连通的, 故可取非空k点子集X⊇Z, 使得∀x∈X-Z均有长度为dx≤k-m的途径可达Z.因此, 对于上述2种情形均有:∀x∈X, 存在从点x出发通过长为dx≤max{0, k-m}的途径Px可达Z(不妨设所达的点为zx∈Z; 特别地, zx和x可表示同一点).另外, 根据注3, 记C中的最小奇有向圈为C′且其长度为g, 并且C中含满足以下2种情形之一的有向圈C*(设其长度为c*):
情形1:C*与C′构成违规圈对.因为zx∈Z, 所以gC*与c*C′是从点zx到自身长为gc*的SSSD途径对, 进而Px+gC*与Px+c*C′是从点x到点zx长为dx+gc*的SSSD途径对.
情形2:C*的符号为“#”(此时C*和C′可以是同一个有向圈).同样由于zx∈Z, 故C*是从点zx到自身长为c*且符号为“#”的途径, 进而Px+C*是从点x到点zx长为dx+c*且符号为“#”的途径.
无论上述哪种情形, ∀x∈X, 总存在从点x到点zx∈Z长为rx, zx的SSSD途径对或符号为“#”的途径, 其中
rx,zx≤max{dx+gc∗,dx+c∗}=dx+max{gc∗,c∗}≤max{0,k−m}+gc1. 再次注意到:zx∈Z=⋂sq=1V(Cq), 故dC(zx, zx)=0.令t=max{0, k-m}+gc1+ϕ(C)+(τ-1).因为t≥rx, zx+dC(zx, zx)+ϕ(C)+(τ-1), 根据引理7, 有SRt({x})⊇⋃τ−1i=0Ri({zx}).结合引理4可得:|SRt({x})|≥|⋃τ−1i=0Ri({zx})|≥τ, 由命题1(ⅰ)可知定理得证.
推论1 设S∈PSn, 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∈CIPSn*, 则由定理1和引理2即得所需结论.
2.2 k点τ-同位基指数
定理2 设S∈CIPSn*, 且g是C中的最小奇数,则
φτ(S,k)≤k+τ−2+gc1+ϕ(C). 证明 由于Z≠Ø, 不妨设z∈Z.因为S是本原的从而是强连通的, 故可取非空k点子集X⊇{z}, 使得∀x∈X, 均有长度为dx≤k-1的途径Px可达点z (注意:z和x可以是同一点).根据注3, 可设C中的最小奇有向圈为C′且其长度为g, 且C中含满足以下2种情形之一的有向圈C* (设其长度为c*):
情形1:C*与C′构成违规圈对.因为z∈⋂sq=1V(Cq), 所以gC*与c*C′是从点z到自身长为gc*的SSSD途径对.进而∀x∈X, Px+gC*与Px+c*C′是从点x到点z长为dx+gc*的SSSD途径对.
情形2:C*的符号为“#”(此时C*和C′可以是同一个有向圈).同样因为z∈⋂sq=1V(Cq), 所以C*是从点z到自身长为c*且符号为“#”的途径, 进而∀x∈X, Px+C*是从点x到点z长为dx+c*且符号为“#”的途径.
无论上述哪种情形, ∀x∈X, 总存在从点x到点z长为rx, z的SSSD途径对或符号为“#”的途径, 其中
rx,z≤max{dx+gc∗,dx+c∗}=dx+max{gc∗,c∗}≤(k−1)+gc1. 又再注意到z∈⋂sq=1V(Cq), 故dC(z, z)=0.另外, 由引理4可知:|⋃τ−1i=0Ri({z})|≥τ, 不妨设⋃τ−1i=0Ri({z})⊇{v1, v2, …, vτ}.令
t=(k−1)+gc1+ϕ(C)+(τ−1). ∀x∈X, 由于t≥rx, z+dC(z, z)+ϕ(C)+(τ-1), 由引理7可得:SRt({x})⊇⋃τ−1i=0Ri({z})⊇{v1, v2, …, vτ}, 由命题1(ⅱ)可知定理得证.
推论2 设S∈PSn, 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∈CIPSn*, 则由定理2和引理2即得所需结论.
定理3 设S∈CIPSn, 且g是C中的最小奇数, 则
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*+m≤n.设从C*出发到Z的最短途径为P (不妨设从u∈V(C*)出发到v∈Z), 记其长度为p, 易见:p≤n+1-c*-m.由于S是强连通的, 故可取非空k点子集X⊇{u}, 使得∀x∈X,均有长度为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≠Ø.取v∈V(C*)∩Z.同样根据S的强连通性, 可取非空k点子集X⊇{v}, 使得∀x∈X, 均有长度为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. 无论上述哪种情形, ∀x∈X, 总存在从点x到点v∈Z长为rx, v的SSSD途径对或符号为“#”的途径, 其中
rx,v≤k−1+ng. 又因为v∈Z=⋂sq=1V(Cq), 故dC(v, v)=0.由引理4可知:|⋃τ−1i=0Ri({v})|≥τ, 不妨设⋃τ−1i=0Ri({v})⊇{v1, v2, …, vτ}.令
t=(k−1+ng)+ϕ(C)+(τ−1). ∀x∈X, 由于t≥rx, v+dC(v, v)+ϕ(C)+(τ-1), 由引理7可得:SRt({x})⊇⋃τ−1i=0Ri({v})⊇{v1, v2, …, vτ}, 由命题1(ⅱ)即证得所需结论.
2.3 第k重下τ-基指数
定理4 设S∈CIPSn*, 其中|Z|=m, 且g是C中的最小奇数,则
ψτ(S,k)≤max{0,τ−min{k,m}}+gc1+ϕ(C). 证明 若k≤m, 取非空k点子集X⊆Z; 若k>m, 取非空k点子集X⊇Z.显然, X∩Z⊆Z且|X∩Z|=min{k, m}.由于∀x∈X∩Z⊆Z=⋂sq=1V(Cq), 故dC(x, x)=0.另外, 根据注3, 记C中的最小奇有向圈为C′且其长度为g, 并且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到自身长为rx的SSSD途径对或符号为“#”的途径, 其中rx≤max{gc*, c*}≤gc1.令
t=gc1+ϕ(C)+max{0,τ−min{k,m}}. 由引理8, 有SRt(X∩Z)⊇⋃max{0,τ−min{k,m}}i=0Ri(X∩Z).结合引理4可得:
|SRt(X)|≥|SRt(X∩Z)|≥|max{0,τ−min{k,m}}⋃i=0Ri(X∩Z)|≥τ, 从而由命题1(ⅲ)可知定理得证.
推论3 设S∈PSn, 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∈CIPSn*, 则由定理4和引理2即得所需结论.
定理5 设S∈CIPSn, 且g是C中的最小奇数, 则
ψτ(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*+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且符号为“#”的途径, 且
max{p+gc∗,c∗+p}≤(n+1−c∗−m)+gc∗≤n−m+(g−1)(n−m)+1≤ng. 情形2:V(C*)∩Z≠Ø.令x∈V(C*)∩Z.从而, gC*与c*C′是从点x到点x长为gc*的SSSD途径对, 或C*是从点x到点x长为c*且符号为“#”的途径, 且
max{gc∗,c∗}≤gc∗≤ng. 无论哪种情形, 必有从点x到某点v∈Z (v和x可以相同)长为rx, v的SSSD途径对或符号为“#”的途径, 其中rx, v≤ng.又因为v∈Z=⋂sq=1V(Cq), 故dC(v, v)=0.令
t=ng+ϕ(C)+(τ−1). 取X⊇{x}, 由于t≥rx, v+dC(v, v)+ϕ(C)+(τ-1), 由引理7,有SRt(X)⊇SRt({x})⊇⋃τ−1i=0Ri({v}), 因此, 结合引理4可得:|SRt(X)|≥|⋃τ−1i=0Ri({v})|≥τ, 由此根据命题1(ⅲ)即证得所需结论.
2.4 第k重上τ-基指数
定理6 设S∈CIPSn*, 其中|Z|=m, 且g是C中的最小奇数,则
Lτ(S,k)≤max{0,n−m−k+τ}+gc1+ϕ(C). 证明 根据注3, 记C中的最小奇有向圈为C′且其长度为g, C中含有向圈C* (设其长度为c*).对于任意的非空k点子集X, 分别考虑以下2种情形.
情形1:n-m-k < 0.易见, X∩Z≠Ø且|X∩Z|≥k+m-n≥1.由于∀x∈X∩Z⊆Z=⋂sq=1V(Cq), 故dC(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到自身长为rx的SSSD途径对或符号为“#”的途径, 其中rx≤max{gc*, c*}≤gc1.令
t=gc1+ϕ(C)+max{0,n−m−k+τ}. 由引理8, 有SRt(X)⊇SRt(X∩Z)⊇⋃max{0,n−m−k+τ}i=0Ri(X∩Z).再结合引理4可得:
|SRt(X)|≥|SRt(X∩Z)|≥|max{0,n−m−k+τ}⋃i=0Ri(X∩Z)|≥τ. 情形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长为rx, z的SSSD途径对或符号为“#”的途径, 其中
rx,z≤max{d+gc∗,d+c∗}≤(n+1−k−m)+max{gc∗,c∗}≤(n+1−k−m)+gc1. 又因为z∈Z=⋂sq=1V(Cq), 故dC(z, z)=0.令
t=max{0,n−m+τ−k}+gc1+ϕ(C). 由于n-m+τ-k≥0, 从而
t=(n−m−k+τ)+gc1+ϕ(C)=(n+1−k−m)+gc1+ϕ(C)+(τ−1)≥rx,z+dC(z,z)+ϕ(C)+(τ−1), 由引理7, 有SRt(X)⊇SRt({x})⊇⋃τ−1i=0Ri({z}).结合引理4可得:
|SRt(X)|≥|SRt({x})|≥|τ−1⋃i=0Ri({z})|≥τ. 综上2种情形, 由命题1(ⅳ)可得所需结论.
推论4 设S∈PSn, 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∈CIPSn*, 则由定理6和引理2即得所需结论.
定理7 设S∈CIPSn, 且g是C中的最小奇数,则
Lτ(S,k)≤n+τ−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*+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且符号为“#”的途径, 且
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≠Ø.令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*且符号为“#”的途径, 且
max{w+gc∗,w+c∗}≤(n−k)+gc∗≤(n−k)+ng. 无论上述哪种情形, 对于任意的非空k点子集X, 必有从点x∈X到某点v∈Z长为rx, v的SSSD途径对或符号为“#”的途径, 其中rx, v≤(n-k)+ng.又因为v∈Z=⋂sq=1V(Cq), 故dC(v, v)=0.令
t=(n−k)+ng+ϕ(C)+(τ−1). 由于t≥rx, v+dC(v, v)+ϕ(C)+(τ-1), 由引理7可得:SRt(X)⊇SRt({x})⊇⋃τ−1i=0Ri({v}).因此, 结合引理4可得:
|SRt(X)|≥|SRt({x})|≥|τ−1⋃i=0Ri({v})|≥τ, 由此, 根据命题1(ⅳ)即证得所需结论.
2.5 ω-不可分基指数
定理8 设S∈CIPSn*, 其中|Z|=m, 且g是C中的最小奇数, 则
εω(S)≤n−m+ω+gc1+ϕ(C). 证明 根据注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∈X∩Z⊆Z=⋂sq=1V(Cq), 故dC(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到自身长为rx的SSSD途径对或符号为“#”的途径, 其中rx≤max{gc*, c*}≤gc1.令
t=gc1+ϕ(C)+(n−m+ω). 由引理8, 有SRt(X)⊇SRt(X∩Z)⊇⋃n−m+ωi=0Ri(X∩Z).再由引理4可得:
|SRt(X)|≥|SRt(X∩Z)|≥|n−m+ω⋃i=0Ri(X∩Z)|≥k+ω. 情形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长为rx, z的SSSD途径对或符号为“#”的途径, 其中
rx,z≤max{d+gc∗,d+c∗}≤(n+1−k−m)+max{gc∗,c∗}≤(n+1−k−m)+gc1. 又因为z∈Z=⋂sq=1V(Cq), 故dC(z, z)=0.令
t=(n+1−m−k)+gc1+ϕ(C)+(k+ω−1). 因为t≥rx, z+dC(z, z)+ϕ(C)+(k+ω-1), 由引理7, 有SRt(X)⊇SRt({x})⊇⋃k+ω−1i=0Ri({z}).结合引理4可得:
|SRt(X)|≥|SRt({x})|≥|k+ω−1⋃i=0Ri({z})|≥k+ω. 综上2种情形, 根据命题1(ⅴ)可得所需结论.
推论5 设S∈PSn, 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∈CIPSn*, 则由定理8和引理2即得所需结论.
定理9 设S∈CIPSn, 且g是C中的最小奇数, 则
εω(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*+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且符号为“#”的途径, 且
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≠Ø.令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*且符号为“#”的途径, 且
max{w+gc∗,w+c∗}≤(n−k)+gc∗≤(n−k)+ng. 无论上述哪种情形, 对于任意的非空k点子集X, 必有从点x∈X到某点v∈Z长为rx, v的SSSD途径对或符号为“#”的途径, 其中rx, v≤(n-k)+ng.又因为v∈Z=⋂sq=1V(Cq), 故dC(v, v)=0.令
t=(n−k)+ng+ϕ(C)+(k+ω−1). 由于t≥rx, v+dC(v, v)+ϕ(C)+(k+ω-1), 由引理7可得:SRt(X)⊇SRt({x})⊇⋃k+ω−1i=0Ri({v}), 因此, 结合引理4可得:
|SRt(X)|≥|SRt({x})|≥|k+ω−1⋃i=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≤i≤n-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+τ−k−1,εω(˜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+τ−k−1, (4) εω(S)≤2n+ω−1, (5) 这些上界均可达且˜Sn, 1是极图之一, 其中,式(2)、(3)是文献[5]的结论.
-
[1] 冀占江, 覃桂茳, 时伟. 群作用下逆极限空间中移位映射的动力学性质[J]. 安徽大学学报(自然科学版), 2020, 44(5): 41-45. JI Z J, QING G J, SHI W. Dynamical properties of the shift map in inverse limit space of group action[J]. Journal of Anhui University(Natural Science Edition), 2020, 44(5): 41-45.
[2] 曹毅, 吴晓荣. 正上密度回归点集的若干性质[J]. 福州大学学报(自然科学版), 2016, 44(3): 401-404. CAO Y, WU X R. Some properties of positive upper density recurrence points[J]. Journal of Fuzhou University(Natural Science Edition), 2016, 44(3): 401-404.
[3] 冀占江. 群作用下逆极限空间上移位映射的G非游荡点与G链回归点[J]. 湖南师范大学自然科学学报, 2018, 41(6): 77-81. JI Z J. G-nonwandering points and G-chain recurrent points of the shift map in the inverse limit spaces of a topological group action[J]. Journal of Natural Science of Hunan Normal University, 2018, 41(6): 77-81.
[4] 贺毅, 张君, 白丹莹. 逆极限空间转移映射非游荡集的中心测度[J]. 重庆工商大学学报(自然科学版), 2015, 32(5): 49-51. HE Y, ZHANG J, BAI D Y. Measurement of the center of the inverse limit space transition mapping none-wande-ring set[J]. Journal of Chongqing Technology and Business University(Natural Science Edition), 2015, 32(5): 49-51.
[5] 霍展福. 类帐篷映射上的链回归点集研究[D]. 南宁: 广西大学, 2019. HUO Z F. Study on the sat of chain recurrent points on the tent-like mapping[D]. Nanning: Guangxi University, 2019.
[6] 孙太祥, 席鸿建. 图映射的负极限集[J]. 中国科学: 数学, 2017, 47(5): 591-598. SUN T X, XI H J. Negative limit sets of graph maps[J]. Scientia Sinica: Mathematica, 2017, 47(5): 591-598.
[7] 罗飞, 金渝光. 强一致收敛条件下序列系统与极限系统的关联性[J]. 重庆师范大学学报(自然科学版), 2015, 32(4): 78-80. LUO F, JIN Y G. The condition of strong uniform convergence of relationship between sequence system and limit the system[J]. Journal of Chongqing Normal University(Natural Science), 2015, 32(4): 78-80.
[8] 孙太祥, 曾凡平, 秦斌, 等. 广义树映射的吸引中心和w-极限集空间[J]. 中国科学: 数学, 2018, 48(9): 1131-1142. SUN T X, ZENG F P, QING B, et al. The attracting centre and space of w-limit sets of a general tree map[J]. Scientia Sinica: Mathematica, 2018, 48(9): 1131-1142.
[9] 耿雪萍. 动力系统中几类点集的不变性研究[D]. 重庆: 重庆师范大学, 2015. GENG X P. Study invariance of several points set in dynamical system[D]. Chongqing: Chongqing Normal University, 2015.
[10] 陈彬. 动力系统中的回复性与混沌行为[D]. 南京: 南京大学, 2016. CHEN B. Recurrence and chaotic behavior of dynamical systems[D]. Nanjing: Nanjing University, 2016.
[11] 曾眺英. 有向部分半群作用下的敏感性[J]. 华南师范大学学报(自然科学版), 2021, 53(6): 105-110. doi: 10.6054/j.jscnun.2021099 ZENG T Y. The sensitivity under directed partial semi-group actions[J]. Journal of South China Normal University(Natural Science Edition), 2021, 53(6): 105-110. doi: 10.6054/j.jscnun.2021099
[12] AHMADI S A. Invariants of topological G-conjugacy on G-spaces[J]. Mathematica Moravica, 2014, 18: 67-75. doi: 10.5937/MatMor1401067A
[13] JI Z J. The G-sequence shadowing property and G-equicontinuity of the inverse limit spaces under group action[J]. Open Mathematics, 2021, 19: 1290-1298. doi: 10.1515/math-2021-0102
[14] BALOGH Z, LAVER V. Unitary subgroups of commutative group algebras of the characteristic two[J]. Ukrainian Mathematical Journal, 2020, 72: 871-879. doi: 10.1007/s11253-020-01829-3
[15] CHOI T, KIM J. Decomposition theorem on G-spaces[J]. Osaka Journal of Mathematics, 2009, 46: 87-104.
-
期刊类型引用(1)
1. 王正家,曾雨晴,徐欣犀,徐佑犀,王超. 基于多传感器的机器人夹取系统研究. 机床与液压. 2023(11): 27-33 . 百度学术
其他类型引用(0)
计量
- 文章访问数: 52
- HTML全文浏览量: 9
- PDF下载量: 34
- 被引次数: 1