图的矩阵表示

无向图 $G=<V,E>$, $|V|=n$, $|E|=m$, 令 $m_{ij}$ 为 $v_i$ 与 $e_j$ 的关联次数, 称 $(m_{ij}{)}_{n\times m}$ 为 $G$ 的关联矩阵, 记为 $M(G)$.

有向图 $D=<V,E>$, 令 $m_{ij}=\{\begin{array}{ll}1& v_i\text{为}{e}_j\text{的起点}\\ 0& v_i\text{与}{e}_j\text{不关联}\\ -1& v_i\text{为}{e}_j\text{的终点}\end{array}$, 则称 $(m_{ij}{)}_{n\times m}$ 为 $D$ 的关联矩阵, 记为 $M(D)$.

有向图 $D=<V,E>$, 令 $a_{ij}^{(1)}$ 为顶点 $v_i$ 邻接到顶点 $v_j$ 边的条数, 称 $(a_{ij}^{(1)}{)}_{n\times n}$ 为 $D$ 的邻接矩阵, 记为 $A(D)$.

有向图 $D=<V,E>$, 令 $p_{ij}=\{\begin{array}{ll}1& v_i\to v_j\\ 0& \text{others}\end{array}$, 称 $(p_{ij}{)}_{n\times n}$ 为 $D$ 的可达矩阵, 记为 $P(D)$.