关联矩阵与邻接矩阵 2018-11-27

1. 邻接矩阵

1.1 定义

设无向图 G=(V, E)，其中顶点集 $V = {v_1, v_2,\cdots, v_n}$, 边集 $E={e_1, e_2, \cdots, e_m}$，
用 $a_{ij}$表示顶点$v_i$与顶点$v_j$之间的边的数目，可能取值为0, 1, 2, ....,
称所得矩阵$A=A(G)=(a_{ij}))_{n \times n}$为图 G 的邻接矩阵

1.2 邻接矩阵的性质

A(G) 是对称矩阵
若 G 是无环图，则A(G)中第 i 行(列)的元素之和等于顶点$v_i$的度

类似地，有向图D的邻接矩阵$A(D)=(a_{ij})_{n \times n}$，$a_{ij}$表示从始点$v_i$到终点$v_j$的有向边的条数，其中$v_i$和$v_j$为D的顶点

e.g. 求下图的邻接矩阵

其邻接矩阵如下所示：
$\left[ \begin{matrix} 0&1&1&1\\ 1&0&1&0 \\ 1 &1 & 0 &1\\ 1&0&1&0 \end{matrix} \right]$

2. 关联矩阵

2.1 定义：

设无向图 G=(V, E)，其中顶点集 $V = {v_1, v_2,\cdots, v_n}$, 边集 $E={e_1, e_2, \cdots, e_m}$，
用$m_{ij}$表示顶点$v_i$与边$e_j$关联的次数，可能取值为0, 1, 2, ....,
称所得的矩阵$M(G)=(m_{ij})_{n \times m} $为图G的关联矩阵

类似的，有向图D的关联矩阵的元素定义为：

\[m_{ij}=\left\{\begin{array}{cc} 1, & v_i 是有向边e_j的始点\\ -1, & v_i 是有向边e_j的终点\\ 0, & v_i 是有向边e_j的不关联点\\ \end{array}\right.\]