變換圖的張量積圖

金晶晶

(福建船政交通職業(yè)學院 公共教學部，福建 福州 350007)

20世紀50、60年代， Ryser H J和Fulkerson D R等數(shù)學家對(0，1)-矩陣類U(R,S)(具體定義見第1節(jié)的定義1)進行研究并得到許多重要結(jié)論[1,2].U(R,S)的相關(guān)性質(zhì)已廣泛地應(yīng)用于組合圖論和網(wǎng)絡(luò)流理論等領(lǐng)域中[1]. 1980年，著名的圖論專家Brualdi R A定義了U(R,S)上的變換圖G(R,S)[2]，并且提出關(guān)于變換圖的連通性、直徑與哈密爾頓性等問題[2]，許多學者隨之做了進一步研究[3-11]. 對變換圖G(R,S)結(jié)構(gòu)方面的問題，Jin J J 自2011年起陸續(xù)研究一類變換圖G(R*,S*)的基本性質(zhì)并刻畫其結(jié)構(gòu)特征[8-11].

本文所涉及的圖為簡單圖，未定義的術(shù)語參見文獻[12].

1 變換圖的定義

aij=0或1(i=1,…，m,j=1,…，n),

Brualdi R A定義的G(R,S)為無向簡單圖，其頂點集V(G(R,S))=U(R,S)，并且對任意A,B∈U(R,S),A，B在U(R,S)中相鄰當且僅當A能經(jīng)過一個變換得B.

2 變換圖的張量積圖

定義2 若A是一個m×n的矩陣，而B是一個p×q的矩陣，則矩陣的張量積(又稱Kronecker-積)是一個mp×nq的矩陣[13]：

即，A?B是把A的每個元素代之以塊aij?B而得. 矩陣的張量積是研究矩陣結(jié)構(gòu)的重要工具. 近30年來，矩陣的張量積在結(jié)構(gòu)矩陣方程理論和自動控制理論研究中得到重要應(yīng)用.

若G(R,S)是U(R,S)上的變換圖，與v∈G(R,S)所對應(yīng)的矩陣為A∈U(R,S).為方便表示，下面統(tǒng)一用v來表示其所對應(yīng)的(0,1)-矩陣A.

3 變換圖的張量積圖的若干性質(zhì)

|V(G)|、|E(G)|和D(G)分別表示圖G的頂點數(shù)、邊數(shù)和直徑. 由定義3和組合數(shù)學的乘法原理易得下面的定理.

定理2 |V(G1(R1,S1)?G2(R2,S2))|=|V(G1(R1,S1))|×|V(G2(R2,S2))|.

由定理2得，|V(G1(R1,S1)?G2(R2,S2))|≠0當且僅當|V(G1(R1,S1))|≠0且|V(G2(R2,S2))|≠0.

綜上，|E(G1(R1,S1)?G2(R2,S2))|≠0.

q1q2j1j2

情形2 情形1證明了v*=v?v′時定理3的必要性成立，下面證明v*=v′?v時定理3的必要性亦成立.

j1j2q1q2

由定理3立即得：

定理4 |E(G1(R1,S1)?G2(R2,S2))|=max{|E(G1(R1,S1))|,|E(G2(R2,S2))|}.

定理5 |D(G1(R1,S1)?G2(R2,S2))|=max{|D(G1(R1,S1))|,|D(G2(R2,S2))|}.

[1] Brualdi R A. Matrices of zeros and ones with fixed row and column sum vectors[J].Linear Algebra and its Applications, 1980, 33：159-231.

[2] Ryser H J. Combinatorial properties of matrices of zeros and ones[J]. Canadian Journal of Mathematics, 1957,9：371-377.

[3] 陳榮斯, 郭曉峰, 張?；? 一類0.1 矩陣變換圖的邊連通性[J]. 新疆大學學報(自然科學版), 1988, 5(1): 17-25.

[4] Li X L, Zhang F J. Hamiltonicity of a type of interchange graphs[J]. Discrete Applied Mathematics, 1994, 51(1/2)：107-111.

[5] Brualdi R A，Shen J. Disjoint cycles in Eulerian digraphs and the diameter of interchange graphs[J]. Journal of Combinatorial Theory Series B, 2002, 85(2)：189-196.

[6] 錢建國. 變換圖的直徑及Brualdi 猜想[J]. 數(shù)學學報, 2002, 45(2)：411-416.

[7] Yuster R. Packing 4-cycles in Eulerian and bipartite Eulerian tournaments with an application to distances in interchange graphs[J]. Annals of Combinatorics. 2005, 9(1):117-124.

[8] Jin J J. Some properties for a class of interchange graphs[J]. Discrete Applied Mathematics,2011, 159(17)：2069-2077.

[9] 金晶晶. 一類變換圖的距離性質(zhì)[J]. 吉首大學學報(自然科學版), 2012, 33(4): 31-36.

[10] 金晶晶. 一類變換圖的遞歸構(gòu)造方法[J]. 湖南工程學院學報(自然科學版), 2013, 23(4): 45-48.

[11] 金晶晶.每行和為1 的(0,1)方陣變換圖的若干性質(zhì)[J]. 寧德師范學院學報(自然科學版), 2015,27(3): 237-240.

[12] Bondy J A, Murty U S R. Graph theory with its applications[M]. Wisconsin: The MacMillan Press Ltd, 1976.

[13] 柳柏濂. 組合矩陣論[M]. 北京：科學出版社, 2005.