##### 关联矩阵 - 关联矩阵 - **关联矩阵**是利用顶点和边之间的相关关系来表示[[图]]的[[矩阵]]. 给定图 $G=(V,E)$, 顶点集 $V = \{v_1, v_2, \ldots, v_n\}$, 边集 $E = \{e_1, e_2, \ldots, e_m\}$, 则关联矩阵 $A$ 是一个 $n \times m$ 的矩阵, 其中元素 $A_{ij}$​ 表示顶点 $v_i$​ 与边 $e_j$ 的关系. 对于[[无向图]]和[[有向图]]各有不同 - 无向 $\displaystyle A_{ij}=\left\{{\begin{array}{rl}\,1&{\text{顶点 }}v_{i}{\text{ 与边 }}e_{j}\text{ 相关}\\0&{\text{无关}}\end{array}}\right.$ - 有向 $\displaystyle A_{ij}=\left\{{\begin{array}{rl}{-1}&{\text{边 }}e_{j}{\text{ 从顶点 }}v_{i}\text{ 出发}\\{\phantom {-}}1&{\text{边 }}e_{j}{\text{ 指向顶点 }}v_{i}\\{\phantom {-}}0&{\text{无关}}\end{array}}\right.$