張德全,李修清

(桂林航天工業(yè)高等專(zhuān)科學(xué)校計(jì)算機(jī)系,廣西桂林 541004)

圍長(zhǎng)為2的本原無(wú)限布爾方陣類(lèi)的本原指數(shù)集

張德全,李修清

(桂林航天工業(yè)高等專(zhuān)科學(xué)校計(jì)算機(jī)系,廣西桂林 541004)

研究了圍長(zhǎng)為2的無(wú)限布爾方陣的本原性,通過(guò)無(wú)限有向圖D(A)的直徑給出了這類(lèi)矩陣的本原指數(shù)的上確界,最后證明了直徑小于等于d且圍長(zhǎng)為2的本原無(wú)限布爾方陣所構(gòu)成的矩陣類(lèi)的本原指數(shù)集為={2,3,…,3d}.

無(wú)限布爾方陣;本原指數(shù);有向圖;直徑

1 引言

設(shè)β={0,1}是由兩個(gè)元素所組成的布爾代數(shù),具有布爾加法:a+b=max{a,b}和布爾乘法:a·b=min{a,b},這里β={0,1}中約定0＜1.定義在β={0,1}上的具有無(wú)限行和無(wú)限列的矩陣稱(chēng)為無(wú)限布爾方陣.按通常矩陣的加法、數(shù)量乘法和矩陣乘法,我們給出無(wú)限布爾方陣的加法,數(shù)量乘法和乘法的定義.

定義1設(shè)A=(aij),B=(bij)都是無(wú)限布爾方陣,λ∈β,

由無(wú)限布爾方陣的乘法定義,無(wú)限布爾方陣的冪運(yùn)算是有意義的,設(shè)A是一個(gè)無(wú)限布爾方陣,若存在有限的正整數(shù)k,使Ak＞0(即Ak中的每個(gè)元素均為1),則稱(chēng)A是本原無(wú)限布爾方陣(簡(jiǎn)稱(chēng)本原的),使Ak＞0成立的最小正整數(shù)k稱(chēng)為A的本原指數(shù),記作γ(A)=k.設(shè)A=(aij)是一個(gè)無(wú)限布爾方陣,則A可自然地對(duì)應(yīng)一個(gè)無(wú)限階有向圖D(A)=(V,E),其中V={v1,…,vn,…}是頂點(diǎn)集,E是弧集,aij=1當(dāng)且僅當(dāng)有弧(vi,vj)∈E(i,j=1,2,… ),稱(chēng)為A的伴隨有向圖,顯然有向圖D(A)=(V,E)中可以有自環(huán),但沒(méi)有重復(fù)弧.

無(wú)限布爾方陣的本原性可以自然地用圖的語(yǔ)言表述,設(shè)D是一個(gè)無(wú)限階有向圖(圖中允許有自環(huán),但不允許有重復(fù)弧),若存在有限的正整數(shù)k,使得任取圖中兩點(diǎn)i,j,對(duì)于任意一個(gè)≥k的正整數(shù)m,都有點(diǎn)i到點(diǎn)j長(zhǎng)為m的途徑,且圖D中存在兩點(diǎn)u,v,使得點(diǎn)u到點(diǎn)v沒(méi)有長(zhǎng)為k?1的途徑,則稱(chēng)D是本原有向圖,且稱(chēng)k為D的本原指數(shù),記作γ(D)=k.顯然,A是本原無(wú)限布爾方陣的充分必要條件是A的伴隨有向圖D(A)為本原有向圖,且γ(A)=γ(D(A))；因此研究無(wú)限布爾方陣的本原性及其本原指數(shù)集就完全等同于研究相應(yīng)的伴隨有向圖的本原性及其指數(shù)集.

