生成树专题
生成树算法
前置说明
- 如无特别说明，
n 表示图中节点数，m 表示图中边数。
生成树
定义：一个无向连通图中，选取边集的一个子集作为新边集使得图变为一个连通且不含环路的图，这个新图称为原图的一个生成树。
- 定理：生成树上任意两点间有且仅有一条路径。
证明：设存在两节点，这两节点之间在生成树上有多条路径，由于图为无向图，故这多条路径中任意两条路径构成环路，与生成树定义矛盾。若存在两节点，这两节点之间在生成树上无路径，则生成树不连通，与生成树定义矛盾。证毕。
- 定理：生成树的边数
m=n-1 。证明：取一个节点作为根节点，则每个非根节点到根仅有一条路径，即每个非根节点仅对应一条到根的边，故边数为
m=n-1 。证毕。 - 定理：生成树上对任意两节点间连接一条边，则生成树出现环。
证明：由上述定理即得。
最小生成树
定义：一个无向连通图的所有生成树中，边权之和最小的生成树称为最小生成树。
- 定理：无向连通图中边权最小的边必定属于最小生成树边集。
证明：假设最小边权的边不属于最小生成树边集，则将该边加入最小生成树，由上述定理知此时最小生成树上形成环，删除环上最大边权的边，形成的新图必定为生成树，且边权和小于原边权和，与假设矛盾。证毕。
由上方定理可知：可以使用贪心法求最小生成树。每次寻找图中未被选取且边权最小的边，若加入此边，当前生成的图不会形成环路，则选取此边作为当前图中的一条边。当无法选取时形成的图为原图的最小生成树。
最小瓶颈生成树
定义：在无向连通图的所有生成树中，最大边权最小的生成树称为最小瓶颈生成树。
- 定理：最小生成树必定为最小瓶颈生成树。
证明：设一个最小生成树中存在一条边，其权值大于另一不同的最小瓶颈生成树，删除这条边，将最小生成树分为两部分，取一条最小瓶颈生成树中的边连接这两部分（这条边必定存在，因为最小生成树中被删除的边可以不被最小瓶颈生成树选取说明这两部分之间有多条路径。），则新树边权和小于原树，与原树为最小生成树矛盾。证毕。
次小生成树
定义：不与最小生成树相同的生成树中，边权和最小的生成树。
求法：对图求最小生成树，对于每条非树边
严格次小生成树：需要在求最大边权边时维护次大值，替换时若最大值与替换边权值相等则使用次大值替换。
最优比率生成树
定义略。
求法：0-1分数规划，二分答案求最大(小)生成树。