行數(shù)為2的變換圖的若干性質(zhì)

金晶晶

（福建船政交通職業(yè)學(xué)院 通識(shí)教育學(xué)院，福建 福州 350007）

但由于U(R,S)的復(fù)雜性，關(guān)于變換圖G(R,S)性質(zhì)和結(jié)構(gòu)刻畫(huà)的研究較少。變換圖G(R,S)的性質(zhì)是Brualdi 猜想研究的重要工具。為了深入研究變換圖G(R,S)的性質(zhì)，本文研究了行數(shù)為2 的變換圖G(R*,S*)，其中，R*=(r1,r2)且S*=(1,…,1)。

1 主要結(jié)果

對(duì)于行數(shù)為2的變換圖G(R*,S*)，若a1j= 1，則a2j= 0，j= 1,2,…,n；反之亦然。這就意味著A完全由第一行來(lái)決定。顯然，A的第一行A′是包含r1個(gè)“1”和n-r1個(gè)“0”的行向量；行數(shù)為2的變換圖G(R*,S*)是變換圖G(R,S)的子圖，G(R*,S*)的矩陣類U(R*,S*)是G(R,S)的矩陣類U(R,S)的2 × 2 子矩陣類，G(R*,S*)局部刻畫(huà)了G(R,S)的性質(zhì)和內(nèi)在結(jié)構(gòu)。定義H(r,n)為所有由“0”和“1”組成的n維行向量的集合，其中r( ≥1)表示每個(gè)n維行向量中“1”的個(gè)數(shù)，顯然，H(r,n)中每個(gè)n維行向量中“0”的個(gè)數(shù)為n-r。設(shè)B∈H(r,n)，B的一個(gè)變換是指將B的一個(gè)形如(0,1)（或(1,0)）的子向量替換成(1,0)（或(0,1)）的一個(gè)作用。G(r,n)定義為這樣的一個(gè)無(wú)向簡(jiǎn)單圖：其點(diǎn)集是H(r,n)，H(r,n)中的兩個(gè)n維行向量是相鄰的，當(dāng)且僅當(dāng)其中一個(gè)n維行向量可以由另外一個(gè)n維行向量經(jīng)過(guò)一個(gè)變換得到。比較G(R*,S*)與G(r,n)的定義，可得：

定理1G(R*,S*)與G(r,n)是同構(gòu)的，其中R*=(r1,r2)且S*=(1,1,…,1)，r=r1，n=r1+r2。

因此，只要研究G(r,n)的性質(zhì)就可得到G(R*,S*)的相應(yīng)性質(zhì)。

定理2G(r,n)同構(gòu)于G(n-r,n)。

證明G(r1,n1)的頂點(diǎn)v所對(duì)應(yīng)的行向量是n1維的，將它擴(kuò)大為n2維行向量v′，v′與v在第1至第n1位置上的元素相同，v′在第n1+ 1,n1+ 2,…,n1+r2-r1位置上的元素都是“1”，而在第n1+r2-r1+ 1,n1+r2-r1+ 2,…,n2位置上的元素都是“0”。記由這些v′所生成的圖為G′(r2,n2)，不難看到，G′(r2,n2) ?G(r1,n1)，且G′(r2,n2) ?G(r2,n2)。

定理6 的逆一般不成立。例如，G(1,6)是一個(gè)6 階完全圖，而G(2,4)是一個(gè)6 階非完全圖，所以與G(1,6)中的某個(gè)子圖同構(gòu)，但是，2 ＞1。

另外，G(r,n)有較好的連通性，G(r,n)的連通度等于其最小度r(n-r)[3]；G(r,n)是哈密爾頓圖[5]。

2 幾類變換圖的作圖

下面，根據(jù)變換圖的性質(zhì)，對(duì)變換圖G(1,4)、G(2,4)、G(2,5)和G(2,6)進(jìn)行作圖.用G[C]表示G(r,n)的點(diǎn)集的一個(gè)子集C的生成子圖。稱C為G的一個(gè)團(tuán)，當(dāng)且僅當(dāng)G[C]為完全圖。稱G(r,n)中點(diǎn)數(shù)最多的團(tuán)為最大團(tuán)。若G(r,n)中的一個(gè)頂點(diǎn)所對(duì)應(yīng)的行向量在i1,i2,…,it位置上的元素為“1”，其余位置上的元素全為“0”，則將該頂點(diǎn)記為vi1,i2,…,it，則變換圖G(1,4)、G(2,4)、G(2,5)分別為圖1～3：

圖1 變換圖G(1,4)Figure 1 Interchange graph G(1,4)

圖2 變換圖G(2,4)Figure 2 Interchange graph G(2,4)

圖3 變換圖G(2,5)Figure 3 Interchange graph G(2,5)

由圖1～3 可見(jiàn)，G(1,4)是完全圖；G(2,4)有8 個(gè)最大團(tuán)，每個(gè)最大團(tuán)的頂點(diǎn)數(shù)為3；G(2,5)有5 個(gè)最大團(tuán)，每個(gè)最大團(tuán)的頂點(diǎn)數(shù)為4。

下面，利用變換圖的性質(zhì)和遞歸構(gòu)造方法對(duì)G(2,6)進(jìn)行作圖。根據(jù)定理3，G(2,6)是8正則的，且其頂點(diǎn)數(shù)為V(G(2,6)) = 15，分別是v1,2、v1,3、v1,4、v1,5、v1,6、v2,3、v2,4、v2,5、v2,6、v3,4、v3,5、v3,6、v4,5、v4,6、v5,6，邊數(shù)E(G(2,6)) =60。G(2,6)共有6 個(gè)最大團(tuán)：C1={v1,2,v1,3,v1,4,v1,5,v1,6}，C2={v1,2,v2,3,v2,4,v2,5,v2,6}，C3={v1,3,v2,3,v3,4,v3,5,v3,6}，C4={v1,4,v2,4,v3,4,v4,5,v4,6}，C5={v1,5,v2,5,v3,5,v4,5,v5,6}，C6={v1,6,v2,6,v3,6,v4,6,v5,6}。每個(gè)最大團(tuán)的頂點(diǎn)數(shù)是5，邊數(shù)是10，且每個(gè)頂點(diǎn)都包含在2個(gè)最大團(tuán)中，每條邊恰包含在1個(gè)最大團(tuán)中?；谝陨嫌懻?，按照變換圖G(2,6)的最大團(tuán)構(gòu)造，先畫(huà)出最大團(tuán)C1={v1,2,v1,3,v1,4,v1,5,v1,6}，再依次按照最大團(tuán)C1、C2、C3、C4、C5、C6對(duì)G(2,6)進(jìn)行作圖。

圖4 變換圖G(2,6)中的最大團(tuán)C1Figure 4 The maximum clique of interchange graph G(2,6)

圖5 變換圖G(2,6)Figure 5 Interchange graph G(2,6)

綜上，變換圖G(1,5)、G(2,7)和G(3,6)亦可按照其性質(zhì)和最大團(tuán)的遞歸構(gòu)造進(jìn)行作圖，此處不再贅述。