1 聚類問題：最大間隔的K聚類。我們定義一個K聚類的間隔是處在不同聚類中的任意一對點之間的最小距離。一個自然的目標是尋求具有最大可能間隔的k聚類。
這個問題的算法與Kruskal算法非常相似，首先每一個點都是一個聚類，然后依次按照Kruskal進行計算。。。相當于在Kruskal中刪除了k-1條最貴的邊。
2 假設給定一個連通圖G，假定邊的費用都是不同的，G有n個頂點和m條邊，指定了G的一條特定的邊e，給出一個運行時間在O(m+n)的算法來確定e是否包含在G的一棵最小生成樹里。
算法現(xiàn)在就已經(jīng)很顯然了，我們通過從G中刪除所有權(quán)比e大的邊，（包括e）然后使用看一下e中的兩個端的是否聯(lián)通。當前僅當沒有這樣一條路徑的時候，e屬于一棵最小生成樹。
3 看一下最小生成樹的兩個性質(zhì)：
割性質(zhì)：當e是從某個集合S跨到補集V-S的最便宜的邊，那么它在每一顆最小生成樹里。
圈性質(zhì)：如果e是某個圈C上最貴的邊，那么它不在最小生成樹里。
4 一個課后問題：
給定一個最短路問題，但是邊權(quán)是一個到達時間的函數(shù)(邊權(quán)統(tǒng)一為時間的量綱， 函數(shù)單調(diào)遞增)，此時仍然是Dijkstra算法，Dijkstra 算法實質(zhì)就是一個寬度優(yōu)先搜索。
5 給定一棵完全二叉樹，然后每個邊有權(quán)值。要求修改邊，然后使得跟到每個葉子節(jié)點的距離相同，要求修改的和最小？給出一個算法，這個在電路設計中就是同時性的要求。
這個是個非常不錯的算法。還是一個遞歸的過程：
6
給定一個連通圖，他的邊的費用都是不同的，證明G有唯一的一棵最小生成樹。
如果G有兩棵最小生成樹，則T 和P，必然有不同的邊，把T與P不同的邊加入到P中，必然形成圈。