黃宇飛 ，柳柏濂

(1. 廣州民航職業(yè)技術學院，廣州510403;2. 華南師范大學數學科學學院，廣州510631)

記n 階(0，1)矩陣集為Bn.對于A=(aij) Bn，其可以和一個具有n個頂點的有向圖D =(V，E)建立一一對應關系，其中V ={v1，v2，…，vn}是標號頂點集，E 是弧集，且這里1≤i，j≤n.稱A(或記為A(D))為有向圖D 的鄰接矩陣，把D(或記為D(A))叫做矩陣A 的伴隨有向圖.

記所有元素都是“1”的n 階矩陣為Jn. 一個矩陣A Bn稱為本原的，如果存在正整數k 使得Ak=Jn;等價地，一個有向圖D =(V，E)是本原的，如果存在正整數k 使得任意兩點u，v V(u 和v 可以表示同一點)，在D 中有從點u 到點v 長為k 的途徑.我們把n 階本原矩陣集(或本原有向圖集)記為Pn.

對于一個有向圖D=(V，E)及點子集X?V，以Rt(X)(又稱可達集)表示從點子集X 中的任意頂點出發(fā)，通過長為t 的途徑所能到達的所有點的集合，其中t 為非負整數. 設D =(V，E)是一個本原有向圖，容易驗證:R0(X)=X，Ri(X)=Ri-j(Rj(X))，其中X?V，且i 和j 是滿足i≥j 的非負整數.

在有限馬爾科夫鏈理論中，轉移概率的遍歷性及遍歷指數的問題，與本原矩陣的局部性質有著自然的聯系［1-2］.根據理論和實踐的需要，基于非記憶通信系統(tǒng)的數學模型［3］，Huang 和Liu［4］于2011年提出了4 類廣義本原r-指數的概念:設n，k，r 是滿足1≤k，r≤n 的正整數，則

(1)本原矩陣A Pn的k 點r-指數pr(A，k)是A 的最小冪指數，使得在這個冪中存在k ×n 階子矩陣每行均有r個“1”元;等價地，本原有向圖D Pn的k 點r-指數pr(D，k)是最小的非負整數p，使得存在由k個點構成的子集X?V(D)，對于每一個頂點x X 都有|Rp({x})|≥r.

(2)本原矩陣A Pn的k 點r-同位指數sr(A，k)是A 的最小冪指數，使得在這個冪中存在k×r 階全“1”子矩陣;等價地，本原有向圖D Pn的k 點r-同位指數sr(D，k)是最小的非負整數p，使得存在由k個點構成的子集X?V(D)，及某r個點v1，…，vrV(D)，其滿足?x X 都有Rp({x})?{v1，…，vr}.

(3)本原矩陣A Pn的第k 重下r-指數fr(A，k)是A 的最小冪指數，使得在這個冪中存在k×r 階無零列子矩陣;等價地，本原有向圖D Pn的第k重下r-指數fr(D，k)是最小的非負整數p，使得存在k 點子集X?V(D)滿足|Rp(X)|≥r.

(4)本原矩陣A Pn的第k 重上r-指數Fr(A，k)是A 的最小冪指數，使得在這個冪中任意k ×n階子矩陣至多有n -r 列全零列;等價地，本原有向圖D Pn的第k 重上r-指數Fr(D，k)是最小的非負整數p，使得任意k個點構成的子集X?V(D)均滿足|Rp(X)|≥r.

廣義本原r-指數是著名的本原指數和廣義本原指數［5-6］的進一步拓廣，其對本原矩陣冪序列中的行和列進行了更精細的刻畫.在文獻［3］中，關于一般的n 階本原矩陣(有向圖)的4 類廣義本原r-指數的上界問題得到了初步的研究. 本文將繼續(xù)探討若干特殊的本原矩陣(有向圖)類(如:w-不可分矩陣、w-幾乎可分矩陣、完全不可分矩陣、幾乎可分矩陣、含多圈結構的本原有向圖、含交圈結構的本原有向圖、微對稱本原矩陣和對稱本原矩陣等)其廣義本原r-指數的上界問題.

