Why cannot I find any information about spanning tree for DAG ? I must be wrong somewhere.
$\begingroup$
$\endgroup$
2
-
8$\begingroup$ Please flesh out the question a bit. Why do you think the usual definition does not make sense? Of course, you will have to decide wether the spanning three should have directed paths from a root to all nodes or not; that might make a difference. $\endgroup$– Raphael ♦Mar 30, 2012 at 10:45
-
8$\begingroup$ Whether such a thing exists depends crucially on your definitions. $\endgroup$– Dave ClarkeMar 30, 2012 at 10:53
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
4
Why focusing on dags and not general directed graphs? I think you should have a look at the directed minimum spanning tree problem, also known as the arborescence problem (PDF). The problem can be solved using the Chu-Liu/Edmonds algorithm. The wikipedia entry is not as clear as I was expecting, but it does have links to the original papers.
-
4$\begingroup$ Maybe you should edit the Wiki article? :) $\endgroup$– Raphael ♦Mar 31, 2012 at 7:19
-
1
-
$\begingroup$ The Chu-Liu/Edmonds algorithm requires specifying a single root whereas spanning trees do not specify a root. There is nothing about directed graphs, whether cyclic or acyclic, that inherently constrains one to minimum solution with a single root, let alone that the root(s) is(are) givens. $\endgroup$ Jul 27, 2021 at 17:41
-
$\begingroup$ @wanderingmathematician I checked the Wayback machine and that link has unfortunately been broken since it was first archived way back in 2015. I found some PDF lecture notes to link instead. $\endgroup$ Oct 25, 2021 at 19:14
$\begingroup$
$\endgroup$
1
One generalization of a tree in a directed graph is an arborescence. It is a directed tree with all edges directed from parent to child.
-
$\begingroup$ What about some sort of Minimum Spanning Forest? I don't see a problem with making an MST for each root. $\endgroup$ Nov 4, 2019 at 9:28
$\begingroup$
$\endgroup$
1
The case for DAGs is trivial, which might be the reason you cannot find any dedicated information about them.
First, there must be a unique vertex $r$ of zero incoming degree, which is the root of the directed spanning tree (arborescence). (Otherwise no spanning tree can exist.)
Next, for each vertex $v \neq r$ choose a parent vertex $P(v)$ such that the $w(v, P(v))$ is minimal.
We chose $|V| - 1$ edges in a graph of $|V|$ vertices with no cycles, so thus chosen subset of edges forms a spanning tree $T$. Any other spanning tree, for each vertex $v \neq r$, must have a unique incoming edge $(v, Q(v))$. By our construction $w(v, P(v)) \leq w(v, Q(v))$. Summing over all $v \neq r$ we get that $T$ is minimal.
-
1$\begingroup$ What about some sort of Minimum Spanning Forest? I don't see a problem with making an MST for each vertex of zero incoming degree. $\endgroup$ Nov 4, 2019 at 9:29