Why cannot I find any information about spanning tree for DAG ? I must be wrong somewhere.
4
$\begingroup$
$\endgroup$
-
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 '12 at 10:45
-
8$\begingroup$ Whether such a thing exists depends crucially on your definitions. $\endgroup$ – Dave Clarke Mar 30 '12 at 10:53
8
$\begingroup$
$\endgroup$
Why focusing on dags and not general directed graphs? I think you should have a look at the directed minimum spanning tree problem. 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
-
8
$\begingroup$
$\endgroup$
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$ – Radio Controlled Nov 4 at 9:28
1
$\begingroup$
$\endgroup$
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.
-
$\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$ – Radio Controlled Nov 4 at 9:29
