最小生成树问题的扩展

《最小生成树问题的扩展》由会员分享，可在线阅读，更多相关《最小生成树问题的扩展（7页珍藏版）》请在金锄头文库上搜索。

1、最小生成树问题的拓展最小生成树问题的拓展 摘要摘要 本文主要论述最小生成树问题中的两类拓展最小度限制生成树和次小生成树。 首先分别介绍了这两类拓展问题的模型，然后提出了求解这两类问题的算法，最后，通过一些例子分析其在实际问题中的应用。 关键字关键字 生成树 拓展 度限制 正文正文 最小生成树是信息学竞赛中的经典问题， 但近年来， 竞赛中的题目不再局限于这类经典 模型，难度大大增加。为解决这些问题，我们必须对这些经典模型加以拓展。拓展的类型很 多，本文主要论述其中的两类最小度限制生成树和次小生成树。 1 最小生成树最小生成树 1 1.1.1 最小生成树的定义最小生成树的定义 设 G=(V,E,)

2、是连通的无向图，G 中权值和最小的生成树称为最小生成树。 1 1.2.2 求解最小生成树的算法求解最小生成树的算法 求最小生成树，比较常用的算法有 Prim 算法和 Kruskal 算法。前者借助 Fibonacci 堆可 以使复杂度降为 O(Vlog2V+E)，后者一般应用于稀疏图，其时间复杂度为 O(Elog2V)。 2、最小度限制生成树、最小度限制生成树 2.1、最小度限制、最小度限制生成生成树的定义树的定义 对于一个加权的无向图， 存在一些满足下面性质的生成树： 某个特殊的结点的度等于一 个指定的数值。最小度限制生成树就是满足此性质且权值和最小的一棵生成树。 把它抽象成数学模型就是：

3、设设 G=(V,E,)是连通的无向图，是连通的无向图， v0 V 是特别指定的一个顶点是特别指定的一个顶点,k 为给定的一个正整数。为给定的一个正整数。 如果如果 T 是是 G 的一个生成树且的一个生成树且 dT(v0)=k， 则称， 则称 T 为为 G 的的 k 度限制生成树。度限制生成树。 G 中权值和最小的中权值和最小的 k 度限制生成树称为度限制生成树称为 G 的最小的最小 k 度生成树。度生成树。 2.2、求解最小度限制生成树的算法、求解最小度限制生成树的算法 约定： T 为图 G 的一个生成树， T+a-b 记作(+a,-b)， 如果 T+a-b 仍然是一个生成树， 则称(+a,-

4、b) 是 T 的一个可行交换。 引理 1：设 T1,T2是图 G 的两个不同的生成树， E(T1)E(T2)=a1,a2,an,E(T2)E(T1)=b1,b2,bn,则存在一个排序 bi1,bi2,bin,使得 T2+ej-fij (j=1,2,n)仍然是 G 的生成树。 定理定理 1：设：设 T 是是 G 的的 k 度限制生成树，则度限制生成树，则 T 是是 G 的最小的最小 k 度限制度限制生成生成树当且仅当下面三树当且仅当下面三 个条件同时成立：个条件同时成立： 对于对于 G 中任何两条与中任何两条与 v0关联的边所产生的关联的边所产生的 T 的可行交换都是不可改进的。的可行交换都是不

5、可改进的。 对于对于 G 中任何两条与中任何两条与 v0不关联的边所产生的不关联的边所产生的 T 的可行交换都是不可改进的。的可行交换都是不可改进的。 对于对于 T 的任何两个可行交换的任何两个可行交换(+a1,-b1)和和(+a2,-b2)，若，若 a1,b2与与 v0关联，关联，b1,a2不于不于 v0关联，则有关联，则有(b1)+(b2)(a1)+(a2) 证明：必要性 设 T 是最小 k 度限制生成树，则,显然成立。 以下证明 ：由, 可知如果(+a1,-b2)和(+a2,-b1)都是 T 的可行交换，则有(b2)(a1),(b1) (a2)，故(b1)+(b2)(a1)+(a2);