1 不可分矩陣的廣義本原r-指數

設w 是滿足-n ＜w ＜n 的整數.如果A Bn不含k×l 階零子矩陣，其中1≤k，l≤n 且k +l =n -w+1，則稱A 為w-不可分方陣［7］，亦稱其伴隨有向圖D=D(A)是w-不可分的. 記n 階w-不可分方陣(有向圖)之集為Bn，w.易見，w-不可分方陣有如下的圖論刻畫［7-9］:A Bn，w當且僅當D(A)中任一k(1≤k≤n)點子集X?V(D(A))都有|R1(X)|≥min{n，k+w}.對于A Bn，w，若將其任一非零元換成零元后所得矩陣不再是w-不可分的，則稱A 為w-幾乎可分方陣［7］，同樣把其伴隨有向圖D =D(A)稱作w-幾乎可分的.又記n 階w-幾乎可分方陣(有向圖)之集為NDn，w.特別地，把1-不可分方陣(有向圖)和1-幾乎可分方陣(有向圖)又分別稱為完全不可分方陣(有向圖)和幾乎可分方陣(有向圖)，且記Bn，1=Fn，NDn，1=NDn.

另外，對于整數w1(-n+1 ＜w1＜n)和w2(1≤w2＜n)，w1-不可分方陣必然是(w1-1)-不可分方陣，從而w2-不可分方陣必然是完全不可分方陣，故也是本原方陣［7］，即Bn，w1?Bn，w1-1，Bn，w2?Fn?Pn.下面將分別研究w2-不可分矩陣和w2-幾乎可分矩陣其k 點r-指數和第k 重上r-指數的上界.

在本節(jié)的余下部分，默認假設n，k，r，w 是滿足1≤k，r≤n 且1≤w ＜n 的正整數.為方便起見，采用圖論的語言來闡述主要結論.

1.1 k 點r-指數

定理1 設D Bn，w(或D NDn，w)，其中1≤w＜n，則pr(D，k)≤「(r-1)/w?.

證明 若D Bn，w(1≤w ＜n)，根據其圖論意義可知:任一k (1≤k≤n)點子集X?V(D)都有|R1(X)|≥min{n，k+w}，從而對于?v V(D)，有

其中p=「(r-1)/w?. 結合k 點r-指數的定義即得結論.

若D NDn，w，注意到:NDn，w?Bn，w，故類似可得結論. □

對于完全不可分、幾乎可分方陣(有向圖)，可進一步求得其k 點r-指數的上確界.

設D1是頂點集為V={i|1≤i≤n}、弧集為E={(i，i+1)，(i +1，i)|1≤i≤n -1}∪{(1，1)，(n，n)}的有向圖(圖1).顯然，D1NDn?Fn?Pn.

圖1 有向圖D1Figure 1 Digraph D1

定理2 設D Fn(或D NDn)，則pr(D，k)≤r-1，此上界可達且D1是極圖之一.

證明 若D Fn=Bn，1，由定理1 可得pr(D，k)≤r-1. 下面僅需證明pr(D1，k)=r -1 即得結論.一方面，由于D1Fn=Bn，1，根據定理1，pr(D1，k)≤r-1.另一方面，可直接驗證:對于任意頂點v V(D1)，以及滿足t ≤r - 2 的任意非負整數t，|Rt({v})| =t+1≤r -1，故pr(D1，k)≥r -1. 綜上可得:pr(D1，k)=r-1.

類似地，若D NDn= NDn，1，不難發(fā)現D1NDn，結合定理1 即得:pr(D，k)≤r -1，此上界可達且D1是極圖之一. □

注意到:當r =n 時，k 點n-指數即是廣為研究的k 點指數［3］.由定理2 立可推出完全不可分方陣和幾乎可分方陣其k 點指數的上確界.

