含三個(gè)圈的本原不可冪定號(hào)有向圖的基

王 寧,邵燕靈

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

1 引 言

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

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

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

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

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

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

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

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

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

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

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

2 基本概念

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

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

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

定義4[3]在定號(hào)有向圖中的兩條途徑W1和W2,如果它們有相同的起點(diǎn)、終點(diǎn)、長(zhǎng)度,但有不同的符號(hào),則稱為SSSD途徑對(duì).

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

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

3 預(yù)備知識(shí)

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

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

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

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

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

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

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

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

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

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

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

4 主要結(jié)果

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

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

(Ⅱ)若S中的兩個(gè)n-t-m-s-1圈具有相同的符號(hào),則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的長(zhǎng)度為m+s+t的兩條途徑.由于S中 (僅有的)兩個(gè) n-t-m-s-1圈具有不同的符號(hào),則一定有sgn Q1=-sgn Q2,故 r ≤m+s+t,又≤n-t-m-s-2, 由公式(4)得:

圖1 本原不可冪定號(hào)有向圖D

對(duì)任意的 i,jòV(D),從i到n-m-2 t-2s-1的途徑的長(zhǎng)度 d≤n-t-m-s-2.又注意到 m在兩個(gè)n-t-m-s-1圈上,由expD(m)≤n2-2nt+2m t-2nm+m2-3sn+3sm+3st+t2+2s2+2s-4可知對(duì)任意a≥n2-2nt+2m t-2nm+m2-3sn+3sm+3st+t2+2s2+2s-4,存在從 m到j(luò)的一條a長(zhǎng)途徑,那么存在一對(duì)從i到j(luò)的長(zhǎng)為d+r+expD(m)=n2+m2+t2+2s2-2nt+2m t-2nm-3sn+3sm+3st+2s+n-6的 SSSD途徑對(duì).因此,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不存在長(zhǎng)為 n2+m2+t2+2s2-2nt+2m t-2nm-3sn+3sm+3st+2s+n-7的SSSD途徑對(duì).假設(shè)Wi(i=1,2)是任意兩條從 n-m-t-2s+1到 n-s-1的長(zhǎng)為 k=n2+m2+t2+2s2-2nt+2m t-2nm-3sn+3sm+3st+2s+n-7的途徑.

那么每個(gè) Wi是由若干個(gè) Cn-t-m-s-1圈和若干個(gè) Cn-m-t-2s+2圈和長(zhǎng)為 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),所以有

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

因?yàn)榇藞D是本原有向圖,所以 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時(shí),得 a=-1(與 ai≥0矛盾).當(dāng) b=0時(shí),到 n-m-t-2s+1到 n-s-1只繞 n-m-t-2s+2圈,不繞 n-t-m-s-1圈,那么sgn W1=sgn W2(矛盾).

所以S中不存在長(zhǎng)為k的SSSD途徑對(duì).從而得出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中 (僅有的)兩個(gè) n-t-m-s-1圈具有相同的符號(hào),則sgn Q1=sgn Q2.由于S是本原不可冪的,且S中僅有的3個(gè)圈是兩個(gè) n-t-m-s-1圈和一個(gè) n-m-t-2s+2圈,由引理1知,每個(gè) n-t-m-s-1圈與 n-m-t-2s+2圈構(gòu)成一個(gè)“異圈對(duì)”.所以由公式 (1)知 (n-m-t-2s+2)Cn-t-m-s-1與(n-t-m-s-1)Cn-m-t-2s+2有不同的符號(hào).令 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的長(zhǎng)為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的長(zhǎng)為n2+m2+t2+2s2-2nm-2nt+2m t-3sn+3sm+3st+m+2s+t-1的途徑對(duì).再令 P是從m到n-m-2 t-2s-1的長(zhǎng)為 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符號(hào)不同.因此W1與W2是一對(duì)從n-m-2 t-2s-1到m的長(zhǎng)為n2+m2+t2+2s2-2nm-2nt+2m t-3sn+3sm+3st+m+2s+t-1的SSSD途徑對(duì).類似 (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不存在長(zhǎng)為2n2+2m2+4s2+2 t2+4m t-4nm-4nt=6st-6sn+6sm+3s+n-8的SSSD途徑對(duì).假設(shè)Wi(i=1,2)是任意兩條從n-m-t-2s+1到 n-s-1的長(zhǎng)為 k=2n2+2m2+4s2+2t2+4m t-4nm-4nt+6st-6sn+6sm+3s+n-8的途徑.那么每個(gè)Wi是由若干個(gè)Cn-t-m-s-1圈和若干個(gè) Cn-m-t-2s+2圈和長(zhǎng)為 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中不存在長(zhǎng)為k的SSSD途徑對(duì).從而得出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] 霍麗芳,高玉斌.兩個(gè)圍長(zhǎng)為2的本原不可冪定號(hào)有向圖的廣義基 [J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),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