6、否则，或者(+a1,-b2)或者(+a2,-b1)不是 T 的 可行交换，根据引理 1，T=T+a1,a2-b1,b2仍然是 T 的 k 度限制生成树，则 (T)(T),故(b1)+(b2)(a1)+(a2)。 充分性 设 T 是 k 度限制生成树且满足, ， 假如有另一个 k 度限制生成树T， (T)0，因而，在 T 的这 n 个可行交换中，一定存在某个可以改进的交换（+ai,-bi） 。由于 T 满足, 则 ai,bi若同时与 v0关联或不关联都是不可改进的。也就是说，ai和 bi中必定恰好 有一个不与 v0关联。不妨设 ai与 v0无关联，因为 DT(v0)也等于 k，所以必存在 另一个

7、交换(+aj,-bj),满足aj与v0关联， bj与v0无关联， 且(bi)(ai)+(bj) (aj)0,此与矛盾。因此，T是不存在的，即 T 是 G 的最小 k 度限制生成 树。 定理定理 2： 设： 设 T 是是 G 的最小的最小 k 度限制生成树，度限制生成树， E0是是 G 中与中与 v0有关联的边的集合，有关联的边的集合， E1=E0E(T)， E2=E(T)E0，A=(+a,-b)| aE1,bE2，设，设(a)(b)=min(a)(b)| (+a,-b)A， 则则 T+a-b是是 G 的一个最小的一个最小 k+1 度限制生成树。度限制生成树。 如何求最小 k 度限制生成树呢？

8、首先考虑边界情况。先求出问题有解时 k 的最小值：把 v0点从图中删去后，图中可能会出现 m 个连通分量，而这 m 个连通分量必须通过 v0来连接，所以，在图 G 的所有生成树中 dT(v0)m。也就是说，当 km 时，问题无解。 再根据上述定理，得出算法的框架： 下面分别考虑每一步 首先，将 v0和与之关联的边分别从图中删去，此时的图可能不再连通，对各个连通分量， 分别求最小生成树。 接着， 对于每个连通分量 V， 求一点 v1， v1V,且(v0,v1)=min(v0,v)| vV，则该连通分量通过边(v1,v0)与 v0相连。于是，我们就得到了一个 m 度限制生成树， 不难证明，这就是最

9、小 m 度限制生成树。 这一步的时间复这一步的时间复杂度为杂度为 O(Vlog2V+E) 我们所求的树是无根树，为了解题的简便，把该树转化成以我们所求的树是无根树，为了解题的简便，把该树转化成以 v0为根的有根树。为根的有根树。 假设已经得到了最小 p 度限制生成树，如何求最小 p+1 度限制生成树呢？ 根据定理 2， 最小 p+1 度限制生成树肯定是由最小 p 度限制生成树经过一次可行交换(+a1,-b1) 得到的。我们自然就有了一个最基本的想法枚举！但是，简单的枚举，时间复杂度高达 O(E2)，显然是不能接受的。深入思考不难发现，任意可行的交换，必定是一条边跟 v0关联， 另一条与 v0无

