【资料图】

1、 最优树问题(optimal spanning tree problem)是一类组合优化问题，设G=(V，E)是一个图，V为节点集，E为边集，对任何e∈E，它的权w(e)为已知，在G上，求一个支撑树T使得W(T)=∑e∈Tw(e)为最优(即最大或最小)，这就是最优树问题，或具体地，最大树问题或最小树问题。

2、求G上的最小支撑树有克鲁斯卡尔算法，其要旨是：首先，选取权最小的一条边;然后，对于所有未被选取的边，在那些与已选取的边不产生圈的边中取一个权最小的；如此下去，一直到不能进行为止，从而，这样选出来的所有边构成G的一个支撑树，并且其上边的权之总和为最小，它是一种典型的贪婪算法，若将最优树问题中的支撑树改为G的连通的支撑子图，则这时被称为最优连结问题，最小连结问题与最小树问题是等价的。

标签：