如果我对DAG进行拓扑排序，是否可以丢弃一半邻接矩阵? [英] If I topologically sort a DAG, can I drop half the adjacency matrix?

问题描述

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

I think I have understood a particular situation as described below, but I lack the theoretical knowledge to conduct a proof and I couldn't find any source that mentions it. If my understanding is correct, I can save half the space on my adjacency matrix, if it isn't I'm likely to have pretty weird bugs. So I'd like to be sure, and I'd appreciate if someone with a more solid background could review my reasoning.

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

Say I represent a DAG of n vertices in an n * n adjacency matrix such that the entry i,j is 1 if there is an edge from vertex i to vertex j, 0 otherwise. Because the graph is directed and acyclic, it follows that, if i,j = 1, then j,i = 0. If I now sort the nodes in the matrix such that the topological level of the node at i_n is equal to or greater than the node at i_n-1, then it seems to me that half of the adjacency matrix will always only contain 0s, as it is the case in the following example:

      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

也许我是对的，但是有没有一种正式的方法来检查这一点?

Maybe I'm just right, but is there a formal way to check this?

推荐答案

让adj[i][j]成为从节点i到节点j的邻接项，并且已经对所有节点i < j进行了排序，节点i在拓扑层次结构中比节点j高.

Let adj[i][j] be the adjacency entry from node i to node j and you've sorted it such that for all nodes i < j, node i is higher up the topological hierarchy than node j.

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

Let's assume for a moment that your assumption was incorrect: that we have a counter-example for which adj[i][j] == 1 for i > j (i.e., a one in the upper-right half of your matrix representation). This implies that there must be a cycle containing i and j, since our sorting guarantees that node j is higher up than node i yet we have adj[i][j] == 1 implies we can "climb" up the hierarchy. This is a contradiction, since we know we have a DAG. Therefore we have proven that your assumption is correct.

这篇关于如果我对DAG进行拓扑排序，是否可以丢弃一半邻接矩阵?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！