n階圈圖的一些代數(shù)性質(zhì)

莫貴圈

(貴州師范學(xué)院 數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院，貴州 貴陽 550018)

?

n階圈圖的一些代數(shù)性質(zhì)

莫貴圈

(貴州師范學(xué)院 數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院，貴州 貴陽 550018)

圈圖；關(guān)聯(lián)矩陣；鄰接矩陣；行列式；秩

1 引言及相關(guān)概念

圖論是數(shù)學(xué)的一個分支，它以圖為研究對象，是研究結(jié)點(diǎn)和邊組成的圖形的數(shù)學(xué)理論和方法.圖的表示方式通常有三種，可以用集合、圖形和矩陣來表示.用矩陣表示圖便于用代數(shù)方法來研究圖的性質(zhì)，也便于用計算機(jī)來處理圖.常用的圖的矩陣表示有: 關(guān)聯(lián)矩陣、鄰接矩陣和可達(dá)矩陣.圖的關(guān)聯(lián)矩陣用來表示各個結(jié)點(diǎn)和每條邊之間的關(guān)系，它是描述一個圖中結(jié)點(diǎn)與邊關(guān)聯(lián)性質(zhì)的矩陣；圖的鄰接矩陣用來表示各個結(jié)點(diǎn)之間的關(guān)系，它是描述一個圖中結(jié)點(diǎn)與結(jié)點(diǎn)是否相關(guān)的矩陣.目前，已有不少學(xué)者對圖的關(guān)聯(lián)矩陣、鄰接矩陣進(jìn)行了研究，例如文獻(xiàn)[1]研究了應(yīng)用代數(shù)學(xué)中的置換理論，得出了關(guān)聯(lián)矩陣的一些特殊性質(zhì).關(guān)聯(lián)矩陣、鄰接矩陣都是特殊的(0,1)矩陣，文獻(xiàn)[2]研究了線和為2的兩種(0,1)矩陣的秩.文獻(xiàn)[3]介紹了一種新方法，該方法建立屬性的關(guān)聯(lián)矩陣，然后通過計算屬性的類方差選擇分裂屬性，對原來的ID3算法加以改進(jìn).

關(guān)聯(lián)矩陣和鄰接矩陣的應(yīng)用，是學(xué)者們討論的熱點(diǎn)之一.例如文獻(xiàn)[4]討論了在帶權(quán)圖中利用鄰接矩陣求最短通路；文獻(xiàn)[5]介紹了在二部圖定義的基礎(chǔ)上，給出了一種基于鄰接矩陣的新判斷算法，該算法能較好解決二部圖的判定問題[6]；研究了利用圖的鄰接矩陣及關(guān)聯(lián)矩陣求簡單圖的最大匹配和二分圖的完美匹配；文獻(xiàn)[7]研究了利用鄰接矩陣和關(guān)聯(lián)矩陣來判斷無向圖同構(gòu)的方法；文獻(xiàn)[8]介紹了在圖的關(guān)聯(lián)矩陣基礎(chǔ)上，提出了求無權(quán)簡單圖最大匹配的一種操作簡單、編程容易的新算法——“表單作業(yè)法”；文獻(xiàn)[9]介紹了鄰接矩陣與關(guān)聯(lián)矩陣在圖論問題中的一些應(yīng)用，解決了最大匹配、最小頂點(diǎn)覆蓋、選址等問題.綜上可見，學(xué)者們對有向圖和無向圖的關(guān)聯(lián)矩陣、鄰接矩陣的代數(shù)性質(zhì)的研究甚少，因此，本文將重點(diǎn)研究n階無向圈圖的關(guān)聯(lián)矩陣和n 階有向圈圖的關(guān)聯(lián)矩陣、鄰接矩陣的行列式、秩等代數(shù)性質(zhì).

定義1[10](1)設(shè)G=為n(n≥3)階無向簡單圖,V={v1,v2,…,vn},E={(v1,v2),(v2,v3),…,(vn-1,vn),(vn,v1)}，則稱G為n階圈圖，記作Cn.

(2)設(shè)D為n(n≥2)階有向簡單圖，V={v1,v2,…,vn},E={,,…,,}，則稱D為n階圈圖，也可記作Cn.

定義2[10]設(shè)無向圖G=，V={v1,v2,…,vn}，E={e1,E2,…,em},令mij為頂點(diǎn)vi與邊ej的關(guān)聯(lián)次數(shù)，則稱(mij)n×m為G的關(guān)聯(lián)矩陣，記作M(G).

