[科普中国]-最小枝杈树问题

基本内容

树：一个有k个连通分支且无圈的图为k-树或森林。即两个要求：第一是连通的，第二是不含圈的。这样的图很像一棵树，我们就形象地称之为“树”。例如图1所示。

树的性质：树的边数等于其顶点数减1；树的任意两个顶点之间恰有一条初级链相连接；在树中任意去掉一条边后，便得到一个不连通的图；在树中任意两个顶点之间添加一条新边，所得新图恰有一个初级圈。

枝杈树：若图 G 的生成子图 H 是树，则称 H 为 G 的枝杈树或支撑树。

最小枝杈树：设G=[V,E]是一个无向图，对每一条边 ∈E有一个长度C( ) ≥0,G的任意支撑树T各条边的长度之和称为树T的长度，记为C（T）。长度最小的支撑树称为最小树1。

相关定理

1.连通图的生成树一定存在2。

证明：给定连通图 G，若 G 无圈，则 G 本身就是自己的生成树。若 G 有圈，则任取 G 中一个圈C，记删去 C 中一条边后所得之图为 G。显然 G中圈 C 已经不存在，但 G仍然连通。若 G中还有圈，再重复以上过程，直到得到一个无圈的连通图 H。易知 H 是 G 的生成树。

2.设G=(V,E)是一个图，则下列命题等价于：

①G是树；
　　②G是无环图且G的任意两个顶点之间有唯一的一条路；
　　③G是无圈图且有|V|-1条边；
　　④G是连通图且有|V|-1条边；
　　⑤G是连通图且每一条边都是割边；
　　⑥G是无圈图，但在任意一对顶点间加上一条边后恰有一个圈。

3.设图G=(V，E)是一个树，|V|≥2，则G中至少有两个点的度为1（悬挂点）2。

证明:令p=( ) 是G中含边数最多的一条路，因|V|≥2，并且G是连通的，故 与 是不同的。则有d( )= d( )= 1。否则有d( )≥2，则存在边{ }使h≠2. 那么将出现G有圈或p不是最长路。同理可证d( )=1。

解决方法

一个简单连通图只要不是树，其生成树就不唯一，而且非常多。一般地，n 个顶点地完全图，其不同地生成树个数为 。因而，寻求一个给定赋权图的最小生成树，一般是不能用穷举法的。例如，30 个顶点的完全图有 个生成树， 有 42 位，即使用最现代的计算机，在我们的有生之年也是无法穷举的。所以，穷举法求最小生成树是无效的算法，必须寻求有效的算法。在求最小生成树的有效算法中，最著名的两个是 Kruskal（克罗斯克尔）算法和 Prim（普瑞姆）算法，其迭代过程都是基于贪婪法来设计的。

Kruskal 算法

Kruskal算法思想

在构造支撑树的过程中每一步都避开圈，同时要求所选择加入的边的权最小。

Kruskal 算法的直观描述

假设 是赋权图 G 的最小生成树， 中的边和顶点均涂成红色，初始时 G 中的边均为白色。
　　① 将所有顶点涂成红色；
　　② 在白色边中挑选一条权值最小的边，使其与红色边不形成圈，将该白色边涂红；
　　③ 重复②直到有 n-1 条红色边，这 n-1 条红色边便构成最小生成树 的边集合2。

Prim 算法

Prim 算法的思想
　　设 和 C( ) 分别为图 G 的最小生成树的边集及其权值，初始状态均为空，算法结束时 包含最小生成树的所有边，C( ) 表示最小生成树的权值。先指定一个顶点为初始访问点，记做 ，将 加到“通过点”的集合 V 中，然后找出跨接在“通过点”集合 与“未通过点”集合 之间权最小的边 e 作为“通过边”加入 中，并将 e 在 中的端点转到 中。重复上述过程直至 为止1。

Prim 算法的直观描述
　　假设 是赋权图 G 的最小生成树。任选一个顶点将其涂红，其余顶点为白点；在一个端点为红色，另一个端点为白色的边中，找一条权最小的边涂红，把该边的白端点也涂成红色；如此，每次将一条边和一个顶点涂成红色，直到所有顶点都成红色为止。最终的红色边便构成最小生成树 的边集合。

Prim和Kruskal的贪心策略是一样的，都是选取耗费最小的边，只不过选取的范围不同：对于Prim，其选取的边(u,v)必有一个顶点已经被覆盖，另一个顶点未被覆盖。而对于Kruskal,其选取的边(u,v)任意，只要这个边的加入不能使被覆盖的顶点构成回路1。

破圈法

破圈法思想：将图的全部边按照边权的大小从大到小排序，在原图的基础上，从前到后考察这些边，每考察一边，验证是否存在包含该边在内的初级圈。若有，将该边从边集中删除，否则保留。直到剩余子图为一树（可以以剩余的边数作为检验条件），否则在考察下一条边1。

破圈法的直观描述

任取一个圈，从圈中去掉一条权最大的边(如果有两条或两条以上的边都是权最大的边，则任意去掉其中一条)。在余下的图中，重复这个步骤，直至得到一个不含圈的图为止，这时的图便是最小枝杈树2。

应用

在工农业生产、交通运输、通讯和电力领域经常都能看到许多网络，如管道网、公路网、计算机通讯网、输电线网等。还有许多看不见的网络，如各种关系网、事物的相互冲突关系等等，这些网络都可归结为网络最优化问题3。常见的应用有电信网络（计算机网络、电话专用线网络、有线电视网络等等）的设计、低负荷运输网络的设计，使得网络中提供链接的部分（如铁路、公路 等）的总成本最小、高压输电线路网络的设计电器设备线路网络（如数字计算机系统）的设计、连接多个场所的管道网络设计等。

现实生活中有许多类似在城镇间架设的电话线、铺设管道、修筑道路的问题，通常在一些早期的发展阶段，由于技术或财力的局限，人们总是从节省材料或资金的角度，试图设计一个网络能够使得不同城镇均能被直接或间接的连接起来，使其总长度最短。例如：要在n个城市之间铺设光缆，主要目标是要使这 n 个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同，因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小枝杈树。