这一讲介绍最小生成树。先看看什么是最小生成树。
首先我们有一个无向的连通 带权图，这个图的顶点集合是V，
它的边集是E，然后每一条边有一个权值。
比如说边e它的权值用w(e)来表示，
这就是无向带权图。那么这样图的一棵生成树
是包含了G的所有的顶点这样的一棵树。
这棵树各个边的权值之和， 我们记作T的权值W(T)，
是这棵树的权，我们希望求得一棵树，
它这个权值达到最小，这样的树就叫最小 生成树，这是问题的输入，
这棵最小生成树就是问题的输出。下面我们看一棵最小
生成树的例子。这是一棵最小生成树它的原始的图，
就是这个图，它里面一共有六个顶点， 然后它的权值都标在这个
边的位置上，这是它的边，一共有10条边。
那么这样的一个图，它的最小生成树就是下面这个图。
它所选择的边就是这种红颜色的边，这是原图
的一棵的最小生成树，它的权值就是把这些个边的长度
全部加起来就是它的权值，这是一棵最小的生成树。
下面我们看一下生成树的性质。
这是一个命题给出来的， G是一个n阶的连通图，n阶就是它的顶点数是n。
那么T是G的生成树， 当且仅当满足下面的条件，一个是无圈，无圈就是在T中没有回路。
而且T恰恰好是n减1条边，这是它构成生成树的
充分必要条件，这是第一个结果。第二个结果，
如果T是G的生成树，有一条不在树中的边 e，如果我们把这条边加到这棵树上去，
这棵树和这个边构成的图一定含有一个圈，圈就是回路。
所以当你加一条不是树的边到树里去，就一定会出现一条回路。
我们看一下，这假定是 图G的一棵生成树，现在它是没有回路的，没有圈。
然后我们加上一条不在树中的边，比如说加这个蓝颜色的边，
这就出现了一条这个回路，这就是这个第二个结论的含义。
下面我们看看还有第三个结果，
就是说刚才我们看到在树中加上一条非树边，就会构成一个圈。
我们要把这个圈中任意去掉一条边， 就可以得到G的另外一棵生成树T'。
你比如说这是刚才那个图，我们加了
这个不在树中的边以后，这样形成了一个圈， 然后我们把这个圈中的任何一条边去掉，
比如说我们把这条边去掉，这样就又构成了原图的
一棵生成树。这个就是通过用新的边，这个蓝颜色的边
替换了原来的这条绿色的边，得到 了一棵新的树T'，这是说由树T
得到新的树T'的方法，就可以采用这样的方法。
下面我们看看这些生成树的性质，怎么样的来应用。
首先算法的步骤是来选择边，根据刚才的命题的第一个结果，
选边的时候不能形成回路，这是构成树的必要条件，而且截至的
条件，边数选到n减1条就可以截至了，因为既不构成回路，边数正好是n减1条，
这就说明它已经得到了一棵生成树，这是算法步骤是根据我们的前面
的性质来决定了算法的结束条件和约束条件。然后我们再看一看
改进生成树的方法。如果在一棵生成树中加上一个非树边会形成
一个回路，然后我们去掉这个回路中的另外一条树中的边ei，
这就得到了一棵新的生成树T'，这是刚才那个命题的结果。
那么T'的权值和原来那棵树T的权值它们的差值是多少呢？
等于加入这条边的权值减掉去掉 那条边的权值。那么如果我加入这条边的权值更小，
就是说W(e)小于W(ei)在这个前提下就可以推出来，
新构造的这棵树的权值W(T') 要小于W(T)，所以我们在
构造这棵新的生成树，如果使得它的权减小，就用
边，权更小的边来替换原来树中的边就可以做到，这是改进生成树
的方法。下面我们看看怎么样来求最小的生成树。
这是原始问题，给定的输入是一个带权图，
连通的，然后求它的一棵最小的生成树。
这里边的算法我们会有两个算法，一个是Prim算法，一个是
Kruskal算法，这是两个重要的算法。那么生成树 在网络中有着重要的应用。
它是把这些结点能够连通起来的一个最简单的方式。
它在实际中有着重要的应用。下边把这一讲小结一下。
首先我们先介绍什么叫生成树，什么叫生成树的权。
然后我们给出了最小生成树的定义，
就是具有最小权值的这棵生成树就是最小生成树。
最后我们介绍了生成树的性质。
通过这样的性质来设计算法，给出算法的结束条件。
另外也通过这样的性质我们来改造一棵树，使得它的权值变得更小。
变成更好的生成树，它都是根据这个性质来做的。
这是这一讲的主要内容。
Wanling QuProfessor
