我认为我已经了解了如下所述的特定情况,但是我缺乏进行证明的理论知识,而且找不到任何提及它的资料。如果我的理解是正确的,那么我可以在邻接矩阵上节省一半的空间,如果不是的话,我可能会遇到一些非常奇怪的错误。因此,我想确定一下,如果背景更扎实的人可以复习我的推理,我将不胜感激。
假设我在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
也许我是对的,但是有没有正式的方法可以检查这一点?
最佳答案
假设adj[i][j]
是从节点i
到节点j
的邻接条目,并且您已对其进行排序,以使得对于所有节点i < j
,节点i
在拓扑层次结构中都比节点j
高。
让我们暂时假设您的假设是不正确的:我们有一个反示例,其中adj[i][j] == 1
代表i > j
(即矩阵表示形式右上角的一个)。这意味着必须存在一个包含i
和j
的循环,因为我们的排序保证了节点j
高于节点i
,但我们拥有adj[i][j] == 1
意味着我们可以“爬升”层次结构。这是矛盾的,因为我们知道我们有DAG。因此,我们证明了您的假设是正确的。
关于graph-theory - 如果我对DAG进行拓扑排序,是否可以丢弃一半邻接矩阵?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/777613/