一類含有兩個(n-1)-圈的三色有向圖本原指數(shù)

羅美金, 盧鈺松, 韋玉程

(河池學(xué)院 數(shù)理學(xué)院, 廣西 宜州 546300)

1 預(yù)備知識

若D是包含紅弧、黃弧和藍弧的有向圖，則稱D是一個三色有向圖.若D中每一對頂點(i,j)都存在從i到j(luò)的途徑，則稱D是強連通的.給定D中的一條途徑ω，若用r(ω)，y(ω)和b(ω)分別表示ω中紅弧、黃弧和藍弧的數(shù)目，稱ω為一條(r(ω),y(ω),b(ω))-途徑，則ω這條途徑的分解是向量(r(ω),y(ω),b(ω))或(r(ω),y(ω),b(ω))T[1].

一個三色有向圖D是本原的，當(dāng)且僅當(dāng)存在非負整數(shù)h，k和v，且h+k+v>0，使得D中的每一對頂點(i,j)都存在從i到j(luò)的(h,k,v)-途徑，h+k+v的最小值即為三色有向圖D的本原指數(shù)，記為exp(D)[1].

設(shè)C={γ1,γ2,…,γl}是D的圈集合，定義D的圈矩陣M是一個3×l矩陣，它的第i列是γi的分解.M的content(記為content(M))定義為0如果M的秩小于3，否則定義為M的所有非零3階主子式的最大公因數(shù)[2].

引理1[2]一個至少包含一條紅弧、一條黃弧和一條藍弧的三色有向圖D是本原的，當(dāng)且僅當(dāng)D是強連通的，且content(M)=1.

非負本原矩陣簇指數(shù)的研究是矩陣組合理論中一個嶄新的研究課題，是非負本原矩陣對指數(shù)問題的深化，更是單個非負矩陣概念的推廣，是國內(nèi)外研究的熱點問題.當(dāng)前，關(guān)于傳統(tǒng)單個非負本原矩陣、本原矩陣對的指數(shù)已經(jīng)取得了不少成果[1,3-4]，而對于具有代表性的非負本原矩陣簇指數(shù)的研究因情況復(fù)雜，可能性多，計算量大等因素造成大部分問題都未得到解決，成果甚少[2,5-9].

本文將非負矩陣簇與其伴隨有向圖建立關(guān)系，在文獻[6]的基礎(chǔ)上，進一步討論至少包含一條紅弧、一條黃弧和一條藍弧的三色有向圖D，給出了a=c時的本原情況，并借助maple計算指數(shù)上界及刻畫極圖.該三色有向圖D的未著色圖如圖1所示.

圖1 未著色有向圖DFig.1 Uncolored digraph of D

由圖1可知，D中含有n(n≥3)個頂點，一個n-圈和兩個(n-1)-圈，且三圈有一條n-3長的公共弧3→4→…→n.不妨設(shè)D的圈矩陣為

(1)

式中:a，b，c，d，e，f都為非負整數(shù)，且a，b，c，d，e，f滿足關(guān)系式：

(2a)

(2b)

2 a=c時的本原條件

定理1若a=c，b=d-1時，三色有向圖D是本原的，當(dāng)且僅當(dāng)x=0，y=±1，c=1.

證明由圖1可知D是強連通的.不防設(shè)e=c+x,f=d+y，代入式(2a)和式(2b)則有-2≤x≤2，-2≤y≤2，-2≤x+y≤2.若a=c，b=d-1時，結(jié)合式(1)有c+d≤n-1，det(M)=x(-n-d+1)+cy.由引理1可得，D是本原的當(dāng)且僅當(dāng)content(M)=1，即x(-n-d+1)+cy=±1.分以下5種情況討論D在a=c，b=d-1時的本原情況：

1) 若D是本原的，且x=-2，則c≥2，0≤y≤2，-2(-n-d+1)+cy=±1.容易驗證，y=0或2時，-2(-n-d+1)+cy為偶數(shù)；y=1時，-2(-n-d+1)+c=2n+2d+c-2>1；顯然-2(-n-d+1)+cy≠±1.故x=-2時，D是不本原的.