若A=(aij)是一個(gè)無(wú)限布爾方陣,且主對(duì)角線上的元素均為零且至少有一對(duì)非零對(duì)稱(chēng)元,則A對(duì)應(yīng)的伴隨有向圖D(A)=(V,E)是一個(gè)沒(méi)有自環(huán)且最小圈長(zhǎng)為2的無(wú)限階有向圖,我們將一個(gè)圖的最小圈長(zhǎng)稱(chēng)為這個(gè)圖的圍長(zhǎng),這樣主對(duì)角線上的元素均為零且至少有一對(duì)非零對(duì)稱(chēng)元的無(wú)限布爾方陣的伴隨有向圖是一個(gè)圍長(zhǎng)為2的無(wú)限階有向圖,反之一個(gè)圍長(zhǎng)為2的無(wú)限階有向圖的鄰接矩陣也是一個(gè)主對(duì)角線上的元素均為零且至少有一對(duì)非零對(duì)稱(chēng)元的無(wú)限布爾方陣.

通過(guò)D(A)的直徑估計(jì)本原矩陣A的本原指數(shù)是一個(gè)十分有意義的課題,關(guān)于n階本原矩陣的本原指數(shù),文[2]給出了n階對(duì)稱(chēng)本原矩陣本原指數(shù)的上界估計(jì):γ(D)≤2d,文[3]給出了一般的n階本原矩陣的本原指數(shù)上界估計(jì):γ(A)≤d2+1,其中d為D(A)的直徑.但對(duì)于無(wú)限布爾方陣A通過(guò)D(A)的直徑來(lái)估計(jì)A的本原指數(shù)及本原指數(shù)集等問(wèn)題的研究還很不深入,文[1]中研究了含有非零對(duì)角元的無(wú)限布爾方陣,通過(guò)D(A)的直徑給出了其本原指數(shù)的上界估計(jì),并給出了這類(lèi)矩陣的本原指數(shù)集的刻劃,文[4]中研究了對(duì)稱(chēng)無(wú)限布爾方陣,并通過(guò)D(A)的直徑給出了對(duì)稱(chēng)本原無(wú)限布爾方陣的本原指數(shù)集的刻劃.本原指數(shù)研究的另一個(gè)方面是對(duì)各種特殊的本原矩陣類(lèi)的本原指數(shù)以及本原指數(shù)集的研究.本文研究主對(duì)角線上的元素均為零且至少有一對(duì)非零對(duì)稱(chēng)元的一類(lèi)無(wú)限布爾方陣,即伴隨有向圖D(A)的圍長(zhǎng)為2的一類(lèi)無(wú)限布爾方陣,記這類(lèi)方陣的集合為B0,即B0={A|A是無(wú)限布爾方陣,且伴隨有向圖D(A)的圍長(zhǎng)為2};本文研究這類(lèi)無(wú)限階布爾方陣的本原性,通過(guò)伴隨有向圖D(A)的直徑給出本原指數(shù)的上確界,最后給出直徑小于等于d的圍長(zhǎng)為2的本原無(wú)限布爾方陣所構(gòu)成的矩陣類(lèi)的本原指數(shù)集的刻劃.

2 B0中無(wú)限布爾方陣為本原陣的一個(gè)充分必要條件

設(shè)D是一個(gè)無(wú)限階有向圖,i,j是圖中的兩個(gè)頂點(diǎn),k是一個(gè)正整數(shù),若從頂點(diǎn)i到頂點(diǎn)j有長(zhǎng)為m≥k(其中m是大于或等于k的任意一個(gè)正整數(shù))的途徑,但從頂點(diǎn)i到頂點(diǎn)j沒(méi)有長(zhǎng)為k?1的途徑,則稱(chēng)k為頂點(diǎn)i到頂點(diǎn)j的局部本原指數(shù),記作γ(i,j)=k;由以上對(duì)無(wú)限階有向圖D的本原性以及圖D的本原指數(shù)的定義,顯然可得:

命題2設(shè)D是一個(gè)無(wú)限階有向圖,則D是本原的當(dāng)且僅當(dāng)集合{γ(i,j)|i,j∈V(D)}是有限集,且當(dāng)D是本原圖時(shí)有γ(D)=max{γ(i,j)|i,j∈V(D)}.

