4
$\begingroup$

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

$\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$

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.

$\endgroup$
  • 4
    $\begingroup$ Maybe you should edit the Wiki article? :) $\endgroup$ – Raphael Mar 31 '12 at 7:19
8
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.