2) 若D是本原的，且x=-1，則c≥1，-1≤y≤2，-(-n-d+1)+cy=±1.容易驗證，y=-1或0或1或2時，-(-n-d+1)+cy=n+d-1+cy>1；顯然-(-n-d+1)+cy≠±1.故x=-1時，D是不本原的.

3) 若D是本原的，且x=0，則c≥0，-2≤y≤2，cy=±1.容易驗證，y=-2或0或2時，cy為偶數(shù)；y=±1時，則必有c=1成立.故x=0，y=±1，c=1時，D是本原的.

4) 若D是本原的，且x=1，則c≥0，-2≤y≤1，-n-d+1+cy=±1.容易驗證，y=-2或-1或0或1 時，-n-d+1+cy<-1；顯然-n-d+1+cy≠±1.故x=1時，D是不本原的.

5) 若D是本原的，且x=2，則c≥0，-2≤y≤0，2(-n-d+1)+cy=±1.容易驗證，y=-2或-1或0時，2(-n-d+1)+cy<-1；顯然2(-n-d+1)+cy≠±1.故x=2時，D是不本原的.

綜上所述，若a=c，b=d-1時，三色有向圖D是本原的，當(dāng)且僅當(dāng)x=0，y=±1，c=1.定理得證.

類似定理1的證明，可得定理2～定理4.

定理2若a=c，b=d時，三色有向圖D是本原的，當(dāng)且僅當(dāng)滿足以下條件之一:

1)x=y=-1，d-c=±1；

2)x=-1，y=0，d=1；

3)x=-1，y=c=1，d=0；

4)x=0，y=±1，c=1；

5)x=d=1，y=-1，c=0；

6)x=d=1，y=0；

7)x=y=1，c-d=±1.

定理3若a=c，b=d+1時，三色有向圖D是本原的，當(dāng)且僅當(dāng)滿足以下條件之一:

1)x=-1，y=1，c+d=n-2；

2)x=-1，y=0，c=1，d=n-2；

3)x=-1，y=2，-n+d+2c+1=±1；

4)x=0，y=±1，c=1；

5)x=1，y=-2，n-d-2c-1=±1；

6)x=1，y=-1，c+d=n-2；

7)x=1，y=0，c=0，d=n-2.

定理4若a=c，b=d+2時，三色有向圖D是本原的，當(dāng)且僅當(dāng)x=0，y=±1，c=1.

3 指數(shù)上界

以下對定理1～定理4中的所有本原情況，分別討論找到對應(yīng)的指數(shù)上界，將所得指數(shù)上界進行比較，找到所有本原情況下，a=c，b=d，x=y=1，c-d=±1時，D的本原指數(shù)最大.以下只給出a=c，b=d，x=y=1，c-d=±1時的指數(shù)上界證明過程，其他本原情況不再贅述.

定理5若三色有向圖D是本原的，且a=c，b=d，x=y=1，c-d=±1，則

證明對任意的頂點(i,j)，記pij是從i到j(luò)的最短路r(pij)=s，y(pij)=t，b(pij)=w.分a=c，b=d，x=y=1，c-d=1和a=c，b=d，x=y=1，c-d=-1兩種情況討論D的本原指數(shù)上界.

1) 當(dāng)a=c，b=d，x=y=1，c-d=1時

只需證明對D的任意一對頂點y都有一((d+1)(nd+2n-2d-4)+(d+1)(nd+d2+2n+d-2)+(d+2)(d2+2d+1)，d(nd+2n-2d-4)+d(nd+d2+2n+d-2)+(d+1)(d2+2d+1)，(n-2d-1)(nd+2n-2d-4)+(n-2d-2)(nd+d2+2n+d-2)+(n-2d-4)(d2+2d+1))-途徑.取ρ1=nd+2n-2d-4+(n-2)s-nt-w，ρ2=nd+d2+2n+d-2-(n+d-1)s+(n+d+2)t+w，ρ3=d2+2d+1+ds-(d+1)t.因此，從頂點i出發(fā)，沿pij到頂點j，轉(zhuǎn)n-圈ρ1次，轉(zhuǎn)其中一個(n-1)-圈ρ2次，轉(zhuǎn)另一個(n-1)-圈ρ3次的途徑有分解

