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

2018-11-27 本文已影响32人默写年华Antifragile

参考: 关联矩阵与邻接矩阵

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&0\\ 0&0&0&0 \\ 0 &1 & 0 &1\\ 1&0&0&0 \end{matrix} \right]

关联矩阵：

\left[ \begin{matrix} 1&0&0&-1&1\\ -1&-1&0&0&0 \\ 0 &1 & 1 &0 &-1\\ 0&0&-1&1&0 \end{matrix} \right]

上一篇下一篇

猜你喜欢

热点阅读