若干本原有向圖類其廣義本原r-指數(shù)的界

黃宇飛 ，柳柏濂

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

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

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

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

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

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

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

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

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

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

1 不可分矩陣的廣義本原r-指數(shù)

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

另外，對(duì)于整數(shù)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 點(diǎn)r-指數(shù)和第k 重上r-指數(shù)的上界.

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

1.1 k 點(diǎn)r-指數(shù)

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

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

其中p=「(r-1)/w?. 結(jié)合k 點(diǎn)r-指數(shù)的定義即得結(jié)論.

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

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

設(shè)D1是頂點(diǎn)集為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 設(shè)D Fn(或D NDn)，則pr(D，k)≤r-1，此上界可達(dá)且D1是極圖之一.

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

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

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

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

1.2 第k 重上r-指數(shù)

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

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

定理3 設(shè)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)點(diǎn)子集X ?V(D)都有|R1(X)|≥min{n，k +w}，從而對(duì)于?X?V(D)且|X| =k，有其中p =「(r -k)/w?.根據(jù)第k 重上r-指數(shù)的定義可得:Fr(D，k)≤p=「(r-k)/w?.

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

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

設(shè)Dk(1≤k≤n)表示頂點(diǎ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).易見(jiàn)，DkNDn?Fn?Pn(1≤k≤n).

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

關(guān)于本原有向圖Dk的第k 重上r-指數(shù)有如下的結(jié)論:

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

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

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

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

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

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

2 含特殊圈結(jié)構(gòu)的本原有向圖的廣義本原r-指數(shù)

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

引理3［1］D Pn當(dāng)且僅當(dāng)D 是一個(gè)n 階的強(qiáng)連通有向圖，且D 中所有不同圈長(zhǎng)的最大公因數(shù)等于1.

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

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

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

引理6［10］設(shè)D Pn，且X 是一個(gè)非空點(diǎn)子集，即?≠X?V(D).則對(duì)于任意非負(fù)整數(shù)t，都有

接下來(lái)給出幾類含特殊圈結(jié)構(gòu)的本原有向圖的定義.

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

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

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

2.1 第k 重上r-指數(shù)

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

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

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

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

所以存在從點(diǎn)x*到其自身長(zhǎng)為p -i 的途徑. 結(jié)合引理6 可得:

綜上，結(jié)合第k 重上r-指數(shù)的定義可得結(jié)論. □

定理5 刻畫了含多圈結(jié)構(gòu)的本原有向圖其第k重上r-指數(shù)的上界.采用類似的方法，接下來(lái)考慮含交圈結(jié)構(gòu)的本原有向圖.

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

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

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

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

根據(jù)第k 重上r-指數(shù)的定義，綜上可得結(jié)論. □

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

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

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

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

下面進(jìn)一步特殊化本原有向圖的圈結(jié)構(gòu)，分別研究n 階微對(duì)稱有向圖集MSPn和n 階對(duì)稱本原有向圖集SPn的第k 重上r-指數(shù).

定理7 設(shè)D MSPn，則

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

定理8 設(shè)D SPn，則

證明 因?yàn)镈 SPn，所以D 中每一個(gè)點(diǎn)均落于一個(gè)長(zhǎng)為2 的有向圈上，又結(jié)合引理3 可知:D 中必含一個(gè)長(zhǎng)為奇數(shù)c 的有向圈C.

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

情形1:n-c -k ＜0.顯然，|X∩V(C)|≥c +k-n≥1，即X∩V(C)≠?.注意到:從X∩V(C)中的任一點(diǎn)x 出發(fā)到其自身與R 中每種長(zhǎng)度的有向圈均相交的最短途徑之長(zhǎng)為0，即dR(x，x)=0.根據(jù)引理5，對(duì)于非負(fù)整數(shù)i =0，…，(n - c)+ (r - k)，由于p-i≥c-1 =dR(x，x)+φ(R)，故有從點(diǎn)x 到其自身長(zhǎng)為p-i 的途徑.從而結(jié)合引理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(不妨設(shè)為點(diǎn)x X)出發(fā)到C(不妨設(shè)為點(diǎn)y C)的最短途徑為W，則W 的長(zhǎng)度d≤n+1 -k-c(＞0).由于W 是從點(diǎn)x X 到點(diǎn)y C 且與R 中每種長(zhǎng)度的有向圈均相交的最短途徑，故dR(x，y)≤(n -c)+(1 -k). 根據(jù)引理5，對(duì)于非負(fù)整數(shù)i=0，…，r-1，由于

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

根據(jù)第k 重上r-指數(shù)的定義可得結(jié)論. □

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

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

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

2.2 第k 重下r-指數(shù)

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

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