此時，結(jié)合圖1，可得0≤s≤d+2，0≤t≤d+1，0≤w≤n-2d-1.當(dāng)s=d+2時，t≥0，w≥0；當(dāng)t=d，w=n-2d-1或t=d，w=n-2d-2或t=d+1，w=n-2d-4時，s≥0;當(dāng)w=n-2d-2或w=n-2d-1時，pij至少轉(zhuǎn)其中一個(n-1)-圈1次.容易驗證，ρ1≥0，ρ2≥0，ρ3≥0.所以，

exp(D)≤(d+1)(nd+2n-2d-4)+(d+1)×

(nd+d2+2n+d-2)+(d+2)(d2+

2d+1)+d(nd+2n-2d-4)+d(nd+d2+2n+d-2)+(d+1)(d2+2d+1)+

(n-2d-1)(nd+2n-2d-4)+(n-

2d-2)(nd+d2+2n+d-2)+(n-

2d-4)(d2+2d+1)=n(nd+2n-2d-4)+(n-1)(nd+d2+2n+d-2)+

(n-1)(d2+2d+1)

顯然，exp(D)是關(guān)于d的函數(shù)，利用maple對上式合并計算得

exp(D)≤2dn2+4n2+2d2n-2d2-7n-3d+1

對exp(D)關(guān)于變量d求導(dǎo)得

exp′(D)=2n2+4nd-4d-3

2) 當(dāng)a=c，b=d，x=y=1，c-d=-1時

只需證明對D的任意一對頂點(i,j)都有一((d-1)(nd-2d+n-2)+(d-1)(nd+d2+n-d-2)+d3，d(nd-2d+n-2)+d(nd+d2+n-d-2)+(d+1)d2，(n-2d+1)(nd-2d+n-2)+(n-2d)(nd+d2+n-d-2)+(n-2d-2)d2)-途徑.取ρ1=nd-2d+n-2-ns+(n-2)t-w，ρ2=nd+d2+n-d-2+(n+d+1)s-(n+d-2)t+w，ρ3=d2-ds+(d-1)t.因此，從頂點i出發(fā)，沿pij到頂點j，轉(zhuǎn)n-圈ρ1次，轉(zhuǎn)其中一個(n-1)-圈ρ2次，轉(zhuǎn)另一個(n-1)-圈ρ3次的途徑有分解如下：

此時，結(jié)合圖1，可得0≤s≤d，0≤t≤d+1，0≤w≤n-2d+1.當(dāng)t=d+1時，s≥0，w≥0；當(dāng)s=d-1，w=n-2d+1或s=d-1，w=n-2d或s=d，w=n-2d-2時，t≥0；當(dāng)s=d，w=n-2d+1或w=n-2d時，pij至少轉(zhuǎn)其中一個(n-1)-圈1次.容易驗證，ρ1≥0，ρ2≥0，ρ3≥0.所以，

exp(D)≤(d-1)(nd-2d+n-2)+(d-1)×

(nd+d2+n-d-2)+d3+d(nd-

2d+n-2)+d(nd+d2+n-d-2)+(d+1)d2+(n-2d+1)(nd-2d+n-2)+(n-2d)(nd+d2+n-d-2)+

(n-2d-2)d2=n(nd-2d+n-2)+

(n-1)(nd+d2+n-d-2)+(n-1)d2

顯然，exp(D)是關(guān)于d的函數(shù)，利用maple對上式合并計算得

exp(D)≤2dn2+2n2+2d2n-2d2-

4dn-5n+d+2

對exp(D)關(guān)于變量d求導(dǎo)得

exp′(D)=2n2+4nd-4d-4n+1

因0≤d≤n/2-1，則exp′(D)>0，exp(D)在閉區(qū)間[0，n/2-1]上為增函數(shù)，因此

其他本原情況，尋找指數(shù)上界的方法與a=c，b=d，x=y=1，c-d=±1時相同，證明過程相似，故只給出結(jié)果不再贅述.當(dāng)a=c時，三色有向圖D的所有本原情況和本原指數(shù)上界，見表1所列.

表1 a=c時，D的本原條件和指數(shù)上界

4 極圖刻畫

