极小树与割集

本文考虑了极小树与割集之间的联系,给出了一种关于求极小树的算法模型,称为割集取边法。它在理论上将包括现有的Prim算法、Sollin算法、Kruskal算法等特例。文中还通过论证,对Sollin算法的条件作了减弱。它也将有助于构造新的具体算法,文中给出的生成树调整法即为一例。割集取边法可看作是回路去边法(即3]中破圈法)的一种对偶形式。最后,本文对经常遇到的平面极小树指出了几点特殊的性质。