【定理14.*】：对连通带权图G=(W,E)运行Prim算法，生成的树是最小生成树。 【证】：设该连通带权图有n个顶点，m条边。T是算法中边的集合，下面对T中的边数k进 行归纳法，证明生成树是最小的。 归纳假设是：当T有k条边时，T包含在某棵最小生成树中。 当k=0时，T是一个空集，由于连通带权图存在最小生成树，所以当m=0时，假设 成立。现在假设k=时，假设成立，即T包含在一棵最小生成树T'中。下面考虑 k=i+1。 设U是Prim算法给出的顶点集合，假设(u,v)是下一条将被加入到T中的边，其中u在 U中，v不在U中。如果(u,v)在T'中，那么归纳假设成立，证明完成。下面假设(u,v) 不在T'中，由于T'是一棵最小生成树，所以T'中存在一条从到v的通道。另外因为 u∈U,v庄U,所以此条通道一定包含一条边e,它的一个顶点在U中而另外一个顶点不 在U中。 从上面分析，我们知道Prim算法选择了边(u,v)而不是边e,所以(u,v)的权一定不大 于e的权。于是，如果将(u,v)加入到T'中，并从T'中去掉e构成T",那么T"的权不会增 加。由于T"是连通的且有n-1条边，所以它是一棵最小生成树。但T”包含了TU(u,v)的 i+1条边，这就对i+1证明了归纳假设。 由数学归纳法可知，Pm算法产生的树T总是包含在一棵最小生成树中。当算法结束 且n-1条边时，此时T即是最小生成树。总上，Prim算法产生一棵最小生成树。 习题14.2补二道习题 l3.分别利用Kruskal算法和Prim算法求下图的最小生成树。 G 14.利用Prim算法求出下图的最小生成树。【定理 14.*】：对连通带权图G  (V ,E) 运行 Prim 算法，生成的树是最小生成树。 【证】：设该连通带权图有 n 个顶点，m 条边。T 是算法中边的集合，下面对T 中的边数 k 进 行归纳法，证明生成树是最小的。 归纳假设是：当T 有 k 条边时，T 包含在某棵最小生成树中。 当 k  0 时，T 是一个空集，由于连通带权图存在最小生成树，所以当 m  0时，假设 成立。现在假设 k  i 时，假设成立，即T 包含在一棵最小生成树T 中。下面考虑 k  i 1。 设U 是 Prim 算法给出的顶点集合，假设(u, v) 是下一条将被加入到T 中的边，其中u 在 U 中，v 不在U 中。 如果(u, v) 在T 中，那么归纳假设成立，证明完成。下面假设(u, v) 不在T 中，由于T 是一棵最小生成树，所以T 中存在一条从 u 到 v 的通道。另外因为 u U,v U ，所以此条通道一定包含一条边 e ，它的一个顶点在U 中而另外一个顶点不 在U 中。 从上面分析，我们知道 Prim 算法选择了边(u, v) 而不是边e ，所以(u, v) 的权一定不大 于e 的权。于是，如果将(u, v) 加入到T 中，并从T 中去掉e 构成T，那么T的权不会增 加。由于T是连通的且有 n 1条边，所以它是一棵最小生成树。但T包含了T (u,v) 的 i 1条边，这就对i 1证明了归纳假设。 由数学归纳法可知，Prim 算法产生的树T 总是包含在一棵最小生成树中。当算法结束 且 n 1条边时，此时T 即是最小生成树。总上，Prim 算法产生一棵最小生成树。 习题 14.2 补二道习题 13．分别利用 Kruskal 算法和 Prim 算法求下图的最小生成树。 a b g h i G c d e f 4 8 7 8 11 7 1 2 6 4 14 9 10 2 14．利用 Prim 算法求出下图的最小生成树