1 聚类问题：最大间隔的K聚类。我们定义一个K聚类的间隔是处在不同聚类中的任意一对点之间的最小距离。一个自然的目标是寻求具有最大可能间隔的k聚类。
这个问题的算法与Kruskal算法非常相似，首先每一个点都是一个聚类，然后依次按照Kruskal进行计算。。。相当于在Kruskal中删除了k-1条最贵的边。
2 假设给定一个连通图G，假定边的费用都是不同的，G有n个顶点和m条边，指定了G的一条特定的边e，给出一个运行时间在O(m+n)的算法来确定e是否包含在G的一棵最小生成树里。
算法现在就已经很显然了，我们通过从G中删除所有权比e大的边，（包括e）然后使用看一下e中的两个端的是否联通。当前仅当没有这样一条路径的时候，e属于一棵最小生成树。
3 看一下最小生成树的两个性质：
割性质：当e是从某个集合S跨到补集V-S的最便宜的边，那么它在每一颗最小生成树里。
圈性质：如果e是某个圈C上最贵的边，那么它不在最小生成树里。
4 一个课后问题：
给定一个最短路问题，但是边权是一个到达时间的函数(边权统一为时间的量纲， 函数单调递增)，此时仍然是Dijkstra算法，Dijkstra 算法实质就是一个宽度优先搜索。
5 给定一棵完全二叉树，然后每个边有权值。要求修改边，然后使得跟到每个叶子节点的距离相同，要求修改的和最小？给出一个算法，这个在电路设计中就是同时性的要求。
这个是个非常不错的算法。还是一个递归的过程：
6
给定一个连通图，他的边的费用都是不同的，证明G有唯一的一棵最小生成树。
如果G有两棵最小生成树，则T 和P，必然有不同的边，把T与P不同的边加入到P中，必然形成圈。