什么是最小枝杈树问题介绍
又叫最小支撑树问题、最小生成树问题，是指在一个网络规划中，从一个起点出发到所有接点，找出一条或几条路线，以使在这样一些路线中所采用的全部支线的总长度最小的规划问题。
最小枝杈树问题基本内容
树：一个有k个连通分支且无圈的图为k-树或森林。即两个要求：第一是连通的，第二是不含圈的。这样的图很像一棵树，我们就形象地称之为“树”。例如图1所示。
树的性质：树的边数等于其顶点数减1；树的任意两个顶点之间恰有一条初级链相连接；在树中任意去掉一条边后，便得到一个不连通的图；在树中任意两个顶点之间添加一条新边，所得新图恰有一个初级圈。
枝杈树：若图 G 的生成子图 H 是树，则称 H 为 G 的枝杈树或支撑树。
最小枝杈树：设G=是一个无向图，对每一条边
∈E有一个长度C(
) ≥0,G的任意支撑树T各条边的长度之和称为树T的长度，记为C（T）。长度最小的支撑树称为最小树。
最小枝杈树问题相关定理
1、连通图的生成树一定存在。
证明：给定连通图 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（悬挂点）。
证明:令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 条红色边便构成最小生成树
的边集合。
最小枝杈树问题Prim 算法
Prim 算法的思想
设
和 C(
) 分别为图 G 的最小生成树的边集及其权值，初始状态均为空，算法结束时
包含最小生成树的所有边，C(
) 表示最小生成树的权值。先指定一个顶点为初始访问点，记做
，将
加到“通过点”的集合 V 中，然后找出跨接在“通过点”集合
与“未通过点”集合
之间权最小的边 e 作为“通过边”加入
中，并将 e 在
中的端点转到
中。重复上述过程直至
为止。
Prim 算法的直观描述
假设
是赋权图 G 的最小生成树。任选一个顶点将其涂红，其余顶点为白点；在一个端点为红色，另一个端点为白色的边中，找一条权最小的边涂红，把该边的白端点也涂成红色；如此，每次将一条边和一个顶点涂成红色，直到所有顶点都成红色为止。最终的红色边便构成最小生成树
的边集合。
Prim和Kruskal的贪心策略是一样的，都是选取耗费最小的边，只不过选取的范围不同：对于Prim，其选取的边(u,v)必有一个顶点已经被覆盖，另一个顶点未被覆盖。而对于Kruskal,其选取的边(u,v)任意，只要这个边的加入不能使被覆盖的顶点构成回路。
最小枝杈树问题破圈法
破圈法思想：将图的全部边按照边权的大小从大到小排序，在原图的基础上，从前到后考察这些边，每考察一边，验证是否存在包含该边在内的初级圈。若有，将该边从边集中删除，否则保留。直到剩余子图为一树（可以以剩余的边数作为检验条件），否则在考察下一条边。
破圈法的直观描述
任取一个圈，从圈中去掉一条权最大的边(如果有两条或两条以上的边都是权最大的边，则任意去掉其中一条)。在余下的图中，重复这个步骤，直至得到一个不含圈的图为止，这时的图便是最小枝杈树。
最小枝杈树问题应用
在工农业生产、交通运输、通讯和电力领域经常都能看到许多网络，如管道网、公路网、计算机通讯网、输电线网等。还有许多看不见的网络，如各种关系网、事物的相互冲突关系等等，这些网络都可归结为网络最优化问题。常见的应用有电信网络（计算机网络、电话专用线网络、有线电视网络等等）的设计、低负荷运输网络的设计，使得网络中提供链接的部分（如铁路、公路 等）的总成本最小、高压输电线路网络的设计电器设备线路网络（如数字计算机系统）的设计、连接多个场所的管道网络设计等。
现实生活中有许多类似在城镇间架设的电话线、铺设管道、修筑道路的问题，通常在一些早期的发展阶段，由于技术或财力的局限，人们总是从节省材料或资金的角度，试图设计一个网络能够使得不同城镇均能被直接或间接的连接起来，使其总长度最短。例如：要在n个城市之间铺设光缆，主要目标是要使这 n 个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同，因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小枝杈树。