解：过程如下： 3 Vs 3 3 5 5 5 6 7
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 7 解：过程如下： 1 v5 v8 2 1 v1 v5 v8 2 3 1 v1 v4 v5 v8 3 v7 2 1 5 v1 v4 v5 v8 3 v7 2 1 5 6 v1 v4 v5 v8 v3
6 6 8 定理1由克鲁斯克尔算法得到的任何生成树一定是最小 生成树。（证明略） 8
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 8 3 v7 2 1 5 6 v1 v4 v5 v8 v3 v6 8 3 v7 2 1 5 6 v1 v4 v5 v8 v3 v6 8 v2 9 定理1 由克鲁斯克尔算法得到的任何生成树一定是最小 生成树。(证明略)
例2在一个边赋权G中，下面算法是否可以产生有最小 权值的生成路？为什么？ 算法：(I)选一条边e,使得w(e)尽可能小； (2)若边e1,e2…,e已经选定，则用下述方法从D(e1,e;}中 选取边e+1: (a)G(e1e2,e:,et1)]为不相交路之并； (b)w(e+i)是满足(a)的尽可能小的权。 (3)当(2)不能继续执行时停止。 解：该方法不能得到一条最小生成路
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 9 例2 在一个边赋权G中，下面算法是否可以产生有最小 权值的生成路？为什么？ 算法: (1) 选一条边e1,使得w(e1)尽可能小； (2) 若边e1,e2,…,ei已经选定，则用下述方法从E\｛e1,..,ei｝中 选取边ei+1： (a) G[｛ e1,e2,…,ei ,ei+1｝]为不相交路之并； (b) w(ei+1)是满足(a)的尽可能小的权。 (3)当 (2)不能继续执行时停止。 解：该方法不能得到一条最小生成路
例如，在下图G中我们用算法求生成路： 用算法求出的生成路为： 10
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 10 例如，在下图G中我们用算法求生成路： 3 1 2 2 3 4 3 6 6 7 9 10 用算法求出的生成路为： 1 2 2 6 9 3
直接在图中选出的一条生成路为： 后者的权值小于前者。 (二)、管梅谷的破圈法 在克鲁斯克尔算法基础上，我国著名数学家管梅谷 教授于1975年提出了最小生成树的破圈法
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 11 直接在图中选出的一条生成路为： 1 2 3 3 6 6 后者的权值小于前者。 (二)、管梅谷的破圈法 在克鲁斯克尔算法基础上，我国著名数学家管梅谷 教授于1975年提出了最小生成树的破圈法