1.2節(jié) Paths, Cycles, and Trees講了關(guān)于路、圈、樹的幾個(gè)基本成果。

定理：

TH3：關(guān)于連通分量的斷言

TH4：圖是二分圖 iff 它不含奇數(shù)長的圈。

TH5：圖是森林 iff 每個(gè)頂點(diǎn)對(x,y)包含至多一條x-y路。

TH6：關(guān)于樹的斷言

書中給出兩種建生成樹的方式。一是廣度優(yōu)先，從而引出了直徑的概念: diamG = maxx,yd(x,y)，頂點(diǎn)：radG=minx?maxy?d(x,y)；二是從一個(gè)頂點(diǎn)開始，每次加一條邊建立。不難證明推論8：A tree of order n has size n-1.

下面的部分是產(chǎn)生一個(gè)圖的最經(jīng)濟(jì)生成樹的算法（也就是最小生成樹）。分為四種：

1. 每次都加入最小的邊，不能成圈

2. 每次都刪去最大的邊，保持連通

3. Prim算法

4. （沒有相等兩權(quán)時(shí)適用）每個(gè)點(diǎn)都選擇連接最小邊。這一過程重復(fù)進(jìn)行

不難證明，當(dāng)沒有邊權(quán)相等時(shí)，所形成的最小生成樹是唯一的。

祝大家新年快樂！