推論1 設D Fn(或D NDn)，則其k 點指數p(D，k)=pn(D，k)≤n-1，此上界可達且D1是極圖之一.

1.2 第k 重上r-指數

引理1［4］設n，k，r 是滿足1≤k，r≤n 的正整數，D 是一個n 階本原有向圖，則Fr(D，k)=0 當且僅當k≥r.

根據引理1，本節(jié)默認假設k ＜r.

定理3 設D Bn，w(或D NDn，w)，其中1≤w＜n，則Fr(D，k)≤「(r-k)/w?.

證明 若D Bn，w(1≤w ＜n)，由其圖論意義可知:任一k (1 ≤k ≤n)點子集X ?V(D)都有|R1(X)|≥min{n，k +w}，從而對于?X?V(D)且|X| =k，有其中p =「(r -k)/w?.根據第k 重上r-指數的定義可得:Fr(D，k)≤p=「(r-k)/w?.

若D NDn，w，由于NDn，w?Bn，w，同理可證得結論. □

下面給出完全不可分方陣(有向圖)和幾乎可分方陣(有向圖)其第k 重上r-指數的上確界.

設Dk(1≤k≤n)表示頂點集為V ={i|1≤i≤n}、弧集為E ={(i，k +1)，(k +1，i)|1≤i≤k}∪{(i，i+1)，(i+1，i)|k+1≤i≤n-1}∪{(i，i)|1≤i≤k，或i=n}的有向圖(圖2).易見，DkNDn?Fn?Pn(1≤k≤n).

圖2 有向圖Dk(1≤k≤n)Figure 2 Digraph Dk(1≤k≤n)

關于本原有向圖Dk的第k 重上r-指數有如下的結論:

引理2 Fr(Dk，k)=r-k.

證明 一方面，由于DkNDn=NDn，1?Fn=Bn，1，由定理3 可得:Fr(Dk，k)≤r -k. 另一方面，取k 點子集X={1，…，k}，易見:對于滿足t≤r -k -1的任意非負整數t，均有|Rt(X)| =k +t≤r -1，故Fr(Dk，k)≥r-k.綜上可得結論成立. □

定理4 設D Fn(或D NDn)，則Fr(D，k)≤r-k，此上界可達且Dk是極圖之一.

證明 對于D Fn=Bn，1(或D NDn=NDn，1)，由定理3 可得:Fr(D，k)≤r -k. 又因DkNDn?Fn，結合引理2 即得結論. □

當r =n 時，第k 重上n-指數正是第k 重上指數［3］.根據定理4 可得完全不可分方陣和幾乎可分方陣其第k 重上指數的上確界.

推論2 設D Fn(或D NDn)，則其第k 重上指數F(D，k)=Fn(D，k)≤n -k，此上界可達且Dk是極圖之一.

2 含特殊圈結構的本原有向圖的廣義本原r-指數

首先介紹下文需要用到的若干重要引理.

引理3［1］D Pn當且僅當D 是一個n 階的強連通有向圖，且D 中所有不同圈長的最大公因數等于1.

設D Pn.以R=R(D)表示D 中所含的若干不同圈長之集，又記從點u 到點v 且與R 中每種長度的圈均相交的最短途徑之長為dR(u，v).設R={c1，…，cs}(s≥2)表示一個互質的正整數集，以φ(R)=φ(c1，…，cs)表示互質正整數c1，…，cs的Frobenius數.關于Frobenius 數的定義及有關結論可參見文獻［1］，其中一個重要的結論如下:

引理4［1］設c1、c2是互質的正整數，則φ(c1，c2)=(c1-1)(c2-1).

引理5［1］設D Pn，且c1，c2，…，cs(s≥2)是D 中若干不同的圈長，其中ci≠cj(1≤i ＜j≤s)，g.c.d.(c1，c2，…，cs)=1 (g. c. d. 表示最大公因數).令R={c1，c2，…，cs}.那么，對于滿足t≥dR(i，j)+φ(R)的非負整數t，必然存在一條從點i 到點j的長為t 的途徑.

