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中，必然形成圈。