定義3[10]設(shè)有向無環(huán)圖G=，V={v1,v2,…,vn}，E={e1,E2,…,em}，令：

則稱(mij)n×m為G的關(guān)聯(lián)矩陣，記作M(G).

2 結(jié)論及其證明

定理1 設(shè)Cn是n(n≥3)階無向圈圖，Cn的關(guān)聯(lián)矩陣M(Cn)的行列式與秩分別為:

證明 因為Cn是n階無向圈圖， 所以Cn的關(guān)聯(lián)矩陣為:

綜上得n C 的關(guān)聯(lián)矩陣M(Cn)的行列式與秩分別為:

定理2 n階有向圈圖的關(guān)聯(lián)矩陣M(Cn)的行列式與秩分別為:

所以?n∈N,都有|M(Cn)|=0.

定理3 n階有向圈圖的鄰接矩陣A(Cn)的行列式與秩分別為:

由上述討論知|A(Cn)|≠0知， A(Cn)為滿秩矩陣，即R(A(Cn))=n.綜上得，n階有向圈圖的鄰接矩陣A(Cn)的行列式與秩分別為:

[1] 董永紅,簡芳洪.關(guān)聯(lián)矩陣的一些特殊性質(zhì)[J].九江學(xué)院學(xué)報(自然科學(xué)版),2011，44(3):37-39.

[2] 朱雪芳.一類(0,1)矩陣的秩[J].杭州師范大學(xué)學(xué)報(自然科學(xué)版),2013,12(3):223-226.

[3] 方立.基于關(guān)聯(lián)矩陣的決策樹分類算法[J].長春大學(xué)學(xué)報,2013,23(4):426-429.

[4] 黃師化. 鄰接矩陣求帶權(quán)圖中最短通路[J].安慶師范學(xué)院學(xué)報(自然科學(xué)版),2013,19(4):26-28.

[5] 王敏，韓俊英.一種基于鄰接矩陣的二部圖判定算法[J].重慶理工大學(xué)學(xué)報(自然科學(xué)版),2011,25(8):75-77.

[6] 李世群.簡單圖的最大匹配的矩陣求法[J].數(shù)學(xué)的實(shí)踐與認(rèn)識,2007,37(7):120-124.

[7] 張磊，李世群．用矩陣判斷無向圖同構(gòu)的幾種方法[J].衡陽師范學(xué)院學(xué)報，2011，32(6):19-21.

[8] 段春生，莊劉.關(guān)于簡單圖最大匹配的矩陣算法研究[J].四川師范大學(xué)學(xué)報(自然科學(xué)版),2012,35(4):478-481.

[9] 付小娟,李宗濤. 基于鄰接矩陣與關(guān)聯(lián)矩陣解決最大匹配等問題[J].貴陽學(xué)院學(xué)報(自然科學(xué)版),2015,10(2):7-9.

[10] 屈婉玲,耿素云.離散數(shù)學(xué)[M].3版.北京：清華大學(xué)出版社,2014:171-172.

責(zé)任編輯：時 凌

SomeAlgebraicPropertiesofnOrderCircleGraphs

MOGuiquan

(CollegeofMathematicsandComputerScience,GuizhouEducationUniversity,Guiyang550018,China)

Inthispaper,wediscussthecorrelationmatrixofnorderundirectedgraphandthecorrelationmatrixoforderdirectedgraph,thedeterminantofadjacencymatrix,thealgebraicpropertiesofrankandsoon,andgetthecorrespondingconclusion:①thedeterminantandrankofthecorrelationmatrixM(Cn)ofnorderundirectedgraphsare:|M(Cn)|=2,R(M(Cn))=n,nisodd;|M(Cn)|=0,R(M(Cn))=n-1, niseven.②ThedeterminantandrankofthecorrelationmatrixM(Cn)ofnorderdirectedgraphare:|M(Cn)|=0,R(M(Cn))=n-1,nisinteger. ③ThedeterminantandrankoftheadjacencymatrixA(Cn)ofthedirectedgraphare:|A(Cn)|=1,R(A(Cn)=n,nisodd; |A(Cn)|=-1,R(A(Cn))=n,niseven.

circlegraph;incidencematrix;adjacencymatrix;determinant;rank

2016-08-12.

國家自然科學(xué)基金項目(11661023);2015年省級本科教學(xué)工程建設(shè)項目(黔教高發(fā)[2015]337號).

莫貴圈(1984- ),女,碩士生，講師,主要從事半群的研究.

1008-8423(2016)03-0295-04

10.13501/j.cnki.42-1569/n.2016.09.013

O

A