引理6［10］設D Pn，且X 是一個非空點子集，即?≠X?V(D).則對于任意非負整數t，都有

接下來給出幾類含特殊圈結構的本原有向圖的定義.

定義1［11］設D Pn，且C ={C1，C2，…，Cs}(s≥2)是其若干不同長度的有向圈構成的一個子集，并記有向圈Cq的長度為cq(q =1，2，…，s). 若c1＞c2＞… ＞cs≥1，g. c. d. (c1，c2，…，cs)=1，且所有有向圈Cq(q=1，…，s)有m (≥1)個公共點，即V(Cq)| =m，則稱D 為含交圈結構的本原有向圖.記含交圈結構的n 階本原有向圖之集為CIPn.

定義2［10，12］設A=(aij) Bn.若?1≤i ＜j≤n都有aij=aji=1，則稱A 為對稱矩陣，D(A)為對稱有向圖;若存在1≤i ＜j≤n 滿足aij=aji=1，則稱A為微對稱矩陣，D(A)為微對稱有向圖.記n 階對稱本原矩陣(有向圖)之集為SPn，n 階微對稱本原矩陣(有向圖)之集為MSPn.

下面將從含多圈結構的本原有向圖出發(fā)展開研究，逐步探討若干含特殊圈結構的本原有向圖其4類廣義本原r-指數的上界問題.為方便敘述，采用圖論的語言來刻畫主要結論.如無特別說明，默認假設n，k，r 是滿足1≤k，r≤n 的正整數.

2.1 第k 重上r-指數

根據引理1，此節(jié)均默認假設k ＜r.

定理5 設D Pn，且C1，…，Cs(s≥2)是D 中若干不同長度的有向圈，又記有向圈Cq的長度為cq(q=1，…，s)，且R={c1，…，cs}，其中c1＞…＞cs≥1，g.c.d.(c1，…，cs)=1.則

證明 對于任意的非空k 點子集X，構建從X出發(fā)且與R 中每種長度的有向圈均相交的最短途徑:記從X 出發(fā)到有向圈C1的最短途徑為W1，易見W1的長度l1≤max{0，(n-c1)+(1-k)};又記從X 出發(fā)經有向圈C1再到有向圈C2的最短途徑為W1+W2，則W1+W2的長度(1－k)};以此類推，可找到一條從X 出發(fā)依次經過有向圈C1，…，Cs-1最終到達有向圈Cs的最短途徑W1+W2+… +Ws，其總長度為

必然存在從點x 到點ys的長為p - i 的途徑，則Rp({x})?Ri({ys}).因此，結合引理6 可得:

所以存在從點x*到其自身長為p -i 的途徑. 結合引理6 可得:

綜上，結合第k 重上r-指數的定義可得結論. □

定理5 刻畫了含多圈結構的本原有向圖其第k重上r-指數的上界.采用類似的方法，接下來考慮含交圈結構的本原有向圖.

定理6 設D CIPn，且D 中含有若干不同長度的有向圈C1，…，Cs(s≥2)，記其長度分別為c1，…，cs，令R={c1，…，cs}，其中c1＞…＞cs≥1，g.c.d.(c1，…，cs)=1，且|V(Cq)| =m(≥1).則

情形1:n-m-k ＜0.易見，|X∩Z|≥m +k -n≥1，即X∩Z≠?.注意到:從X∩Z 中的任一點x 出發(fā)到其自身與R 中每種長度的有向圈均相交的最短途徑之長為0，即dR(x，x)=0. 又由引理5，對于非負整數i=0，…，(n -m)+(r -k)，因為p -i≥φ(R)=dR(x，x)+φ(R)，所以存在從點x 到其自身長為p-i 的途徑.結合引理6 可得:

情形2:n -m -k≥0.記從X(不妨設為點x X)出發(fā)到Z(不妨設為點z Z)的最短途徑為W，則W 的長度d≤n+1 -k-m(＞0).由于W 是從點x X 到點z Z 且與R 中每種長度的有向圈均相交的最短途徑，故dR(x，z)≤(n -m)+(1 -k). 根據引理5，對于非負整數i=0，…，r-1，由于

