韋揚(yáng)江,陶冰雨,張小鳳,周美江

(南寧師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,廣西 南寧 530100)

0+0=0·0=0·1=1·0=0, 0+1=1+0=1+1=1·1=1.

設(shè)A=(aij),B=(bij)∈Mn(),如果對任意1≤i,j≤n都有aij≥bij,則稱A控制B,記為A≥B或B≤A.只有一個(gè)分量為1的布爾矩陣稱為細(xì)胞.用Eij表示(i,j)-元為1的細(xì)胞.令wt(A)為A中的分量1的個(gè)數(shù),稱為A的權(quán)重.

設(shè)G=(V,E)是無向圖,其中V和E分別是G的頂點(diǎn)集和邊集.邊的序列

α1-α2,α2-α3,…,αk-αk+1

稱為長為k的路(其中當(dāng)i≠j時(shí)有αi≠αj),用α1-α2-…-αk+1表示.G中頂點(diǎn)α與β的距離,記作d(α,β),定義為它們之間最短路徑的長度.G中與α相鄰的頂點(diǎn)的全體記為N(α),α的度deg(α)是集合N(α)的階數(shù).G的團(tuán)數(shù)是G的最大完全子圖的階數(shù),G的著色數(shù),是把G的所有頂點(diǎn)進(jìn)行著色而任意兩個(gè)相鄰頂點(diǎn)著色不同所用的最少顏色數(shù).

布爾矩陣A稱為可逆的或單位,如果存在布爾矩陣B使得AB=BA=E,其中E是單位陣.文獻(xiàn)[7]證明了布爾矩陣是可逆的當(dāng)且僅當(dāng)它是置換矩陣.令Pn為上的n階置換矩陣的全體,記Hn={A∈Mn()|A被某個(gè)n階置換矩陣控制}.顯然,如果A,B∈Mn()使得A+B是可逆的,則存在S∈Pn使得A≤S,B≤S.半環(huán)Mn()的單位圖,記作G(Mn()),是以Hn為頂點(diǎn)集的簡單無向圖,其中兩個(gè)不同的頂點(diǎn)A與B相鄰當(dāng)且僅當(dāng)A+B是單位.本文給出了G(Mn())的頂點(diǎn)數(shù),并利用置換矩陣的性質(zhì)先后確定了該圖的直徑、團(tuán)數(shù)和著色數(shù).

1 圖G(Mn())的頂點(diǎn)數(shù)

對于A=(aij)∈Mn(),記RA={(i,j)|aij=1}.如果B∈Mn()使得A+B是置換矩陣,則有RA∪RB=RA+B.因此A是圖G(Mn())中的一個(gè)頂點(diǎn)當(dāng)且僅當(dāng)RA={(i1,j1),(i2,j2),…,(is,js)},其中i1,i2,…,is兩兩不同,j1,j2,…,js兩兩不同,1≤s≤n.記In={1,2,…,n}.

定理1.1對于n≥2,圖G(Mn())的頂點(diǎn)數(shù)為

證明設(shè)Qt={A∈Hn|wt(A)=t},t=1,2,…,n.易見|Q1|=n2.

由于G(Mn())的頂點(diǎn)數(shù)恰為|Q1|+|Q2|+…+|Qn|,故結(jié)論成立.

以下均設(shè)n≥3.

2 圖G(Mn())的直徑

首先確定任意兩個(gè)置換矩陣之間的距離.

定理2.1設(shè)S1,S2是兩個(gè)不同的n階置換矩陣,其中

S1=E1,j1+E2,j2+…+En,jn,S2=E1,t1+E2,t2+…+En,tn.

(1) 如果RS1∩RS2≠?,則d(S1,S2)=2.

(2) 設(shè)RS1∩RS2=?.若存在子集{i1,i2,…,ix}?In,1

{ji1,ji2,…,jix}={ti1,ti2,…,tix},

則d(S1,S2)=3;否則d(S1,S2)=4.

