MULTI-TERMINAL NETWORK FLOWS
MULTI-TERMINAL NETWORK FLOWS
复制标题
DOI：
10.1137/0109047
复制
发表时间：
1961-01-01
期刊：
影响因子：
--
通讯作者：
HU, TC
中科院分区：
文献类型：
--
作者：
GOMORY, RE;HU, TC
在生成树中，存在一个或多个其值在生成树中是最大的。这是一棵最大生成树，可以很容易地用Prim方法构造出来.任何最大生成树都具有以下容易建立的性质。设N和N是两个节点，其直接连接弧不在树中，则连接弧中的数目满足n-< min（n.，一个名词，其中ni，no是树内连接N到N的（唯一）路径的弧上的数字。因为如果不等式不成立，树路径中的最小弧可以被移除，并且直接弧NN被替换以形成具有大于最大值的值的树。
Among spanning trees there is one or more whose value is maximal among spanning trees. This is a maximal spanning tree and can easily be constructed byPrim’s method. Any maximal spanning tree has the following easily established property. Let N and N be two nodes whose direct connecting arc isnot in the tree, then the number in that connecting arc satisfies n-< min (n., n., no,) where the ni, no, are numbers on the arcs of the (unique) path connecting N to N within the tree. For if the inequality did not hold, the smallest arc in the tree path could be removed and the direct arc NN, substituted to form a tree with value larger than the maximum.