n階圈圖的一些代數性質

莫貴圈

(貴州師范學院 數學與計算機科學學院，貴州 貴陽 550018)

?

n階圈圖的一些代數性質

莫貴圈

(貴州師范學院 數學與計算機科學學院，貴州 貴陽 550018)

圈圖；關聯矩陣；鄰接矩陣；行列式；秩

1 引言及相關概念

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

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

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

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

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

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

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

2 結論及其證明

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

證明 因為Cn是n階無向圈圖， 所以Cn的關聯矩陣為:

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

定理2 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] 董永紅,簡芳洪.關聯矩陣的一些特殊性質[J].九江學院學報(自然科學版),2011，44(3):37-39.

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

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

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

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

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

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

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

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

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

責任編輯：時 凌

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.

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

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

1008-8423(2016)03-0295-04

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

O

A