跨越树对DAG有意义吗？

Question

为什么我找不到有关DAG的跨越树的任何信息？我一定在某个地方错了。

Answer 1

为什么要专注于DAG而不是一般的定向图？我想你应该看看 定向的最小跨树问题. 。可以使用 Chu-Liu/Edmonds算法. 。 Wikipedia条目并不像我期望的那样清晰，但确实有与原始论文的链接。

Answer 2

在有向图中的树的一个概括是 树木. 。这是一棵有向树，所有边缘都从父母到孩子。

Answer 3

DAGS的情况是微不足道的，这可能是您找不到有关它们的任何专用信息的原因。

首先，必须有一个唯一的顶点$ r $零传入度，这是定向跨越树的根（树木）。 （否则不存在生成树。）

接下来，对于每个顶点$ v neq r $选择一个父顶点$ p（v）$，使$ w（v，p（v））$很小。

我们选择$ | V | - $ | V | $顶点的图中的1 $边缘没有任何循环，因此选择的边缘子集形成一个跨度树$ t $。对于每个顶点$ v neq r $，任何其他跨越树都必须具有唯一的传入边缘$（v，q（v））$。通过我们的构造$ W（v，p（v）） leq W（v，q（v））$。总结所有$ v neq r $，我们得到$ t $很少。