設(shè)D(A)=(V,E)是無(wú)限布爾方陣A的伴隨有向圖,i,j是圖中的任意兩個(gè)頂點(diǎn)(這兩點(diǎn)可以相同也可以不同),若既有從頂點(diǎn)i到頂點(diǎn)j的長(zhǎng)度有限的途徑,也有從頂點(diǎn)j到頂點(diǎn)i的長(zhǎng)度有限的途徑,則稱(chēng)圖D(A)是強(qiáng)連通圖,稱(chēng)A為不可約無(wú)限布爾方陣(簡(jiǎn)稱(chēng)不可約的);本文用d(i,j)表示頂點(diǎn)i到頂點(diǎn)j的距離,若集合{d(i,j)|i,j∈V(D)}是有界集,則稱(chēng)D(A)具有有限的直徑,并稱(chēng)max{d(i,j)|i,j∈V(D)}為D(A)的直徑,記作d(D(A));為了方便我們將有向圖D(A)具有有限直徑也稱(chēng)為A具有有限的直徑,將D(A)的直徑也稱(chēng)為A的直徑;用RD(A)表示D(A)的所有有限圈(有限圈:即長(zhǎng)度有限的圈)的長(zhǎng)度的集合,即RD(A)={r|r為D(A)中有限圈的長(zhǎng)度}.

下面給出B0中無(wú)限布爾方陣為本原陣的一個(gè)等價(jià)刻劃.首先給出Schur的一個(gè)引理.

引理1[5](Schur)設(shè)k≥2,ri(i=1,2,…,k)是正整數(shù),且gcd(r1,r2,…,rk)=1,則存在僅與r1,r2,…,rk有關(guān)的非負(fù)整數(shù)N(r1,r2,…,rk),當(dāng)n≥N(r1,r2,…,rk)時(shí),方程r1x1+…+rkxk=n有非負(fù)整數(shù)解.

我們把使引理1成立的最小的非負(fù)整數(shù)N(r1,r2,…,rk)記作φ(r1,r2,…,rk),稱(chēng)為r1,r2,…,rk的Frobenius數(shù),特別當(dāng)k=2時(shí)有:φ(r1,r2)=(r1?1)(r2?1).

設(shè)R={r1,r2,…,rk}?RD是無(wú)限階有向圖D中k個(gè)不同的圈長(zhǎng),且gcd(r1,r,…,rk)= 1,D中從頂點(diǎn)i到頂點(diǎn)j且和長(zhǎng)度分別為r1,r2,…,rk的圈都接觸(只要和一個(gè)長(zhǎng)為r的圈有公共點(diǎn)就稱(chēng)為接觸了長(zhǎng)為r的圈)的最短途徑長(zhǎng)記為dR(i,j),稱(chēng)為從頂點(diǎn)i到頂點(diǎn)j的相應(yīng)于R的廣義相對(duì)距離,記φR為r1,r2,…,rk的Frobenius數(shù),即φR=φ(r1,r2,…,rk),則顯然頂點(diǎn)i到頂點(diǎn)j有長(zhǎng)為m的途徑,其中m大于等于dR(i,j)+φR的任意一個(gè)正整數(shù),從而由局部本原指數(shù)的定義有:γ(i,j)≤dR(i,j)+φR.即

引理2設(shè)R={r1,r2,…,rk}?RD是無(wú)限階有向圖D中k個(gè)不同的圈長(zhǎng),且gcd(r1,r2, …,rk)=1,任取D中i,j兩點(diǎn),則頂點(diǎn)i到頂點(diǎn)j有長(zhǎng)為m≥dR(i,j)+φR的途徑,從而有γ(i,j)≤dR(i,j)+φR.

文[1]中給出了無(wú)限布爾方陣為本原陣的一個(gè)等價(jià)刻劃.

定理1[1]設(shè)A是一個(gè)無(wú)限布爾方陣,D(A)是A的伴隨有向圖,RD={D(A)中所有有限圈的長(zhǎng)度},則A是本原陣的充分必要條件為:

(i)D(A)是強(qiáng)連通有向圖;