必然存在從點x 到點z 的長為p - i 的途徑，從而Rp({x})?Ri({z}).再結合引理6 可得:

根據第k 重上r-指數的定義，綜上可得結論. □

作為定理5 及定理6 的特殊情況，令s=2(即所考慮的圈結構由2 種不同長度的有向圈構成)，結合引理4 有以下的推論.

推論3 設D Pn，且C1，C2是D 中長度分別為c1，c2的有向圈，其中c1＞c2≥1，g.c.d.(c1，c2)=1.則

推論4 設D CIPn，且C1，C2是D 中長度分別為c1，c2的有向圈，其中c1＞c2≥1，g.c.d.(c1，c2)=1，且|V(C1)∩V(C2)| =m(≥1).則

注1 對上述幾個定理和推論中的圈長等變量賦值，可導出更多有趣的結論. 例如:令推論4 中的c1=3，c2=m =2，有Fr(D，k)≤n +r -k，這正是文獻［4］的定理5.6.

下面進一步特殊化本原有向圖的圈結構，分別研究n 階微對稱有向圖集MSPn和n 階對稱本原有向圖集SPn的第k 重上r-指數.

定理7 設D MSPn，則

證明 由于D MSPn，結合引理3 可知:D 中含有長度分別為2 和c 的有向圈，其中c 是奇數，即g.c.d.(2，c)=1.則利用推論3 即得結論. □

定理8 設D SPn，則

證明 因為D SPn，所以D 中每一個點均落于一個長為2 的有向圈上，又結合引理3 可知:D 中必含一個長為奇數c 的有向圈C.

令p=(n -1)+(r -k)，R ={2，c}. 由引理4知:φ(R)=φ(2，c)=c -1.對于任意的非空k 點子集X，分2 種情形討論從X 出發(fā)到C 的最短途徑:

情形1:n-c -k ＜0.顯然，|X∩V(C)|≥c +k-n≥1，即X∩V(C)≠?.注意到:從X∩V(C)中的任一點x 出發(fā)到其自身與R 中每種長度的有向圈均相交的最短途徑之長為0，即dR(x，x)=0.根據引理5，對于非負整數i =0，…，(n - c)+ (r - k)，由于p-i≥c-1 =dR(x，x)+φ(R)，故有從點x 到其自身長為p-i 的途徑.從而結合引理6 可得:|Rp(X)|≥|Rp(X∩V(C))|≥|Ri(X∩V(C))|≥(c+k-n)+［(n-c)+(r-k)］=r.

情形2:n -c -k≥0. 記從X(不妨設為點x X)出發(fā)到C(不妨設為點y C)的最短途徑為W，則W 的長度d≤n+1 -k-c(＞0).由于W 是從點x X 到點y C 且與R 中每種長度的有向圈均相交的最短途徑，故dR(x，y)≤(n -c)+(1 -k). 根據引理5，對于非負整數i=0，…，r-1，由于

必存在從點x 到點y 的長為p - i 的途徑，從而Rp({x})?Ri({y}).故由引理6 可得:

根據第k 重上r-指數的定義可得結論. □

對比分析定理6 和定理8 的證明過程，我們發(fā)現，定理6 還可作下列形式的推廣(證明類似于定理6，此處略).

定理9 設D Pn，且D 中含有長度為cq的若干個有向圈Cq，1，…，Cq，tq，其中cq，tq是正整數，q =1，…，s(s≥2).又設ci≠cj(1≤i ＜j≤s)，R={c1，…，cs}，g.c.d.(c1，…，cs)=1，且=m(≥1).則

注2 易見，由定理9 可直接導出定理8.另外，定理9 還可推出帶環(huán)的本原有向圖其第k 重上r-指數的上界(見文獻［4］的定理5.2).

2.2 第k 重下r-指數

