2.3　圖矩陣

由于現代計算機的誕生發展，使用矩陣對圖或者網絡進行描述是非常適合的。用矩陣形式表述各種網絡的拓撲統計性質，非常有利于編程的規范性和簡潔性。設G是一個圖，其中V（G）={v₁，…，v_n}和E（G）={e₁，…，e_m}分別是它的點集和邊集。

鄰接矩陣是應用最廣泛的矩陣。它描述各個節點之間的鄰接關系，因此包含了網絡的最基本拓撲性質。G的鄰接矩陣是一個n×n矩陣A（G）=（a_ij），其中a_ij是具有端點{v_i，v_j}的邊的數目。每個自環被作為兩條邊計數。

關聯矩陣描述各個節點和各條邊之間的鄰接關系，因此包含了網絡的最全面拓撲性質。G的關聯矩陣是一個n×m矩陣M（G）=（m_ij），其中m_ij是v_i和e_j相關聯的次數（0，1或2）。

圖G的度矩陣是一個n×n的對角矩陣D（G）=（d_ii），其中d_ii是點v_i的度。

圖G的距離矩陣是一個n×n的矩陣Dis（G）=（d_G（v_i，v_j）），其中d_G（v_i，v_j）是點v_i和點v_j之間的距離。

圈矩陣可以描述圖中所有圈以及它們的邊不交并所構成的圈與邊的關系。G的圈矩陣是一個（2^m-n+1-1）×m矩陣C（G）=（c_ij），其中c_ij=1（若邊e_j在圈i中）;否則c_ij=0。

圖G的拉普拉斯矩陣是一個n×n矩陣L₁（G）=D（G）-A（G）。特別地，G的規范化拉普拉斯矩陣定義為

L₂（G）=D（G（D（G）-A（G））D（G

也就是說，　　　　　　L₂（G）=D（GL₁（G）D（G。

G的無符號拉普拉斯矩陣定義為

L₃（G）=D（G）+A（G）

下面列出了圖2-7的幾種矩陣表示。

A（G）=　　M（G）=

D（G）=　　Dis（G）=

C（G）=　　L₁（G）=

L₂（G）=　　L₃（G）=