zbMATH — the first resource for mathematics

Counting and constructing minimal spanning trees. (English) Zbl 0886.05049
The paper presents an algorithm for constructing minimal spanning trees in a network. It is based on the known result that any two minimal spanning trees in a network have the same number of edges of weight \(k\) for each \(k\), suggesting the possibility of partitioning the minimal tree construction process. An algorithm to this effect is outlined as well as a formula for the number of minimal spanning trees.
05C05 Trees
05C30 Enumeration in graph theory
94C15 Applications of graph theory to circuits and networks
94C05 Analytic circuit theory
PDF BibTeX Cite