9

我想我已经理解了如下所述的特定情况，但是我缺乏进行证明的理论知识，并且找不到任何提及它的来源。如果我的理解是正确的，我可以在我的邻接矩阵上节省一半的空间，如果不是，我可能会有非常奇怪的错误。所以我想确定一下，如果有更扎实背景的人可以审查我的推理，我将不胜感激。

假设我在 n * n 邻接矩阵中表示 n 个顶点的 DAG，这样条目i,j是否1存在从 vertexi到 vertex的边j，0否则。因为该图是有向图和无环图，所以如果i,j = 1，则j,i = 0。如果我现在对矩阵中的节点进行排序，使得 i n处的节点的拓扑级别等于或大于 i n-1处的节点，那么在我看来，邻接矩阵的一半将始终只包含0s ，如下例所示：

      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

也许我是对的，但是有没有正式的方法来检查这个？

4

2 回答 2

7

让我们adj[i][j]成为从节点i到节点的邻接条目，j并且您已经对其进行了排序，使得对于所有节点i < j，节点i在拓扑层次结构中高于节点j。

让我们暂时假设您的假设不正确：我们有一个反例adj[i][j] == 1for i > j（即，在矩阵表示的右上半部分中的一个）。这意味着必须有一个包含i和的循环j，因为我们的排序保证节点j高于节点i但我们已经adj[i][j] == 1暗示我们可以“爬上”层次结构。这是一个矛盾，因为我们知道我们有一个 DAG。因此，我们已经证明您的假设是正确的。

于 2009-04-22T15:33:28.850 回答
-1

仅当您的邻接矩阵是使用按排序顺序的图形标签构造时，这才是正确的。举一个反例，构造 B->C->A 的邻接矩阵。

如果您将真实节点的散列保留到其拓扑排序位置并从中构造邻接矩阵，则可以在大矩阵上节省一些空间，因为您在矩阵中使用 O(n) 节省了 O(n²) 空间大小哈希表。

于 2009-04-22T15:17:20.090 回答