證明由S1≠S2易知S1+S2不是置換矩陣,故d(S1,S2)≥2.

(1) 若RS1∩RS2≠?,則存在(i,j)∈RS1∩RS2,于是有Ei,j≤St,且Ei,j+St=St,t=1,2.因此S1-Ei,j-S2是一條長為2的路.所以d(S1,S2)=2.

(2) 設(shè)RS1∩RS2=?,則d(S1,S2)≥3.

若存在子集{i1,i2,…,ix}?In,1

In{i1,i2,…,ix}={p1,p2,…,pn-x},

A1=Ei1,ji1+Ei2,ji2+…+Eix,jix,A2=Ep1,tp1+Ep2,tp2+…+Epn-x,tpn-x,

則有A1≤S1,A2≤S2.由{ji1,ji2,…,jix}∩{tp1,tp2,…,tpn-x}=?可知A1+A2是置換矩陣,故S1-A1-A2-S2是一條長為3的路.所以d(S1,S2)=3.

若對于任何集合{i1,i2,…,ix}?In,1

{ji1,ji2,…,jix}≠{ti1,ti2,…,tix},

則N(S1)∩N(S2)=?.因此d(S1,S2)≥3.

設(shè)Bi∈N(Si),i=1,2,且B1+B2∈Pn.因?yàn)锽i≤Si,i=1,2,且RS1∩RS2=?,不失一般性,可設(shè)B1=E1,j1+E2,j2+…+Ed,jd,B2=Ed+1,td+1+Ed+2,td+2+…+En,tn,RB1∩RB2=?,1≤d

{j1,j2,…,jd}∩{td+1,td+2,…,tn}≠?,

從而B1+B2?Pn.這表明d(S1,S2)≥4.

再由RS1∩RS2=?知存在細(xì)胞Es,ts≤S2,s≠1且ts≠j1.設(shè)

In{1,s}={b1,b2,…,bn-2},In{j1,ts}={c1,c2,…,cn-2},

則S3=E1,j1+Es,ts+Eb1,c1+Eb2,c2+…+Ebn-2,cn-2∈Pn,并且S1-E1,j1-S3-Es,ts-S2是一條長為4的路.所以d(S1,S2)=4.

推論2.2設(shè)S1,S2為3階置換矩陣,則d(S1,S2)當(dāng)RS1∩RS2≠?時(shí)為2,否則為4.

例2.3(1) 設(shè)S1=E1,1+E2,3+E3,2,S2=E1,2+E2,1+E3,3.由定理2.1知d(S1,S2)=4.事實(shí)上,令S3=E1,1+E2,2+E3,3,則S1-E1,1-S3-E3,3-S2是一條長為4的路.

(2) 設(shè)S1=E1,1+E2,2+E3,3+E4,4,S2=E1,2+E2,1+E3,4+E4,3.由定理2.1知d(S1,S2)=3.事實(shí)上,令A(yù)1=E1,1+E2,2,A2=E3,4+E4,3,則S1-A1-A2-S2是一條長為3的路.

定理2.4max{d(A,S)|A∈HnPn,S∈Pn}=4.

證明設(shè)

A=Ei1,j1+Ei2,j2+…+Eim,jm, 其中m

S=E1,k1+E2,k2+…+En,kn,

I′=In{i1,i2,…,im},I″=In{j1,j2,…,jm}.

情形1A≤S.此時(shí)有A+S=S,故d(A,S)=1.

情形2AS且N(A)∩N(S)≠?.取B∈N(A)∩N(S),則A-B-S是一條長為2的路,這意味著d(A,S)=2.

情形3AS且N(A)∩N(S)=?.此時(shí)d(A,S)≥3.

情形3.1存在p,p′∈I′和q,q′∈I″使得Ep,q≤S,Ep′,q′S.此時(shí)存在置換矩陣S0∈N(A)使得Ep,q≤S0.因此A-S0-Ep,q-S是一條長為3的路.所以d(A,S)=3.