(ii)D(A)有有限直徑,存在RD中的有限元素r1,r2,…,rk且滿(mǎn)足gcd(r1,r2,…,rk)=1.

由定理1,我們易給出B0中的無(wú)限布爾方陣為本原陣的一個(gè)充分必要條件.

定理2設(shè)A∈B0,D(A)是A的伴隨有向圖,則A是本原陣的一個(gè)充分必要條件為:

(i)D(A)是強(qiáng)連通有向圖;

(ii)D(A)具有有限的直徑,且D(A)含有奇圈.

3 PB0中直徑為d的無(wú)限布爾方陣的本原指數(shù)的上確界

情形1若y1和y2中至少有一個(gè)為0,不妨設(shè)y1=0,則有x1+k0≡2k0?y1≡0(mod 2),即x1+k0＜2k0且為偶數(shù),由上述討論知在圖D(A)中存在一條u0點(diǎn)到u2點(diǎn)的長(zhǎng)度為x1+k0的偶途徑,矛盾.

情形2若y1和y2均為1,則x1+x2≡2k0?(y1+y2)≡0(mod 2),即x1+x2是一個(gè)小于2k0的偶數(shù),則同樣u0點(diǎn)到u2點(diǎn)存在一條長(zhǎng)度為x1+x2的偶途徑,矛盾.

于是我們就證明了假設(shè)是錯(cuò)誤的,故定理結(jié)論成立.

定理3設(shè)A∈PB0,且D(A)的直徑為d,則γ(A)≤3d,并且上界是可以達(dá)到的.

證明因?yàn)锳∈PB0,由定理2知D(A)具有有限的直徑,設(shè)D(A)的直徑為d,由A∈PB0知,D(A)是一個(gè)沒(méi)有自環(huán)且至少含有一個(gè)2圈的本原圖,設(shè)D(A)的一個(gè)2圈為Γ2,且設(shè)Γ2上的兩個(gè)點(diǎn)為i,j,則i,j點(diǎn)在圖D(A2)中均有自環(huán),由引理3知D(A2)的直徑≤d,于是圖D(A2)中i點(diǎn)或j點(diǎn)到圖D(A2)中的任何一點(diǎn)都有長(zhǎng)度恰為d的途徑,從而在圖D(A)中i點(diǎn)和j點(diǎn)到圖D(A)中的任何一點(diǎn)都分別有長(zhǎng)度恰為2d的途徑;在圖D(A)中任取兩點(diǎn)u,v,由于D(A)的直徑為d,易知從u點(diǎn)用長(zhǎng)度恰為m≥d(m是不小于d的任意一個(gè)正整數(shù))的途徑可以到達(dá)圖D(A)中的i點(diǎn)或j點(diǎn),而i點(diǎn)或j點(diǎn)又可用長(zhǎng)度恰為2d的途徑到達(dá)圖D(A)中的v點(diǎn),于是對(duì)于圖D(A)的任意兩點(diǎn)u,v,u點(diǎn)到v點(diǎn)都存在長(zhǎng)度恰為m+2d(m≥d是任意一個(gè)正整數(shù))的途徑,于是由局部本原指數(shù)的定義得:γ(u,v)≤3d,注意到u,v兩點(diǎn)的任意性得γ(A)≤3d;上界的可達(dá)性證明由下一節(jié)給出.

4 無(wú)限布爾方陣類(lèi)PB0的本原指數(shù)集的刻劃

定理4={2,3,…,3d}(d≥3).

本文我們使用下列記號(hào):設(shè)D是一個(gè)無(wú)限階有向圖,用(i,j)表示頂點(diǎn)i到頂點(diǎn)j的一條弧,[i,j]表示頂點(diǎn)i到頂點(diǎn)j之間的雙向連通邊,即一個(gè)2圈.

定理5{2,3,…,d+1,d+2}?(d≥3).

