graph-theory - 如果我对DAG进行拓扑排序，是否可以丢弃一半邻接矩阵？

Question

我认为我已经了解了如下所述的特定情况，但是我缺乏进行证明的理论知识，而且找不到任何提及它的资料。如果我的理解是正确的，那么我可以在邻接矩阵上节省一半的空间，如果不是的话，我可能会遇到一些非常奇怪的错误。因此，我想确定一下，如果背景更扎实的人可以复习我的推理，我将不胜感激。

假设我在n * n邻接矩阵中表示n个顶点的DAG，因此，如果从顶点i,j到顶点1到顶点i之间存在边，则条目j为0。由于该图是有向的和非循环的，因此，如果是i,j = 1，则遵循j,i = 0。如果我现在对矩阵中的节点进行排序，以使in处的节点的拓扑级别等于或大于in-1处的节点，那么在我看来，邻接矩阵的一半将始终仅包含0，如以下示例所示:

V 1 V 2从V 1 2 3 4 5 6 7 8
///
/\/\到V 1 0 0 0 0 0 0 0 0
/\/\2 0 0 0 0 0 0 0 0
e1/e2\e3/e4\3 1 0 0 0 0 0 0 0
/\/\4 1 1 0 0 0 0 0 0
V 3 V 4 V 5 5 0 1 0 0 0 0 0 0
/|\/6 0 0 0 1 0 0 0 0
/|\/7 0 0 0 1 0 0 0 0
/|\/8 0 0 0 1 1 0 0 0
e5/e6 | e7\e8/
/|\/
V 6 V 7 V 8

也许我是对的，但是有没有正式的方法可以检查这一点？

Answer 1

假设adj[i][j]是从节点i到节点j的邻接条目，并且您已对其进行排序，以使得对于所有节点i < j，节点i在拓扑层次结构中都比节点j高。

让我们暂时假设您的假设是不正确的:我们有一个反示例，其中adj[i][j] == 1代表i > j(即矩阵表示形式右上角的一个)。这意味着必须存在一个包含i和j的循环，因为我们的排序保证了节点j高于节点i，但我们拥有adj[i][j] == 1意味着我们可以“爬升”层次结构。这是矛盾的，因为我们知道我们有DAG。因此，我们证明了您的假设是正确的。