矩阵相关的概念

adjacency matrix 邻接矩阵

一个图的邻接矩阵的定义是:\(A=\lbrace a_{ij} \rbrace\),其中\(a_{ij}=e_{ij}\),第\(ij\)个元素指的是边\(e_{ij}\)的值。

incidence matrix 关联矩阵

一个图的关联矩阵定义为:\(M=\lbrace m_{ij} \rbrace\),其中\(m_{ij}\)为1,如果节点\(v_i\)和边\(e_j\)相关,举例而言:

的关联矩阵为:

e1 e2 e3 e4 e5 e6
v1 1 1 0 0 0 0
v2 0 0 1 1 0 1
v3 0 0 0 0 1 1
v4 1 0 1 0 0 0
v5 0 1 0 1 1 0