定理10 設(shè)D Pn，且D 中含有長(zhǎng)度為cq的若干個(gè)有向圈Cq，1，…，Cq，tq，記Vq=V(Cq，j)，其中cq，tq均是正整數(shù)，q =1，…，s(s≥2). 又設(shè)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 點(diǎn)子集X?Z;若k ＞m，取非空k 點(diǎn)子集X?Z.構(gòu)建從X∩Z 出發(fā)且與R中每種長(zhǎng)度的有向圈均相交的最短途徑:顯然，X∩Z中的任一點(diǎn)均與長(zhǎng)度為c1，…，cl的有向圈相交;記從X∩Z 出發(fā)到Vl+1的最短途徑為Wl+1，易見(jiàn)Wl+1的長(zhǎng)度rl+1≤max{0，(n - |Vl+1|)+(1 -min{k，m})};又記從X∩Z 出發(fā)經(jīng)長(zhǎng)度分別為c1，…，cl，cl+1的有向圈再到Vl+2的最短途徑為Wl+1+Wl+2，則Wl+1+Wl+2的長(zhǎng)度rl+1+rl+2≤max{0，Σq=l+1，l+2(n- |Vq|)+(1-min{k，m})};以此類推，可找到一條從X∩Z 出發(fā)依次經(jīng)過(guò)長(zhǎng)度分別為c1，…，cl，cl+1，…，cs-1的有向圈最終與長(zhǎng)度為cs的有向圈相交(即到達(dá)點(diǎn)集Vs)的最短途徑Wl+1+…+Ws，其總長(zhǎng)度為

根據(jù)引理5，對(duì)于非負(fù)整數(shù)i=0，…，r-1，由于

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

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

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

根據(jù)第k 重下r-指數(shù)的定義，綜上可得結(jié)論. □

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

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

進(jìn)一步地，若D CIPn中的圈結(jié)構(gòu)是由2個(gè)不同長(zhǎng)度的有向圈所構(gòu)成的，即在推論5 中令s=2，結(jié)合引理4 即得以下結(jié)論:

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

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

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

對(duì)應(yīng)于推論6，若考慮D Pn中的圈結(jié)構(gòu)是由2個(gè)不同長(zhǎng)度的有向圈所構(gòu)成，但這2個(gè)有向圈無(wú)公共部分，即在定理10 中令s =2，t1=t2=1，l =1，結(jié)合引理4 可得下述推論:

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

定理11 設(shè)D MSPn.則

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

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

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

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

定理12 設(shè)D SPn且最短奇圈長(zhǎng)為c.則

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

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

2.3 k 點(diǎn)r-指數(shù)

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

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

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

必然存在從點(diǎn)x 到點(diǎn)z 的長(zhǎng)為p - i 的途徑，從而Rp({x})?Ri({z}). 故結(jié)合引理6，對(duì)于每一個(gè)頂點(diǎn)從而根據(jù)k 點(diǎn)r-指數(shù)的定義可得結(jié)論. □

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

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

上述結(jié)論主要刻畫了含交圈結(jié)構(gòu)的本原有向圖其k 點(diǎn)r-指數(shù)的上界.接下來(lái)將分別探討D MSPn和D SPn的k 點(diǎn)r-指數(shù).

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

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

所以必存在從點(diǎn)x 到點(diǎn)y2的長(zhǎng)為p-i 的途徑，從而Rp({x})?Ri({y2}).故對(duì)于每一個(gè)頂點(diǎn)x X，結(jié)合引理6，根據(jù)k點(diǎn)r-指數(shù)的定義可得結(jié)論. □

定理14 設(shè)D MSPn，則

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

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

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

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

證明 因?yàn)镈 SPn，所以D 中每一個(gè)點(diǎn)均落于一個(gè)長(zhǎng)為2 的有向圈上.根據(jù)定理13，令s =2，c1=2，c2=c，則m=c，再結(jié)合引理4，有:

2.4 k 點(diǎn)r-同位指數(shù)

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

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

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

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

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

證明 因?yàn)镈 SPn，所以D 中長(zhǎng)度分別為2和c 的有向圈必有公共點(diǎn).結(jié)合定理16 和引理4 可得結(jié)論. □

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

［2］柳柏濂，黃宇飛. 組合矩陣的結(jié)構(gòu)指數(shù)［M］. 北京:科學(xué)出版社，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］周積團(tuán). r-不可分矩陣的本原指數(shù)［J］. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，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］周積團(tuán). r-不可分矩陣的本原指數(shù)(Ⅱ)［J］. 數(shù)學(xué)理論與應(yīng)用，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］陳佘喜. 對(duì)稱本原圖的集指數(shù)與本原簡(jiǎn)單圖的廣義上指數(shù)的極圖［J］. 應(yīng)用數(shù)學(xué)學(xué)報(bào)，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.