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