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的几种矩阵表示。

图2-7　图G

A（G）=　　M（G）=

D（G）=　　Dis（G）=

C（G）=　　L₁（G）=

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