有向图的关联矩阵与邻接矩阵有何联系

有向图的邻接矩阵和关联矩阵都是表示有向图的常用矩阵表示方法。

邻接矩阵是一个 $n\times n$ 的矩阵，其中 $n$ 表示有向图中顶点的个数。如果 $i$ 到 $j$ 有一条有向边，则邻接矩阵中的第 $i$ 行第 $j$ 列为 $1$，否则为 $0$。

而关联矩阵是一个 $n\times m$ 的矩阵，其中 $n$ 表示有向图中的顶点数，$m$ 表示有向边的数量。如果第 $i$ 个顶点和第 $j$ 条边之间有关联，则关联矩阵中的第 $i$ 行第 $j$ 列为 $1$ 或 $-1$，表示该边是从 $i$ 开始或者结束。

它们的联系在于，我们可以从邻接矩阵中得到关联矩阵。具体地，设邻接矩阵为 $A$，则关联矩阵 $B$ 可以通过以下方法得到：

1. 对于邻接矩阵中第 $i$ 行第 $j$ 列为 $1$ 的元素，假设这是一条从 $i$ 到 $j$ 的边，则在关联矩阵中的第 $i$ 行第 $k$ 列和第 $j$ 行第 $k$ 列分别为 $1$ 和 $-1$，其中 $k$ 是表示第 $i$ 到 $j$ 的第 $k$ 条边。
2. 对于邻接矩阵中第 $i$ 行第 $j$ 列为 $0$ 的元素，则在关联矩阵中的第 $i$ 行和第 $j$ 行的所有列都为 $0$。

因此，关联矩阵可以从邻接矩阵中计算得到。