證明(1)設(shè)3≤k≤d(d≥3),考慮下列無(wú)限階有向圖D=D(V,E),其中V= {1,2,…,d,…},E={(1,2),(2,3),…,(k?2,k?1),[k?1,k];(k,1),(k,2),…,(k,k?2); [k,k+1],[k,k+2],[k,k+3],…}.易知,圖D=D(V,E)強(qiáng)連通,沒(méi)有自環(huán),有2圈和3圈,且直徑≤d,即D=D(V,E)的鄰接無(wú)限布爾方陣A∈P;取圖D=D(V,E)中圈長(zhǎng)為2和3的集合R={2,3},則由引理1知,Frobenius數(shù)φR=2,考慮圖中1點(diǎn)和k+1點(diǎn),顯然dR(1,k+1)=k,于是由引理2知γ(1,k+1)≤k+2,但1點(diǎn)到k+1點(diǎn)顯然沒(méi)有長(zhǎng)為k+1的途徑,故有γ(1,k+1)=k+2,另一方面易知dR(i,j)≤k(i,j=1,2,3,…),于是有γ(i,j)≤k+2(i,j=1,2,3,…),故有γ(D)=k+2(3≤k≤d),即{5,6,…,d+1,d+2}?;

(2)考慮主對(duì)角線上的元素均為零,其余元素均為1的無(wú)限布爾方陣A,易知γ(A)= 2即2∈;

(3)考慮下列無(wú)限有向圖D=D(V,E),其中E={[1,2],(3,1);[i,j](i/=j且i,j= 2,3,…)},V={1,2,…,d,…}.顯然D=D(V,E)強(qiáng)連通,沒(méi)有自環(huán),有2圈和3圈,且直徑為2,則D所對(duì)應(yīng)的鄰接無(wú)限布爾方陣A∈P;易驗(yàn)證A和A2都不是全1矩陣,而A3是全1矩陣,于是γ(A)=3即γ(D)=3,所以3∈

(4)考慮下列無(wú)限有向圖D=D(V,E),其中V={1,2,…,d,…},E={[1,2];[2,3],[2,4],[2,5],…;[3,4]}.顯然圖D=D(V,E)強(qiáng)連通,沒(méi)有自環(huán),有2圈和3圈,且直徑為2,即所對(duì)應(yīng)的無(wú)限布爾方陣A∈P;取圖D=D(V,E)中圈長(zhǎng)的集合R={2,3},考慮圖中1點(diǎn)和5點(diǎn),顯然dR(1,5)=2,Frobenius數(shù)φR(2,3)=2,于是γ(1,5)≤4,但顯然1點(diǎn)到5點(diǎn)沒(méi)有長(zhǎng)為3的途徑,故有γ(1,5)=4,另一方面顯然dR(i,j)≤2(i,j=1,2,3,…),于是有γ(i,j)≤4(i,j=1,2,3,…),故γ(D)=4,即4∈.

定理6{d+3,d+4,…,2d}?(d≥3).

證明設(shè)3≤k≤d(d≥3),考慮下列無(wú)限階有向圖D=D(V,E),其中V= {1,2,…,d,…},E={[1,2],[2,3],[3,4],…;[k?2,k?1],[k?1,k];(k,k+1),(k+1,k+2),…,(d?1,d),(d,d+1);(d+1,1);(3,1),(4,2),…,(k,k?2);[2,d+2],[2,d+3],[2,d+4],…}.易知,圖D= D(V,E)強(qiáng)連通,沒(méi)有自環(huán),有2圈和3圈,且直徑=d,即D=D(V,E)的鄰接無(wú)限布爾方陣A∈P;取圖D=D(V,E)中圈長(zhǎng)為2和3的集合R={2,3},則Frobenius數(shù)φR=2,考慮圖中k+1點(diǎn)和d+1點(diǎn),顯然dR(k+1,d+1)=(d?k)+(d+1),由引理2知,γ(k+1,d+1)≤2d?k+3,顯然k+1點(diǎn)到d+1點(diǎn)沒(méi)有長(zhǎng)為2d?k+2的途徑,故有γ(k+1,d+1)=2d?k+3;另一方面顯然dR(i,j)≤2d?k+1(i,j=1,2,3,…),于是有γ(i,j)≤2d?k+3(i,j=1,2,3,…),故有γ(D)=2d?k+3(3≤k≤d),即{d+3,d+4,…,2d}?,(d≥3).

