第6章 樹與生成樹
6.1 樹保留可達性，不保留多餘的環
樹是頂點非空、連通且無簡單環的有限簡單無向圖。連通給任兩點至少一條道路。若有兩條不同道路連接同一對端點，沿共同開頭走到第一次分岔，接著沿其中一條走到第一次再遇上另一條。這一段和另一條道路的對應段只在兩端相接，因此形成環。反過來，在非空圖中，若任兩點間恰有一條道路，圖必連通；若有環，環上相鄰兩點可由該邊或沿環的另一側相連，矛盾。
一棵至少兩點的樹必有度數為 1 的葉：取一條最長道路，端點若還有別的鄰點，鄰點不在道路上就可延長，在道路上則形成環。刪葉與它的唯一邊後仍連通無環，因其他兩點間的道路不可能經葉當中繼。以單點 0 條邊起算，歸納得 n 點樹有 n−1 條邊。
非空連通圖若有環，刪掉其中一邊。任何原本用到該邊的道路，都可改走環的其餘邊，得到同端點的 walk，再剪掉重複點成道路。因此刪邊後仍連通。有限次刪除後得到保留全部頂點的連通無環子圖，這就是生成樹。故非空連通的 n 點圖至少有 n−1 條邊；若恰有 n−1 條，原圖已是樹。無環圖有 c 個分量時，每個分量是一棵樹，合計 n−c 條邊。
6.2 四個例題
例題1 環上刪一邊不會斷開
圖 A 到 D 的邊為 AB、BC、AC、CD。刪 AC，還有 A→B→C；剩 AB、BC、CD 連成四點道路，沒有環且含全部頂點，是一棵生成樹。
例題2 只數 n−1 不足以判樹
在 A 到 D 上取 AB、BC、AC，邊數為 4−1，但前三點成環，D 孤立。對非空的 n 點圖，若已知連通，n−1 條邊即保證是樹；若已知無環，由 n−c=n−1 得 c=1，也可推出是樹。
例題3 森林可從分量讀邊數
頂點 A 到 G，邊 AB、BC、DE、DF。分量 ABC、DEF、G 都無環；邊數分別 2、2、0，合計 4=7−3。孤立點也是一棵單點樹。
例題4 生成樹不一定唯一
三角形 AB、BC、AC，任刪一邊都留下三點道路，故有三棵生成樹。原圖的環邊是選項，不是要保留的必要邊。
6.3 練習
- B10-C06-Q01 單點、零邊的圖是樹嗎？該點是葉嗎？
- B10-C06-Q02 七點樹的邊數及度數和？
- B10-C06-Q03 A 到 E，邊 AB、AC、AD、DE。列出葉。
- B10-C06-Q04 在上一題，B 到 E 的唯一道路？
- B10-C06-Q05 五點連通簡單圖有四條邊，必是樹嗎？
- B10-C06-Q06 五點無環圖有兩個連通分量，幾條邊？
- B10-C06-Q07 四邊形 AB、BC、CD、AD，刪 BC 後仍連通嗎？
- B10-C06-Q08 四點圖只有 AB、CD，是否有生成樹？
- B10-C06-Q09 從至少兩點的樹刪去任一邊，還能連通嗎？
- B10-C06-Q10 若是 n≥2 點的道路圖，有幾個葉？
6.4 完整解答
Q01
是樹：非空、自身可達、無環。該點度數是 0，本冊定義葉為度數 1，因此不是葉。
Q02
樹有 7−1=6 邊，每邊兩端，度數和 12。
Q03
A 度 3、D 度 2；B、C、E 度 1，因此葉是 B、C、E。
Q04
先從 B 到其唯一鄰點 A，再沿 AD、DE，為 B,A,D,E。樹性排除任何另一條道路。
Q05
是。若有環，刪一邊仍連通，只剩三邊，違反連通的五點圖至少四邊。
Q06
每個分量是樹，分量內點數各減一再加，等於 5−2=3。
Q07
是，B,A,D,C 是涵蓋四個頂點的道路，所以剩下是連通的三邊樹。
Q08
無。選子集合只會刪邊，不會創造跨分量的邊；保留全點的子圖不可能連通。
Q09
不能；若兩端仍有道路，加回被刪的邊便形成一個環，違反樹的無環性。
Q10
首尾各接一條邊，其餘點各接前後兩條。故只有兩端是葉；例如五點道路的葉是 A、E。