情形3.2對所有的p∈I′和q∈I″均有Ep,qS,且RA∩RS≠?.此時(shí)取(a,b)∈RA∩RS和置換矩陣S1,則有長為3的路A-S1-Ea,b-S.所以d(A,S)=3.

情形3.3對所有的p∈I′和q∈I″均有Ep,qS,且RA∩RS=?.

先證明d(A,S)≥4.

設(shè)I′={p1,p2,…,pn-m}.假設(shè)Ep1,h1+Ep2,h2+…+Epn-m,hn-m≤S,則{h1,h2,…,hn-m}∩I″=?,從而有

{h1,h2,…,hn-m}?InI″={j1,j2,…,jm}.

設(shè)A0∈N(A)且RA∩RA0=?.對于Et,kt≤S,t=1,2,…,n,顯然有Et,ktA,Et,ktA0.因此,對于和不可能是置換矩陣.所以與不相鄰,這意味著d(A,S)≥4.

設(shè)n是奇數(shù).設(shè)

A1=Ei1,b1+Ei2,b2+…+Eim,bm≤S,J={j1,j2,…,jm}∩{b1,b2,…,bm}.

再考慮n為偶數(shù)的情況.如果J≠?,則與前面n是奇數(shù)情形的討論類似,可得d(A,S)=4.設(shè)J=?,則有p∈I′使得Ep,j1≤S.同時(shí),若Ei1,q≤S,則q∈I″.設(shè)A′∈N(A)∩Pn且A+Ep,q≤A′.注意到Ei1,j1≤A,故有Ei1,j1+Ep,q≤A′,Ei1,q+Ep,j1≤S.從而由定理2.1知d(A′,S)=3,所以d(A,S)=4.

例2.5(定理2.4的子情形3.3 且n為奇數(shù)) 設(shè)n=5.令

A=E1,2+E2,3+E4,5,S=E1,1+E2,4+E3,2+E4,3+E5,5,

則

I′=In {1,2,4}={3,5},I″=In{2,3,5}={1,4},J={2,3,5}∩{1,3,4}={3}.

由定理2.4知d(A,S)=4.事實(shí)上,令A(yù)0=E3,1+E5,4,S2=A0+E1,2+E2,5+E4,3,則A-A0-S2-E4,3-S是一條長為4的路.

例2.6(定理2.4的子情形 3.3 且n為偶數(shù)) 設(shè)n=6.令

A=E1,3+E2,4+E3,2,S=E1,5+E2,1+E3,6+E4,2+E5,3+E6,4,

則

I′=In {1,2,3}={4,5,6},I″=In {2,3,4}={1,5,6},J={2,3,4}∩{1,5,6}=?.

由定理2.4知d(A,S)=4.事實(shí)上,令A(yù)′=A+E4,1+E5,5+E6,6∈Pn,B1=E1,3+E5,5,B2=E2,1+E3,6+E4,2+E6,4,則A-A′-B1-B2-S是一條長為4的路.

定理2.7max{d(A,B)|A,B∈HnPn}=5.

證明設(shè)A,B∈HnPn.取S∈Pn∩N(A),則由定理2.4知d(S,B)≤4.所以d(A,B)≤5.

令A(yù)=E1,1+E2,2+…+En-1,n-1,B=E1,2+E2,3+…+En-1,n.易知A1∈N(A)當(dāng)且僅當(dāng)A1=t1E1,1+t2E2,2+…+tn-1En-1,n-1+En,n,其中ti∈{0,1},i=1,2,…,n-1.類似地,B1∈N(B)當(dāng)且僅當(dāng)B1=k1E1,2+k2E2,3+…+kn-1En-1,n+En,1,其中kj∈{0,1},j=1,2,…,n-1.

如果A1∈Pn,則由定理2.4的子情形3.3可得d(A1,B)=4.下設(shè)A1?Pn.

情形1B1∈Pn.由定理2.4的子情形3.2和3.3可知d(A1,B1)=3或4.

(1)

其中{m1,m2,…,ms}={p1,p2,…,ps}.