10、关，所以，只要先枚举与 v0关联的边，再枚举另一条边，然后判断该交换是 否可行，最后在所有可行交换中取最优值即可。于是时间复杂度降到了 O(VE)，但这仍然不 能令人满意。进一步分析，在原先的树中加入一条与 v0相关联的边后，必定形成一个环。 若想得到一棵 p+1 度限制生成树，需删去一条在环上的且与 v0无关联的边。删去的边的权 值越大，则所得到的生成树的权值和就越小。如果每添加一条边，都需要对环上的边一一枚 举，时间复杂度将比较高，因为有不少边重复统计多次（下图中红色的边统计了多次） 。 1 先求出最小 m 度限制生成树； 2由最小m度限制生成树得到最小m+1度限制生成树; 3 当 dT(

11、v0)=k 时停止。 这里，动态规划就有了用武之地。设 Best(v)为路径 v0v 上与 v0无关联且权值最大的边。 定义 father(v)为 v 的父结点，动态转移方程：Best(v)=max(Best(father(v),(father(v),v)， 边界条件为 Bestv0=-，Bestv=-| (v0,v)E(T)。 状态共|V|个，状态转移的时间复杂度 O(1)，所以总的时间复杂度为 O(V)。 故由最小故由最小 p 度限制生成树得到最小度限制生成树得到最小 p+1 度限制生成树的时间复杂度为度限制生成树的时间复杂度为 O(V)。 综上，求最小综上，求最小 k 度限制生成树算法总

12、的时间复杂度为度限制生成树算法总的时间复杂度为 O(Vlog2V+E+kV)。 3 3、次小生成树、次小生成树 3.3.1 1、次小生成树的定义、次小生成树的定义 设 G=(V,E,w)是连通的无向图，T 是图 G 的一个最小生成树。如果有另一棵树 T1，满 足不存在树 T,（T）（T1） ，则称 T1是图 G 的次小生成树。 3.23.2、求解次小生成树的算法、求解次小生成树的算法 约定： 由 T 进行一次可行交换得到的新的生成树所组成的集合， 称为树 T 的邻集,记为 N(T)。 定理定理 3：设：设 T 是图是图 G 的最小生成树，如果的最小生成树，如果 T1满足满足(T1)=min(T

13、)| TN(T),则则 T1是是 G 的次小生成树。的次小生成树。 证明：如果 T1不是 G 的次小生成树，那么必定存在另一个生成树 T,T=T 使得 (T)(T)(T1)，由 T1的定义式知 T 不属于 N(T)，则 E(T)E(T)=a1,a21,at，E(T)E(T)=b1,b2,bt，其中 t2。根据引理 1 知，存在一 个排列 bi1,bi2,bit，使得 T+aj-bij仍然是 G 的生成树，且均属于 N(T),所以(aj)(bij)， 所以(T)(T+aj-bij)(T1)，故矛盾。所以 T1是图 G 的次小生成树。 通过上述定理，我们就有了解决次小生成树问题的基本思路。 首先先

14、求该图的最小生成树 T。时间复杂度时间复杂度 O(Vlog2V+E) 然后，求 T 的邻集中权值和最小的生成树，即图 G 的次小生成树。 如果只是简单的枚举，复杂度很高。首先枚举两条边的复杂度是 O(VE)，再判断该交换是否 可行的复杂度是 O(V)，则总的时间复杂度是 O(V2E)。这样的算法显得很盲目。经过简单的 分析不难发现，每加入一条不在树上的边，总能形成一个环，只有删去环上的一条边，才能 保证交换后仍然是生成树，而删去边的权值越大，新得到的生成树的权值和越小。我们可以 以此将复杂度降为 O(VE)。这已经前进了一大步，但仍不够好。 回顾上一个模型最小度限制生成树， 我们也曾面临过类似

15、的问题， 并且最终采用动态规 划的方法避免了重复计算，使得复杂度大大降低。对于本题，我们可以采用类似的思想。首 先做一步预处理，求出树上每两个结点之间的路径上的权值最大的边，然后，枚举图中不在 树上的边，有了刚才的预处理，我们就可以用 O(1)的时间得到形成的环上的权值最大的边。 如何预处理呢？因为这是一棵树，所以并不需要什么高深的算法，只要简单的 BFS 即可。 预处理所要的时间复杂度为 O(V2)。 这样，这一步时间复杂度降为这样，这一步时间复杂度降为 O(V2)。 综上所述，次小生成树的时间复杂度为 O(V2)。 4、实际问题、实际问题中的应用中的应用 4.1 野餐计划野餐计划 矮人虽小却喜欢乘坐巨大的轿车，轿车大到可以装下无论多少矮人。某天，N(N20) 个矮人打算到野外聚餐。为了集中到聚餐地点，矮人 A 要么开车到矮人 B 家中，留下自己 的轿车在矮人 B 家，然后乘坐 B 的轿车同行；要么直接开车到聚餐地点，并将车停放在聚 餐地。 虽然矮人的家很大，可以停放无数量轿车，但是聚餐地点却最多只能停放 K 辆轿车。 现在给你一张加权无向图，它描述了 N 个矮人的家和聚餐地点，要你求出所有矮人开车的 最短总路程。 解答解答这是一个比较明显的度限制