Wang Haihua
🍈 🍉🍊 🍋 🍌
本节均假设图 $G=(V, E)$ 为简单图, 其中 $V=\left\{v_{1}, v_{2}, \cdots, v_{n}\right\}$, $E=\left\{e_{1}, e_{2}, \cdots, e_{m}\right\}$ 。
对于无向图 $G$, 其关联矩阵 $M=\left(m_{i j}\right)_{n \times m}$, 其中 $$ m_{i j}= \begin{cases}1, & \text { 若 } v_{i} \text { 与 } e_{j} \text { 相关联, } \\ 0, & \text { 若 } v_{i} \text { 与 } e_{j} \text { 不关联. }\end{cases} $$ 对有向图 $G$, 其关联矩阵 $M=\left(m_{i j}\right)_{n \times m}$, 其中 $$ m_{i j}= \begin{cases}1, & \text { 若 } v_{i} \text { 是 } e_{j} \text { 的起点, } \\ -1, & \text { 若 } v_{i} \text { 是 } e_{j} \text { 的终点, } \\ 0, & \text { 若 } v_{i} \text { 与 } e_{j} \text { 不关联. }\end{cases} $$
对无向非赋权图 $G$, 其邻接矩阵 $W=\left(w_{i j}\right)_{n \times n}$, 其中 $$ w_{i j}= \begin{cases}1, & \text { 若 } v_{i} \text { 与 } v_{j} \text { 相邻， } \\ 0, & \text { 若 } v_{i} \text { 与 } v_{j} \text { 不相邻. }\end{cases} $$ 对有向非赋权图 $D$, 其邻接矩阵 $W=\left(w_{i j}\right)_{n \times n}$, 其中 $$ w_{i j}= \begin{cases}1, & \text { 若 }\left\langle v_{i}, v_{j}\right\rangle \in A, \\ 0, & \text { 若 }\left\langle v_{i}, v_{j}\right\rangle \notin A .\end{cases} $$
对无向赋权图 $G$, 其邻接矩阵 $W=\left(w_{i j}\right)_{n \times n}$, 其中 注 $10.1$ 当两个顶点之间不存在边时, 根据实际问题的含义或算法需 要, 对应的权可以取为 0 或 $\infty$ 。 有向赋权图的邻接矩阵可类似定义。
参考资料