Is there a way to compute the list of rooted spanning trees or arborescences in a directed graph ?

asked 2017-04-13 10:12:24 +0100

updated 2017-07-31 21:19:20 +0100

5251 ●3 ●44 ●116

Given a directed graph $D$ and a specified vertex $r$, I would like the list of all directed spanning trees, or arborescences, rooted in $r$. This can be computed by induction as is done for spanning trees in undirected graphs with the spanning_trees method of the class Graph, but it seems like this has not been implemented for directed graphs.

edit retag flag offensive close merge delete

add a comment

1 Answer

Sort by » oldest newest most voted

answered 2017-04-14 21:04:37 +0100

tmonteil
27423 ●31 ●204 ●517 http://wiki.sagemath.o...

Indeed, it seems there is no method for enumerating spanning trees on digraphs (though there is a spanning_trees_countmethod for counting them based on the Kirchhoff matrix). If you have an implementation, let me suggest to add it into Sage itself, see http://www.sagemath.org/development.html

edit flag offensive delete link

add a comment

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2017-04-13 10:12:24 +0100

Seen: 518 times

Last updated: Apr 14 '17

Is there a way to compute the list of rooted spanning trees or arborescences in a directed graph ? edit

1 Answer