布尔矩阵半环的单位图*

韦扬江,陶冰雨,张小凤,周美江

(南宁师范大学 数学与统计学院,广西 南宁 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,进而结论成立.