布爾矩陣半環的單位圖*

韋揚江,陶冰雨,張小鳳,周美江

(南寧師范大學 數學與統計學院,廣西 南寧 530100)

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

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

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

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

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

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

1 圖G(Mn())的頂點數

對于A=(aij)∈Mn(),記RA={(i,j)|aij=1}.如果B∈Mn()使得A+B是置換矩陣,則有RA∪RB=RA+B.因此A是圖G(Mn())中的一個頂點當且僅當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())的頂點數為

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

由于G(Mn())的頂點數恰為|Q1|+|Q2|+…+|Qn|,故結論成立.

以下均設n≥3.

2 圖G(Mn())的直徑

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

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

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

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

(2) 設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) 設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.

設Bi∈N(Si),i=1,2,且B1+B2∈Pn.因為Bi≤Si,i=1,2,且RS1∩RS2=?,不失一般性,可設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=?知存在細胞Es,ts≤S2,s≠1且ts≠j1.設

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設S1,S2為3階置換矩陣,則d(S1,S2)當RS1∩RS2≠?時為2,否則為4.

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

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

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

證明設

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.此時有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)=?.此時d(A,S)≥3.

情形3.1存在p,p′∈I′和q,q′∈I″使得Ep,q≤S,Ep′,q′S.此時存在置換矩陣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≠?.此時取(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.

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

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

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

設n是奇數.設

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

再考慮n為偶數的情況.如果J≠?,則與前面n是奇數情形的討論類似,可得d(A,S)=4.設J=?,則有p∈I′使得Ep,j1≤S.同時,若Ei1,q≤S,則q∈I″.設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為奇數) 設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.事實上,令A0=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為偶數) 設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.事實上,令A′=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.

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

令A=E1,1+E2,2+…+En-1,n-1,B=E1,2+E2,3+…+En-1,n.易知A1∈N(A)當且僅當A1=t1E1,1+t2E2,2+…+tn-1En-1,n-1+En,n,其中ti∈{0,1},i=1,2,…,n-1.類似地,B1∈N(B)當且僅當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.下設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.

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

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

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

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

3 圖G(Mn())的頂點度和團數

本節先確定G(Mn())中每個頂點的度,然后確定它的團數.

定理3.1設A∈Hn,則

其中m=wt(A).

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

設A∈HnPn,令A=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)當且僅當對任意B∈W都有RC?RA∪RB.由于wt(A)=m,所以RA的子集數為2m.因此deg(A)=2m(n-m)!.

定理3.2G(Mn())的團數是n+1.

現設H是G(Mn())的最大的團,其中|H|=t≥n+1,則對于α,β∈H,α+β是一個置換矩陣.因此,在團H中恰好存在一個置換矩陣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())的著色數

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

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

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

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

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