引理7［4］設n，k，r 是滿足1≤k，r≤n 的正整數，D 是一個n 階本原有向圖，則fr(D，k)=0 當且僅當k≥r.

由引理7，本節(jié)默認假設k ＜r.

定理10 設D Pn，且D 中含有長度為cq的若干個有向圈Cq，1，…，Cq，tq，記Vq=V(Cq，j)，其中cq，tq均是正整數，q =1，…，s(s≥2). 又設ci≠cj(1≤i ＜j≤s)，R={c1，…，cs}，g.c.d.(c1，…，cs)=1，Z，且|Z| =m(≥1)，其中l(wèi) {1，…，s}.則

證明 若k≤m，取非空k 點子集X?Z;若k ＞m，取非空k 點子集X?Z.構建從X∩Z 出發(fā)且與R中每種長度的有向圈均相交的最短途徑:顯然，X∩Z中的任一點均與長度為c1，…，cl的有向圈相交;記從X∩Z 出發(fā)到Vl+1的最短途徑為Wl+1，易見Wl+1的長度rl+1≤max{0，(n - |Vl+1|)+(1 -min{k，m})};又記從X∩Z 出發(fā)經長度分別為c1，…，cl，cl+1的有向圈再到Vl+2的最短途徑為Wl+1+Wl+2，則Wl+1+Wl+2的長度rl+1+rl+2≤max{0，Σq=l+1，l+2(n- |Vq|)+(1-min{k，m})};以此類推，可找到一條從X∩Z 出發(fā)依次經過長度分別為c1，…，cl，cl+1，…，cs-1的有向圈最終與長度為cs的有向圈相交(即到達點集Vs)的最短途徑Wl+1+…+Ws，其總長度為

根據引理5，對于非負整數i=0，…，r-1，由于

必然存在從點x 到點ys的長為p - i 的途徑，則Rp({x})?Ri({ys}).結合引理6 可得:|Rp(X)|≥

即X∩Z ∩Vl+1∩…∩Vs≠?.此時X∩Z∩Vl+1∩…∩Vs中的任一點x*到其自身且與R 中每種長度的有向圈均相交的最短途徑之長為0，即dR(x*，x*)=0.根據引理5，對于非負整數i=0，…(n-|Vq|)+r-min{k，m}，因為

所以存在從點x*到其自身長為p -i 的途徑. 則由引理6 可得:

根據第k 重下r-指數的定義，綜上可得結論. □

在定理10 中令l=s，且tq=1 (q =1，…，s)，易得關于D CIPn其第k 重下r-指數的上界:

推論5 設D CIPn，且D 中含有若干不同長度的有向圈C1，…，Cs(s≥2)，記其長度分別為c1，…，cs，令R ={c1，…，cs}(c1＞… ＞cs≥1)，g. c. d.(c1，…，cs)=1，且|V(Cq)| =m(≥1).則

進一步地，若D CIPn中的圈結構是由2個不同長度的有向圈所構成的，即在推論5 中令s=2，結合引理4 即得以下結論:

推論6 設D CIPn，且C1，C2是D 中長度分別為c1，c2的有向圈，其中c1＞c2≥1，g.c.d.(c1，c2)=1，且|V(C1)∩V(C2)| =m(≥1).則

下面分別研究n 階微對稱有向圖集MSPn和n階對稱本原有向圖集SPn的第k 重下r-指數的上界.

引理8［4］設D 是一個n 階的本原有向圖且其最短圈長為g，其中n，k，r，g 是滿足1≤g≤k ＜r≤n的正整數.則fr(D，k)≤r-k 且該上界可達.

對應于推論6，若考慮D Pn中的圈結構是由2個不同長度的有向圈所構成，但這2個有向圈無公共部分，即在定理10 中令s =2，t1=t2=1，l =1，結合引理4 可得下述推論:

推論7 設D Pn，且C1，C2是D 中長度分別為c1，c2的有向圈，其中V(C1)∩V(C2)=?，c1≠c2，g.c.d.(c1，c2)=1.則