定理6若a=c，b=d，x=y=1，c-d=1時，三色有向圖D是本原的，則

當(dāng)且僅當(dāng)D中恰有d+2長的連續(xù)紅路.

證明充分性) 結(jié)合定理5，要證明

exp(D)=n(nd+2n-2d-4)+(n-1)(nd+

d2+2n+d-2)+(n-1)(d2+2d+1)

只需證明

exp(D)≥n(nd+2n-2d-4)+(n-1)(nd+d2+2n+d-2)+(n-1)(d2+2d+1)

即可.

設(shè)存在一對非負整數(shù)(h，k，v)，使對D中所有頂點對(i,j)，都有一條從i到j(luò)的(h，k，v)-途徑.取i=j=n，則存在非負整數(shù)u1，u2和u3，使得

結(jié)合圖1，不難發(fā)現(xiàn)三色有向圖D若存在d+2長的連續(xù)紅路，則d+2長的連續(xù)紅路必在(n-1)-圈上.取i，j分別為d+2長連續(xù)紅路的起點和終點，則從i到j(luò)的路分解為(d+2，0，0)，因此

有非負整數(shù)解，即

故u2≥nd+d2+2n+d-2.

故u1≥nd+2n-2d-4，u3≥d2+2d+1.從而

所以

exp(D)≥n(nd+2n-2d-4)+(n-1)(nd+d2+2n+d-2)+(n-1)(d2+2d+1)

必要性) 若三色有向圖D是本原的，D中不存在d+2長的連續(xù)紅路，只需證明exp(D)

對D中的任意一對頂點(i,j)都有一((d+1)(nd+n-2d-2)+(d+1)(nd+d2+2n+d-3)+(d+2)(d2+2d+1)，d(nd+n-2d-2)+d(nd+d2+2n+d-3)+(d+1)(d2+2d+1)，(n-2d-1)(nd+n-2d-2)+(n-2d-2)(nd+d2+2n+d-3)+(n-2d-4)(d2+2d+1))-途徑.取ρ1=nd+n-2d-2+(n-2)s-nt-w，ρ2=nd+d2+2n+d-3-(n+d-1)s+(n+d+2)t+w，ρ3=d2+2d+1+ds-(d+1)t.因此，從頂點i出發(fā)，沿pij到頂點j，轉(zhuǎn)n-圈ρ1次，轉(zhuǎn)其中一個(n-1)-圈ρ2次，轉(zhuǎn)另一個(n-1)-圈ρ3次的途徑有分解

此時，結(jié)合圖1，可得0≤s≤d+2，0≤t≤d+1，0≤w≤n-2d-1.當(dāng)s=d+2時，t≥1或w≥1；當(dāng)s≤d+1時，t≥0且w≥0；當(dāng)t=d+1，w=n-2d-4時，s≥1.容易驗證，ρ1≥0，ρ2≥0，ρ3≥0.所以，

exp(D)≤(d+1)(nd+n-2d-2)+(d+1)(nd+

d2+2n+d-3)+(d+2)(d2+2d+1)+

d(nd+n-2d-2)+d(nd+d2+2n+

d-3)+(d+1)(d2+2d+1)+(n-

2d-1)(nd+n-2d-2)+(n-2d-2)×

(nd+d2+2n+d-3)+(n-2d-4)×

(d2+2d+1)=n(nd+n-2d-2)+

(n-1)(nd+d2+2n+d-3)+

(n-1)(d2+2d+1)

2d-4)+(n-1)(nd+d2+2n+

d-2)+(n-1)(d2+2d+1)

因此，a=c，b=d，x=y=1，c-d=1時，若D中不存在d+2長的連續(xù)紅路，則

exp(D)

(nd+d2+2n+d-2)+(n-1)(d2+2d+1)

結(jié)合定理5，定理得證.

類似定理5、定理6的證明，可得定理7.

定理7若a=c，b=d，x=y=1，c-d=-1時，三色有向圖D是本原的，則

exp(D)=n(nd-2d+n-2)+(n-1)×

(nd+d2+n-d-2)+(n-1)d2

當(dāng)且僅當(dāng)D中恰有d+1長的連續(xù)黃路.