王 寧,邵燕靈

(中北大學(xué)數(shù)學(xué)系,山西太原030051)

1 引 言

非負矩陣的組合理論是研究那些僅依賴于矩陣的零位模式,而與本元素的數(shù)值無關(guān)的性質(zhì),它與圖的某些性質(zhì)有密切聯(lián)系,在信息科學(xué)、通信網(wǎng)絡(luò)、計算機科學(xué)等許多方面有具體的應(yīng)用背景.上世紀年代以來,有關(guān)本原矩陣 (本原有向圖)的本原指數(shù)的研究進展非常迅速,許多問題已經(jīng)圓滿解決.

定義1[1]如果 n階有向圖D是某個n階本原矩陣的伴隨有向圖,則稱D為n階本原有向圖,簡稱n階本原圖.稱A的本原指數(shù)ν(A)為本原有向圖D的本原指數(shù),記為ν(D).

本原指數(shù)的研究最早開始于1950年Wielandt的工作,給出了n階本原指數(shù)的一般性上界

1964年,Dulmage和M endelsohn創(chuàng)造性的運用有向圖理論,得出了 n階本原指數(shù)的一般性上界的另一種形式

其中s是A的伴隨有向圖D(A)的最小圈長.

概括起來,對ν(A)的研究主要集中于以下四個方面:

1)對ν(A)上界的估計,稱為M I問題 (Maximun index).

2)對ν(A)指數(shù)集的刻劃,稱為IS問題 (Set of indicies).

3)極矩陣集合的描述,稱為EM問題 (Extremal matrix).

4)具有指數(shù)ν0的某一類本原矩陣集合的描述,稱為M S問題 (Set of matrices).

本文主要是利用圖論和矩陣理論的方法,對含有三個圈的本原不可冪定號有向圖的基進行了研究.通過運用對圖的特點和規(guī)律進行分析的方法,即有兩個圈長度相同,且都與第三個圈長度不同.首先通過利用有關(guān)本原不可冪定號有向圖的引理及定義得到基的上界再運用反證法并綜合運用 Frobenius集、本原指數(shù)、“異圈對”、SSSD途徑、歧義指數(shù)、圖的直徑等相關(guān)理論知識,討論了在這兩類圖中是否存在所需的SSSD途徑對,從而得出了含有三個圈的本原不可冪定號有向圖的基的精確值.

2 基本概念

設(shè)D是有向圖 (允許有環(huán)但不能有重復(fù)弧),將D中的每條弧標(biāo)記為1或-1所得到的圖稱為定號有向圖.定號有向圖D中的一條途徑W是由一系列的弧e1,e2,…,ek組成的,并且ei的終點與ei+1的始點相同 (i=1,2,…,k-1).途徑W中弧的條數(shù)稱為是途徑W的長度,記為l(W).途徑W的符號定義為記為sgn W.

定義2[2]設(shè)D是一個有向圖,如果存在一個正整數(shù)k,使得 D中任意一對頂點νi和νj(可以相同)都有從νi到νj的長為k的途徑,則稱 D是本原的,最小的 k就是D的本原指數(shù),記作exp(D).

定義3[2]設(shè) D是一個本原有向圖,對于νi∈D,存在正整數(shù) m,使得對任意 t≥m,從νi到D中任意一點都有長為t的途徑,滿足上述條件的最小的 m就是νi的點指數(shù),記作expD(νi).

定義4[3]在定號有向圖中的兩條途徑W1和W2,如果它們有相同的起點、終點、長度,但有不同的符號,則稱為SSSD途徑對.

定義5[3]設(shè) S是定號有向圖,如果s中不含SSSD途徑對,則稱 S是可冪的;否則,稱 S是不可冪的.

定義6[4]設(shè)S是一個本原不可冪定號有向圖,存在正整數(shù)l,使得對任意正整數(shù) t≥l,及 S中任意頂點νi和νj(可以相同),從νi到νj都有長為t的SSSD途徑對,則稱最小的 l是定號有向圖S的基,記作l(S).

3 預(yù)備知識

引理1[5-7]如果S是一個本原定號有向圖,那么S是不可冪的充分必要條件是S S中存在一對長度分別為 p1和 p2的圈 C1和 C2滿足下面兩個條件之一:

(Ⅰ)p1是奇數(shù),p2是偶數(shù),且sgn C2=-1.