定理11 設D MSPn.則

證明 因為D MSPn，所以由引理3 可知:D中含有長度分別為2 和c 的有向圈，其中c 是奇數，即g.c.d.(2，c)=1，且D 的最短圈長g≤2.

若k≥2，則k≥2≥g，由引理8 可得:fr(D，k)≤r-k.

若k=1，且D 中長度分別為2 和c 的有向圈有公共點(即m≥1)，則由推論6 可得:fr(D，1)≤r -min{1，m}+(2 -1)(c-1)=r+c-2≤r+n-2.

若k=1，且D 中長度分別為2 和c 的有向圈無公共點，則根據推論7，有fr(D，1)≤(n -c)+(r -min{1，2})+(2 -1)(c-1)≤r+n-2. □

定理12 設D SPn且最短奇圈長為c.則

證明 若k≥2，又因D SPn的最短圈長g≤2，所以k≥2≥g，則根據引理8 可得:fr(D，k)≤r-k.

若k=1，由于D SPn，故D 中每一個點均落于一個長為2 的有向圈上，即D 中長度分別為2 和c的有向圈必有公共點(即m≥1)，則由推論6 可得:

2.3 k 點r-指數

引理9［4］設n，k，r 是滿足1≤k，r≤n 的正整數，D 是一個n 階本原有向圖.則pr(D，k)=0 當且僅當r=1.

根據引理9，本節(jié)均默認假設r ＞1.

定理13［4］設D Pn，且D 中含有長度為cq的若干個有向圈Cq，1，…，Cq，tq，其中tq是正整數，q=1，…，s(s≥2).又設R={c1，…，cs}，c1＞…＞cs≥1，g.c.d.(c1，…，cs)=1，且|V(Cq，j))|=m(≥1).那么，

必然存在從點x 到點z 的長為p - i 的途徑，從而Rp({x})?Ri({z}). 故結合引理6，對于每一個頂點從而根據k 點r-指數的定義可得結論. □

推論8 設D CIPn，且D 中含有若干不同長度的有向圈C1，…，Cs(s≥2)，記其長度分別為c1，…，cs，令R={c1，…，cs}，其中c1＞… ＞cs≥1，g. c. d.(c1，…，cs)=1，且|則

證明 在定理13 中令tq=1 (q =1，…，s)，即得結論. □

上述結論主要刻畫了含交圈結構的本原有向圖其k 點r-指數的上界.接下來將分別探討D MSPn和D SPn的k 點r-指數.

引理10 設D Pn，且C1，C2是D 中長度分別為c1，c2的有向圈，其中V(C1)∩V(C2)=?，c1＞c2≥1，g.c.d.(c1，c2)=1.則

證明 由于D Pn且V(C1)∩V(C2)=?，考慮從C1(不妨設為點y1)到C2(不妨設為點y2)的最短途徑W，易見其長度d≤n+1 -c1-c2(＞0).又因為D 是強連通的(見引理3)，故可取非空k 點子集X?{y1}，且對于點x X 均有長度為dx≤k -1 的途徑可達點y1.故?x X，存在從點x 出發(fā)經點y1最終到達點y2的途徑，其長度為dx+d，即dR(x，y2)≤dx+d≤n +k -c1-c2，其中R ={c1，c2}. 令p=n+r +k +c1c2-2c1-2c2. 由引理4 和引理5，對于非負整數i=0，…，r-1，因為

所以必存在從點x 到點y2的長為p-i 的途徑，從而Rp({x})?Ri({y2}).故對于每一個頂點x X，結合引理6，根據k點r-指數的定義可得結論. □

定理14 設D MSPn，則

證明 由于D MSPn，根據引理3 可知:D 中含有長度分別為2 和c 的有向圈，其中c 是奇數，即g.c.d.(2，c)=1.

