n階圈圖關(guān)聯(lián)矩陣的特征值

莫貴圈

(貴州師范學(xué)院數(shù)學(xué)與大數(shù)據(jù)學(xué)院，貴州貴陽(yáng)550018)

0 引言

圖論是數(shù)學(xué)的一個(gè)分支，它是以圖為研究對(duì)象，研究結(jié)點(diǎn)和邊組成的圖形的數(shù)學(xué)理論和方法。圈圖是圖論中的一類圖形。目前，已有不少學(xué)者對(duì)圈圖進(jìn)行了研究，例如文獻(xiàn)[1]分別討論了圈外有0個(gè)頂點(diǎn)和t個(gè)頂點(diǎn)的單圈圖關(guān)聯(lián)矩陣的特征值，并證明了特征值完全反映了圈上的頂點(diǎn)個(gè)數(shù)和圈外的頂點(diǎn)個(gè)數(shù)；文獻(xiàn)[2]研究了包含一個(gè)∞—圖為其導(dǎo)出子圖的一類雙圈圖匹配多項(xiàng)式的最大根的取值范圍，以及達(dá)到極值的圖；文獻(xiàn)[3]研究了兩類連通雙圈圖的最大特征值，得出了隨著n的增大，雙圈圖Sn(3，3)和θn(3，3)的最大特征值也隨之增大；文獻(xiàn)[4]研究了給定階數(shù)的k圈圖的最大Laplace 分離度，并刻畫了相應(yīng)的極圖。

圖可以用集合來表示，也可以用矩陣來表示。用矩陣表示圖便于用代數(shù)方法來研究圖的性質(zhì)，也便于用計(jì)算機(jī)來處理圖。常用的圖的矩陣表示有： 關(guān)聯(lián)矩陣、鄰接矩陣和可達(dá)矩陣。圖的關(guān)聯(lián)矩陣用來表示各個(gè)結(jié)點(diǎn)和每條邊之間的關(guān)系，是描述一個(gè)圖中結(jié)點(diǎn)與邊關(guān)聯(lián)性質(zhì)的矩陣。關(guān)聯(lián)矩陣也是學(xué)者們討論的熱點(diǎn)之一，例如文獻(xiàn)[5]研究了關(guān)聯(lián)矩陣的一些特殊性質(zhì)；文獻(xiàn)[6]研究了利用鄰接矩陣和關(guān)聯(lián)矩陣來判斷無向圖同構(gòu)的方法；文獻(xiàn)[7]介紹了鄰接矩陣與關(guān)聯(lián)矩陣在圖論問題中的一些應(yīng)用，解決了最大匹配、最小頂點(diǎn)覆蓋、選址等問題；文獻(xiàn)[8]重點(diǎn)研究了n階無向圈圖的關(guān)聯(lián)矩陣的行列式和秩，以及n階有向圈圖的關(guān)聯(lián)矩陣和鄰接矩陣的行列式、秩等代數(shù)性質(zhì)。

1 預(yù)備知識(shí)

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

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

定義2[9]144設(shè)無向圖G=〈V，E〉，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[9]145設(shè)G=〈V，E〉為無環(huán)的有向圖，V={v1，v2，…，vn}，令E={e1，e2，…，em}，令

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

定義4[9]146設(shè)有向圖D=〈V，E〉，V={v1，v2，…，vn}，|E|=m，令aij(1)為頂點(diǎn)vi鄰接到頂點(diǎn)vj的邊的條數(shù)，稱(aij(1))n×n為D的鄰接矩陣，記作A(D).

HRCT與常規(guī)CT均可見IPF病患的肺部病灶呈彌漫分布，兩肺下葉及胸膜下尤甚，其主要征象表現(xiàn)為：（1）胸膜增厚；（2）支氣管擴(kuò)張，呈柱狀、囊狀性擴(kuò)張；（3）胸膜下線，其胸膜下10毫米內(nèi)和胸膜平行、垂直的不均性線形影，尤以背段、外基底段及肺下葉后多見；（4）小葉肺氣腫，其表現(xiàn)為小囊腔大量聚集，與蜂窩狀相似，多見于下葉；（5）胸膜增厚，小葉間隔性不規(guī)則增厚，胸膜下的小葉內(nèi)出現(xiàn)細(xì)網(wǎng)狀或細(xì)線狀影。

2 主要結(jié)果及證明

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

則M(Cn)的特征多項(xiàng)式為：

|λE-M(Cn)|

=(λ-1)n+(-1)1+2n

=(λ-1)n-1

定理2 設(shè)Cn是n階有向圈圖，則Cn的關(guān)聯(lián)矩陣M(Cn)的特征值分別為：

證明：因?yàn)镃n是n階有向圈圖，所以Cn的關(guān)聯(lián)矩陣為：

|λE-M(Cn)|

=(λ-1)n+(-1)n+1.

證明：因?yàn)镃n是n階有向圈圖，所以Cn的鄰接矩陣為：

則A(Cn)的特征多項(xiàng)式為：

|λE-A(Cn)|

=(-1)2n+1+λn

=λn-1

應(yīng)用上面的定理3，可以證明下面的結(jié)論。

推論1 復(fù)數(shù)域上所有n次單位根的和為0.

證明：設(shè)Cn是n階有向圈圖，則Cn的鄰接矩陣為：