(Ⅱ)p1和 p2都是奇數(shù),且sgn C1=-sgn C2.

為了方便起見,滿足 (Ⅰ)或 (Ⅱ)的圈對 C1和 C2我們稱之為“異圈對”.很容易看到,此時,閉途徑對W1=p2C1和W2=p1C2有相同的長度 p1p2,但有不同的符號:

設(shè) a1,…,ak是非負整數(shù),定義 Frobenius集[8]為 S(a1,…,ak)={r1a1+…+rkak|r1,…,rk是非負整數(shù)}.由Schur引理,如果gcd(a1,…,ak)=1,那么則有S(a1,…,ak)包含所有足夠大的非負整數(shù).在這種情況下,定義 Frobenius數(shù)φ(a1,…,ak)為對于所有整數(shù)m≥φ,使得 m∈S(a1,…,ak)成立的最小整數(shù)φ.

根據(jù)上述定義,有φ(a1,…,ak)-1不屬于 S(a1,…,ak).此外,如果 a,b是互素的非負整數(shù),那么:

設(shè)R={l1,…,lr}為本原有向圖D的圈長集合,且gcd(l1,…,lr)=1.用 d(D)表示 D的直徑.對于D中的每一對頂點x和y,設(shè) d(x,y)為從 x到y(tǒng)的距離,且 dR(x,y)(關(guān)于集合R,從 x到y(tǒng)的相對距離)為從 x到y(tǒng)至少接觸長為li(對于每個 i=1,…,r)的一個圈的最短途徑的長度.記φR=φ(l1,…,lr)為 Frobenius數(shù),那么對于本原指數(shù)和點指數(shù)有以下式子成立:

定義7[9]設(shè)S是一個本原不可冪定號有向圖,S的歧義指數(shù) (ambiguous index)被定義為S中最短的SSSD途徑對的長度,記為 r(S).

引理2[10]設(shè)S是一個本原不可冪定號有向圖,W1和W2是從點 u到點ν的長度為r的SSSD途徑對.則有:

證明 設(shè) x ,y,z是圖S中的任意三個頂點 (可以相同),設(shè) P是S中從z到u的長為 d (z,u)的最短的路,顯然有, 所以, 所以從ν到 y 存在長為的途徑 Q ,所以 P +W1+Q和 P +W2+Q形成了從x到y(tǒng)的長為xm∈Va(xD)d(x,u)+r+expS(ν)的 S SSD途徑對,所以上式成立.

本文對一類本原不可冪定號有向圖的基進行了研究,其基礎(chǔ)圖為圖1.并且綜合運用 Frobenius集、本原指數(shù)、“異圈對”、SSSD途徑、歧義指數(shù)、圖的直徑和反證法等相關(guān)知識,得出了此圖的基的精確值.

4 主要結(jié)果

