Does spanning tree make sense for DAG?

Question

Why cannot I find any information about spanning tree for DAG ? I must be wrong somewhere.

Answer 1

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.

Answer 2

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.

Answer 3

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.