3

我有以下作业问题： DAG：设计一个线性时间算法 ( O(|E|+|V|)) 以确定 DAG 是否具有可从其他所有顶点到达的顶点，如果是，则找到一个。

现在我解决这个问题的方法如下：->首先找到拓扑排序中最后一个顶点（称之为V）。

-> 现在，确定反向图的每个顶点是否都可以从这个顶点 V 到达。

-> 如果每个顶点都是可到达的，那么顶点 V 就是所需的顶点，否则图中没有顶点可以从其他每个顶点到达。

这种方法正确吗？

PS。这个问题的解决方案的提示说我应该计算每个顶点的出度。但我无法理解计算出度有什么帮助。

4

3 回答 3

6

考虑一个 arc (u, v) ∈ E。由于该图是非循环的，u因此无法从 到达v。因此u不能解决问题。由此可见，只有出度为零的顶点才能成为解。

此外，必须恰好有一个顶点的出度为零，否则问题没有解决方案。

我把剩下的留给读者练习。

于 2013-03-30T08:19:37.347 回答
2

解决方案是计算所有顶点的出度，以查看是否有一个单一的汇顶点（出度为 0 的顶点），这是证明。

陈述：当且仅当存在一个出度为 0 的单个顶点时，DAG 有一个顶点可以从所有其他顶点到达。

这个陈述可以分两步来证明。

必要性证明：如果一个 DAG 包含一个可以从其他所有顶点到达的顶点 u，则它必须是唯一的汇顶点（出度为 0 的顶点）

  • 你有 0 出度，否则循环形式，与 DAG 相矛盾。
  • 不能有另一个出度为 0 的汇顶点 v，否则 u 不能从 v 到达

证明。

Proof of sufficiency: If a DAG contains one single sink vertex u, then u should be reachable from every other vertex.

Assume there exist vertices in the DAG that can't reach u. Let's divide all vertices in the DAG into the set of vertices that can reach u ($V_y$), and those cannot reach u ($V_n$), then there do not exist any edges from vertices in $V_n$ pointing to vertices in $V_y$.

Lemma: Any DAG must contain at least one sink vertices.

This is easy to prove by contradiction. Assume every vertex in the DAG has non-zero out-degrees, so starting from one vertex, we can keep traversing along the out-going edges of each vertex. Since DAG contains a finite number of vertices, we will return to a previously visited vertex eventually, i.e. cycle is detected, contradicting DAG definition.

Consider the graph formed by vertices in $V_n$ and edges between them, it must also be a DAG, otherwise, the original graph cannot be a DAG. Suppose v is a sink vertex in this sub-DAG, so v doesn't have any outgoing edge pointing to vertices in $V_n$.

As mentioned above, there can't be any edges from v pointing to any vertex in $V_y$ either, otherwise, v can reach u.

So the overall out-degrees of v in the original DAG is also 0, contradicting the assumption that the DAG contains a single sink vertex. Proved.

于 2019-10-29T20:43:08.970 回答
1

作为提示，考虑一下您可以使用通常的定义将 DAG 划分为源节点（入度 0）、中间节点和汇节点（出度 0）。

如果 DAG 确实包含这样的节点（可从其他每个顶点访问），它会是什么类型的节点？

画一个图的例子，它有两个出度为 0 的节点，每个顶点都有一个顶点可达。

于 2013-03-30T08:09:54.653 回答