英和和英

出典:『Wikipedia』 (2010/12/31 09:06 UTC 版)

英語による解説

引用

Capacitated minimum spanning tree is a minimal cost spanning tree of a graph that has a designated root node r and satisfies the capacity constraint c. The capacity constraint ensures that all subtrees (maximal subgraphs connected to the root by a single edge) incident on the root node r have no more than c nodes. If the tree nodes have weights, then the capacity constraint may be interpreted as follows: the sum of weights in any subtree should be no greater than c. The edges connecting the subgraphs to the root node are called gates. To find the optimal solution, one has to go through all the possible spanning tree configurations for a given graph and pick the one with the lowest cost; such search requires an exponential number of computations.