(2)

其中{l1,l2,…,lh}={q1+1,q2+1,…,qh+1}.

由(1)和(2)可得N(A1)∩N(B1)=?,所以d(A1,B1)≥3.

綜合前面的結(jié)論可知d(A,B)=5.事實(shí)上,令

則有長為5的路A-Z1-E2,2-Z2-En,1-B.

由定理2.1、2.4和2.7立即得到

定理2.8G(Mn(B))的直徑為5.

3 圖G(Mn())的頂點(diǎn)度和團(tuán)數(shù)

本節(jié)先確定G(Mn())中每個(gè)頂點(diǎn)的度,然后確定它的團(tuán)數(shù).

定理3.1設(shè)A∈Hn,則

其中m=wt(A).

證明設(shè)A∈Pn,則頂點(diǎn)B與A相鄰當(dāng)且僅當(dāng)B≤A,當(dāng)且僅當(dāng)RB?RA且B≠A.由于|RA|=n,RA的非空真子集的數(shù)量為2n-2.因此,deg(A)=2n-2.

設(shè)A∈HnPn,令A(yù)=Ei1,j1+Ei2,j2+…+Eim,jm,其中m

W={B∈N(A)|RA∩RB=?},

則對任意B∈W均有B=Es1,t1+Es2,t2+…+Esn-m,tn-m,其中

{s1,s2,…,sn-m}=In{i1,i2,…,im},{t1,t2,…,tn-m}=In {j1,j2,…,jm}.

顯然,|W|=(n-m)!.因此,對于C∈Hn,C∈N(A)當(dāng)且僅當(dāng)對任意B∈W都有RC?RA∪RB.由于wt(A)=m,所以RA的子集數(shù)為2m.因此deg(A)=2m(n-m)!.

定理3.2G(Mn())的團(tuán)數(shù)是n+1.

現(xiàn)設(shè)H是G(Mn())的最大的團(tuán),其中|H|=t≥n+1,則對于α,β∈H,α+β是一個(gè)置換矩陣.因此,在團(tuán)H中恰好存在一個(gè)置換矩陣S.所以對于A∈H必有A≤S.則H={S,α1,α2…,αt-1},其中S=E1,j1+E2,j2+…+En,jn,j1,j2,…,jn兩兩不同,且

αi=ki,1E1,j1+ki,2E2,j2+…+ki,nEn,jn,i=1,2,…,t-1,

4 圖G(Mn())的著色數(shù)

定理4.1G(Mn())的著色數(shù)是n+1.

證明由于兩個(gè)不同的置換矩陣不相鄰,因此所有置換矩陣都可以使用相同的顏色T0.設(shè)

Lt={Ei1,j1+Ei2,j2+…+Eis,js∈HnPn|t=min{Ini1,i2,…,is}},t=1,2,…,n,

則對于G(Mn())的任意頂點(diǎn)A,如果A?Pn,則必存在某個(gè)集合Lt使得A∈Lt.

對于任一個(gè)集合Lm(m=1,2,…,n)中的不同頂點(diǎn)A,B,顯然A+B不是置換矩陣,因此A與B不相鄰,所以,同一個(gè)集合Lm中的頂點(diǎn)可以使用相同的顏色.假設(shè)集合L1,L2,…,Ln的頂點(diǎn)分別使用顏色T1,T2,…,Tn.另一方面,設(shè)頂點(diǎn)C與D相鄰.若C,D中有一個(gè)是置換矩陣,則另一個(gè)必不是置換矩陣,從而C與D的著色不同;若C與D都不是置換矩陣,則這兩個(gè)矩陣顯然不在同一個(gè)集合Lm中.所以,C與D的著色也不同.因此,總共有n+1個(gè)顏色分配給G(Mn())的所有頂點(diǎn),使得相鄰的頂點(diǎn)著色不同.由定理3.2知G(Mn())的團(tuán)數(shù)為n+1,進(jìn)而結(jié)論成立.