Abstract:
An algorithm is proposed for constructing directed spanning forests of the minimal weight, in which the maximum possible degree of affinity between the minimal forests is preserved when the number of trees changes. The consistency of the algorithm is checked and its complexity is determined, which does not exceed $ O (N ^ 3) $ for dense graphs. The result of the algorithm is a set of related spanning minimal forests consisting of $ k $ trees for all admissible $ k $.
Key words and phrases:weighted digraph, minimum forest, Markov chain.
Fulltext:
PDF file (531 kB)