定理1 設(shè) S是n(m≥2,s≥4,t≥0且 m+s+t階本原不可冪定號有向圖,D是它的基礎(chǔ)圖 (如圖1所示).

(Ⅰ)若S中的兩個n-t-m-s-1圈具有不同的符號,則l(S)=n2+m2+t2+2s2-2nt+2m t-2nm-3sn+3sm+3st+2s+n-6.

(Ⅱ)若S中的兩個n-t-m-s-1圈具有相同的符號,則l(S)=2n2+2m2+4s2+2 t2+4m t-4nm-4nt+6st-6sn+6sm+3s+n-7.

證明 (Ⅰ)在圖1中,令 Q1=(n-m-2t-2s-1,n-m-2 t-2s)+…+(n-m-t-2s-1,n-m-t-2s)+(n-m-t-2s,n-s)+…+(n-2,1)+(1,2)+…+(m-1,m),Q2=(n-m-2 t-2s-1,n-m-t-2s+1)+(n-m-t-2s+1,n-m-t-2s+2)+…+(n-s-2,n-s-1)+(n-s-1,m)是從n-m-2 t-2s-1到 m的長度為m+s+t的兩條途徑.由于S中 (僅有的)兩個 n-t-m-s-1圈具有不同的符號,則一定有sgn Q1=-sgn Q2,故 r ≤m+s+t,又≤n-t-m-s-2, 由公式(4)得:

圖1 本原不可冪定號有向圖D

對任意的 i,jòV(D),從i到n-m-2 t-2s-1的途徑的長度 d≤n-t-m-s-2.又注意到 m在兩個n-t-m-s-1圈上,由expD(m)≤n2-2nt+2m t-2nm+m2-3sn+3sm+3st+t2+2s2+2s-4可知對任意a≥n2-2nt+2m t-2nm+m2-3sn+3sm+3st+t2+2s2+2s-4,存在從 m到j(luò)的一條a長途徑,那么存在一對從i到j(luò)的長為d+r+expD(m)=n2+m2+t2+2s2-2nt+2m t-2nm-3sn+3sm+3st+2s+n-6的 SSSD途徑對.因此,l(S)≤n2+m2+t2+2s2-2nt+2m t-2nm-3sn+3sm+3st+2s+n-6.

接下來證明l(S)≥n2+m2+t2+2s2-2nt+2m t-2nm-3sn+3sm+3st+2s+n-6.用反證法證明從 n-m-t-2s+1到 n-s-1不存在長為 n2+m2+t2+2s2-2nt+2m t-2nm-3sn+3sm+3st+2s+n-7的SSSD途徑對.假設(shè)Wi(i=1,2)是任意兩條從 n-m-t-2s+1到 n-s-1的長為 k=n2+m2+t2+2s2-2nt+2m t-2nm-3sn+3sm+3st+2s+n-7的途徑.

那么每個 Wi是由若干個 Cn-t-m-s-1圈和若干個 Cn-m-t-2s+2圈和長為 n-3的路徑組成(其中Cn-m-t-2s+2,Cn-t-m-s-1分別表示n-m-t-2s+2圈與n-t-m-s-1圈).即 k=l(Wi)=ai(n-m-t-2s+2)+bi(n-t-m-s-1)+n-3(ai≥0,bi≥0),所以有

化簡為 (n-m-t-2s+2-b)(n-t-m-s-1)=(a+1)(n-m-t-2s+2).

因為此圖是本原有向圖,所以 n-t-m-s-1與 n-m-t-2s+2互素,所以n-m-t-2s+2|n-m-t-2s+2-b而n-m-t-2s+2＞n-m-t-2s+2-b所以n-m-t-2s+2-b=0或 b=0

當(dāng) n-m-t-2s+2-b=0時,得 a=-1(與 ai≥0矛盾).當(dāng) b=0時,到 n-m-t-2s+1到 n-s-1只繞 n-m-t-2s+2圈,不繞 n-t-m-s-1圈,那么sgn W1=sgn W2(矛盾).

所以S中不存在長為k的SSSD途徑對.從而得出l(S)≥n2+m2+t2+2s2-2nt+2m t-2nm-3sn+3sm+3st+2s+n-6.

綜合上述討論得出l(S)=n2+m2+t2+2s2-2nt+2m t-2nm-3sn+3sm+3st+2s+n-6.

(2)若S中 (僅有的)兩個 n-t-m-s-1圈具有相同的符號,則sgn Q1=sgn Q2.由于S是本原不可冪的,且S中僅有的3個圈是兩個 n-t-m-s-1圈和一個 n-m-t-2s+2圈,由引理1知,每個 n-t-m-s-1圈與 n-m-t-2s+2圈構(gòu)成一個“異圈對”.所以由公式 (1)知 (n-m-t-2s+2)Cn-t-m-s-1與(n-t-m-s-1)Cn-m-t-2s+2有不同的符號.令 P1=(n-m-2 t-2s-1,n-m-t-2s+1)+(n-m-t-2s+1,n-m-t-2s+2)+…+(n-s-1,m),P2=(n-m-2 t-2s-1,n-m-2 t-2s)+…+(n-m-t-2s-1,n-m-t-2s)+(n-m-t-2s,n-1)+(n-1,n)+(n,1)+(1,2)+…+(m-1,m)分別是從n-m-2 t-2s-1到m的長為m+s+t,m+t+3的途徑.令W1=P1+(n-m-t-2s+1)Cn-t-m-s-1,W2=P2+(n-m-t-s-2)Cn-m-t-2s+2是從 n-m-2 t-2s-1到 m的長為n2+m2+t2+2s2-2nm-2nt+2m t-3sn+3sm+3st+m+2s+t-1的途徑對.再令 P是從m到n-m-2 t-2s-1的長為 n-2m-2 t-2s-1的唯一途徑.那么有W1+P=(n-m-t-2s+2)Cn-t-m-s-1,W2+P=(n-t-m-s-1)Cn-m-t-2s+2,從而W1與W2符號不同.因此W1與W2是一對從n-m-2 t-2s-1到m的長為n2+m2+t2+2s2-2nm-2nt+2m t-3sn+3sm+3st+m+2s+t-1的SSSD途徑對.類似 (1)的證明,得出

接下來證明

l(S)≥2n2+2m2+4s2+2t2+4m t-4nm-4nt+6st-6sn+6sm+3s+n-7用反證法證明從 n-m-t-2s+1到n-s-1不存在長為2n2+2m2+4s2+2 t2+4m t-4nm-4nt=6st-6sn+6sm+3s+n-8的SSSD途徑對.假設(shè)Wi(i=1,2)是任意兩條從n-m-t-2s+1到 n-s-1的長為 k=2n2+2m2+4s2+2t2+4m t-4nm-4nt+6st-6sn+6sm+3s+n-8的途徑.那么每個Wi是由若干個Cn-t-m-s-1圈和若干個 Cn-m-t-2s+2圈和長為 n-3的路徑組成,即 k=l(Wi)=ai(n-m-t-2s+2) +bi(n-t-m-s-1)+n-3(ai,bi≥0),故有 (a2-a1)(n-m-t-2s+2)=(b1-b2)(n-t-m-s-1).設(shè)a2-a1=(n-t-m-s-1)x,下證x=0.用反證法,如果 x≥1,則 a2≥n-t-m-s-1(由 a1≥0),所以有

φ(n-m-t-2s+2,n-t-m-s-1) -1=n2+m2+t2+2s2-2nt-2nm+2m t-3sn+3sm+3st-n+m+3s+t-3=-n2-m2-t2-2s2+2nt-2m t+2nm+3sn-3sm-3st-n+m+t+1+a2(n-m-t-2s+2)+b2(n-t-m-s-1)+n-3=[a2-(n-t-m-s-1)](n-m-t-2s+2)+b2(n-t-m-s-1).這與φ(n-m-t-2s+2,n-t-m-s-1)的定義矛盾.同理可證 x≤-1也與φ(n-m-t-2s+2,n-t-m-s-1)的定義矛盾.所以 x=0成立,即有a1=a2,b1=b2.那么有sgnW1=sgnW2,所以S中不存在長為k的SSSD途徑對.從而得出l(S)≥2n2+2m2+4s2+2 t2+4m t-4nm-4nt+6st-6sn+6sm+3s+n-7

綜合以上討論得出

l(S)=2n2+2m2+4s2+2 t2+4m t-4nm-4nt+6st-6sn+6sm+3s+n-7.定理得證.

[1] Shen J,Neufeld S.Local exponents of primitive digraphs[J].Linear Algebra Appl,1998,268：117-129

[2] Li Z,Hall F,Eschenbach C.On the period and base of a sign pattern matrix[J].Linear A lgebra App l,1994,212/213：101-120

[3] Brualdi RA,Liu B.Generalized exponents of primitive directed graphs[J].J Graph Theory,1990(14)：483-499

[4] You LH,Shao JY,Shan H Y.Bounds on the bases of irreducible generalize sign pattern matrix[J].Linear A lgebra App l,2007,427：285-300

[5] Shao JY.On the exponent of a primitive digraph[J].Linear Algebra Appl,1985,64：21-31

[6] Liu BL.Boundson the base of primitive nearly reducible sign pattern matrices[J].Linear Algebra Appl,2006,418：863-881

[7] Gao YB,Shao YL,Shen J.Bounds on the local bases of primitive non-powerful nearly reducible sign patterns[J].Linear Multilin Algebra,2009,57(2)：205-215

[8] 胡紅萍.圖與矩陣的組合理論及其網(wǎng)絡(luò)應(yīng)用 [D].太原：中北大學(xué),2009

[9] 霍麗芳,高玉斌.兩個圍長為2的本原不可冪定號有向圖的廣義基 [J].數(shù)學(xué)的實踐與認識,2010,(10)：235-239

[10] Wang LQ,Miao ZK,Yan C.Local bases of primitive non-powerful signed digraphs[J].Discr Math,2009,309(4)：748-754