Ask Your Question

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 +0200

David Auger gravatar image

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

FrédéricC gravatar image

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

1 Answer

Sort by » oldest newest most voted

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

tmonteil gravatar image

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

edit flag offensive delete link more

Your Answer

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

Add Answer

Question Tools


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

Seen: 394 times

Last updated: Apr 14 '17