定理7當(dāng)d為奇數(shù)時(shí),{2d+1,2d+2,…,3d}?,(d≥3).

證明(1)設(shè)4≤k≤d+2(d≥3),考慮下列無(wú)限階有向圖D=D(V,E),其中V= {1,2,…,d,…},E={(1,2),[2,3],(3,4);[4,5],[5,6],…,[k?2,k?1];(k?1,k),(k,k+1), (k+1,k+2),…,(d,d+1),(d+1,d+2);(1,3),(2,4);(d+2,1);[3,3+d],[3,d+4],[3,d+ 5],…;(d+3,1),(d+4,1),(d+5,1),…}.易知,圖D=D(V,E)強(qiáng)連通,沒(méi)有自環(huán),有2圈和只有長(zhǎng)為d+2的奇圈,且直徑=d,即D=D(V,E)的鄰接方陣A∈P;取圖D=D(V,E)中圈長(zhǎng)為2和d+2的集合R={2,d+2},則由引理2知,Frobenius數(shù)φR=d+1,考慮圖中k點(diǎn)和d+2點(diǎn),顯然dR(k,d+2)=(d+2?k)+(d+1),于是由引理2知γ(k,d+2)≤3d?k+4,易知k點(diǎn)到d+2點(diǎn)沒(méi)有長(zhǎng)為3d?k+3的途徑,故有γ(k,d+2)=3d?k+4,另一方面易證dR(i,j)≤2d?k+3(i,j=1,2,3,…),于是有γ(i,j)≤3d?k+4(i,j=1,2,3,…),故有γ(D)=3d?k+4(4≤k≤d+2),即{2d+2,2d+3,…,3d}?,(d≥3);

(2)考慮下列無(wú)限階有向圖D=D(V,E),其中V={1,2,…,d,…},E={[1,2];(2,3), (3,4),…,(d?1,d),(d,d+1);(d+1,1);[2,d+2],[2,d+3],[2,d+4],…;[1,d+2],[1,d+3],[1,d+ 4],…}.易知,圖D=D(V,E)強(qiáng)連通,沒(méi)有自環(huán),有2圈和3圈,且直徑=d,即D=D(V,E)的鄰接無(wú)限布爾方陣A∈P;取圖D=D(V,E)中圈長(zhǎng)的集合R={2,3},則Frobenius數(shù)φR= 2,考慮圖中3點(diǎn)和d+1點(diǎn),顯然dR(3,d+1)=(d?2)+(d+1),于是γ(3,d+1)≤2d+1,且易知3點(diǎn)到d+1點(diǎn)沒(méi)有長(zhǎng)為2d的途徑,故有γ(3,d+1)=2d+1,另一方面易證dR(i,j)≤2d?1(i,j=1,2,3,…),于是有γ(i,j)≤2d+1(i,j=1,2,3,…),故有γ(D)=2d+1,即2d+1∈(d≥3);綜合(1),(2)就證明了,當(dāng)d為奇數(shù)時(shí){2d+1,2d+2,…,3d}?,(d≥3且為奇數(shù)).

定理8當(dāng)d為偶數(shù)時(shí),{2d+1,2d+2,…,3d}?,(d≥3).

