如果我在拓扑上对DAG进行排序,我可以减少一半的邻接矩阵吗？

Question

我想我已经理解了如下所述的特定情况,但我缺乏进行证据的理论知识,我找不到任何提及它的来源.如果我的理解是正确的,我可以在我的邻接矩阵上节省一半的空间,如果不是,我可能会有非常奇怪的错误.所以我想确定一下,如果有更坚实背景的人能够回顾我的推理,我会很感激.

假设我在n*n邻接矩阵中表示n个顶点的DAG,使得条目i,j是1从顶点i到顶点存在边缘j,0否则.因为图是有针对性的和非循环的,所以,如果i,j = 1,那么j,i = 0.如果我现在对矩阵中的节点进行排序,使得i _n处的节点的拓扑级别等于或大于i _n-1处的节点,那么在我看来,邻接矩阵的一半将始终仅包含0s ,就像以下示例中的情况一样:

      V 1           V 2     from V    1 2 3 4 5 6 7 8
      / \           / \ 
     /   \         /   \      to 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.因此,我们已经证明您的假设是正确的.