若D 中長度分別為2 和c 的有向圈有公共點(即m≥1)，當m=1 時，c≤n-1;當m=2 時，c≤n.根據推論8 和引理4，令s=2，有:pr(D，k)≤(r-1)+max{0，k-m}+(c-1)≤n+r+k-4.

若D 中長度分別為2 和c 的有向圈無公共點，則由引理10 可得:pr(D，k)≤n +r +k +2c -4 -2c=n+r+k-4. □

定理15 設D SPn且最短奇圈長為c. 則pr(D，k)≤r-2 +max{c，k}.

證明 因為D SPn，所以D 中每一個點均落于一個長為2 的有向圈上.根據定理13，令s =2，c1=2，c2=c，則m=c，再結合引理4，有:

2.4 k 點r-同位指數

引理11［4］設n，k，r 是滿足1≤k，r≤n 的正整數，D 是一個n 階本原有向圖，則sr(D，k)=0 當且僅當k=r=1.

根據引理11，本節(jié)均默認假設k+r ＞2.

定理16 設D CIPn，且D 中含有若干不同長度的有向圈C1，…，Cs(s≥2)，記其長度分別為c1，…，cs，令R ={c1，…，cs}，其中c1＞… ＞cs≥1，g. c. d.(c1，…，cs)=1，且則

必然存在從點x 到點z 的長為p - i 的途徑，則Rp({x})?Ri({z}).由引理6 可知:|({z})|≥r，不妨設({z})?{v1，…，vr}.故?x X，均有Rp({x})?({z})?{v1，…，vr}，從而由k 點r-同位指數的定義即得結論. □

定理17 設D SPn且最短奇圈長為c. 則sr(D，k)≤k+r+c-3.

證明 因為D SPn，所以D 中長度分別為2和c 的有向圈必有公共點.結合定理16 和引理4 可得結論. □

［1］柳柏濂. 組合矩陣論［M］. 北京:科學出版社，2005.

［2］柳柏濂，黃宇飛. 組合矩陣的結構指數［M］. 北京:科學出版社，2015.

［3］Brualdi R A，Liu B L. Generalized exponents of primitive directed graphs ［J］. Journal of Graph Theory，1990，14:483 -499.

［4］Huang Y F，Liu B L. Generalized r-exponents of primitive digraphs［J］. Taiwanese Journal of Mathematics，2011，15:1999 -2012.

［5］Liu B L. Generalized exponents of Boolean matrices［J］.Linear Algebra and Its Application，2003，373:169 -182.

［6］Brualdi R A，Shao J Y. Generalized exponents of primitive symmetric digraphs［J］. Discrete Applied Mathematics，1997，74:275 -293.

［7］You L H，Liu B L，Shen J. r-Indecomposable and rnearly decomposable matrices［J］. Linear Algebra and Its Application，2005，407:105 -116.

［8］周積團. r-不可分矩陣的本原指數［J］. 數學的實踐與認識，2003，33(5):96 -98.Zhou J T. Primitive expotents of r-indecomposable matrices［J］. Mathematics in Practice and Theory，2003，33(5):96 -98.

［9］周積團. r-不可分矩陣的本原指數(Ⅱ)［J］. 數學理論與應用，2003，23(2):124 -128.Zhou J T. Primitive expotents of r-indecomposable matrices:Ⅱ［J］. Mathematical Theory and Application，2003，23(2):124 -128.

［10］Liu B L. On fully indecomposable exponent for primitive Boolean matrices with symmetric ones［J］. Linear and Multilinear Algebra，1992，31:131 -138.

［11］Huang Y F，Liu B L. On a conjecture for fully indecomposable exponent and Hall exponent［J］. Linear and Multilinear Algebra，2010，58:699 -710.

［12］陳佘喜. 對稱本原圖的集指數與本原簡單圖的廣義上指數的極圖［J］. 應用數學學報，2005，28(2):243 -252.Chen S X. The set exponent of symmetric primitive digraphs and the extremal graphs of the kth upper generalized exponent for primitive simple graphs［J］. Acta Mathematicae Applicatae Sinica，2005，28(2):243 -252.