證明(1)4≤k≤d+2(d≥3),考慮下列無(wú)限階有向圖D=D(V,E),其中V= {1,2,…,d,…},E={(1,2),[2,3],(3,4);[4,5],[5,6],…,[k?2,k?1];(k?1,k),(k,k+1),…,(d, d+1),(d+1,d+2);(1,3),(2,4);(d+2,1);[3,d+3],[3,d+4],[3,d+5],…;(d+3,1),(d+ 4,1),(d+5,1),…}.易知,圖D=D(V,E)強(qiáng)連通,沒(méi)有自環(huán),有2圈,且只有長(zhǎng)為d+1的奇圈且直徑=d,即D=D(V,E)的鄰接方陣A∈P;取圖D=D(V,E)中圈長(zhǎng)為2和d+1的集合R={2,d+1},則Frobenius數(shù)φR=d,考慮圖中k點(diǎn)和d+2點(diǎn),顯然dR(k,d+2)=(d+2?k)+(d+1),于是γ(k,d+2)≤3d?k+3,且易知k點(diǎn)到d+2點(diǎn)沒(méi)有長(zhǎng)為3d?k+2的途徑,故有γ(k,d+2)=3d?k+3,另一方面易證dR(i,j)≤3d?k+3(i,j= 1,2,3,…),于是有γ(i,j)≤3d?k+3(i,j=1,2,3,…),故有γ(D)=3d?k+3(4≤k≤d+2),即{2d+1,2d+2,…,3d?1}?,(d≥3).

(2)考慮下列無(wú)限階有向圖D=D(V,E),其中V={1,2,…,d,…},E={[1,2];(2,3), (3,4),…,(d?1,d),(d,d+1),(d+1,d+2);(1,3);(d+2,1),(d+2,2);[2,d+3],[2,d+4],[2,d+ 5],…;(d+3,3),(d+4,3),…;(d+2,d+3),(d+2,d+4),(d+2,d+5),…}.易知,圖D= D(V,E)強(qiáng)連通,沒(méi)有自環(huán),有2圈,且只有長(zhǎng)為d+1的奇圈,且直徑=d,即D=D(V,E)的鄰接方陣A∈P;取圖D=D(V,E)中圈長(zhǎng)的集合R={2,d+1},則Frobenius數(shù)φR=d,考慮圖D=D(V,E)中3點(diǎn)和d+2點(diǎn),顯然dR(3,d+2)=(d?1)+(d+1),于是γ(3,d+2)≤3d,且易知3點(diǎn)到d+2點(diǎn)沒(méi)有長(zhǎng)為3d?1的途徑,故有γ(3,d+2)=3d,另一方面易證dR(i,j)≤2d(i,j=1,2,3,…),于是有γ(i,j)≤3d(i,j=1,2,3,…),故有γ(D)=3d,即3d?,(d≥3).(且d為偶數(shù));

綜合(1)、(2)就證明了,當(dāng)d為偶數(shù)時(shí),{2d+1,2d+2,…,3d}?(d≥3且d為偶數(shù)).綜合定理5到定理8我們就證明了定理4的結(jié)論成立.

[1]李修清,王敏.一類(lèi)本原無(wú)限布爾方陣的本原指數(shù)集的刻劃[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2007,37(1):100-103.

[2]Delorme C,Sole P.Diameter,covering index,covering radius and eigenvalues[J].Europ.J.Combinatorics, 1991,12:93-108.

[3]Jian Shen.Proof of a conjecture about the exponent of primitive matrices[J].Linear Algebra Appl.,1995, 216:185-203.

[4]李修清,王敏.對(duì)稱(chēng)無(wú)限布爾方陣的本原指數(shù)集的刻劃[J].系統(tǒng)科學(xué)與數(shù)學(xué),2008,28(12):1478-1485

[5]柳柏濂.組合矩陣論[M].北京:科學(xué)出版社,1996.

On primitive exponent set for the class of primitive infinite Boolean matrices with girth 2

ZHANG De-quan,LI Xiu-qing
(Department of Computer Science,Guilin College of Aerospace Technology,Guilin541004,China)

This paper studies the primitiveness of infinite Boolean matrices with girth 2.And it offers the least upper bound of the primitive exponent through the diameter of the infinite digraph D(A).In the end we completely determine the primitive exponent set of the matrices which are class of primitive infinite Boolean matrices with girth 2 and whose diameters are not more than d is={2,3,…,3d}.

infinite Boolean matrices,primitive exponent,digraph,diameter

O157.5

A

1008-5513(2009)03-0464-06

2008-12-30.

廣西區(qū)教育廳科研項(xiàng)目(桂教科研[2006]26號(hào)).

張德全(1959-),副教授,研究方向：組合數(shù)學(xué).

2000MSC:05C50