圖論第11章 - 樹 (Trees) 考前重點複習

快速公式參考

一、基本定義與概念

樹 Tree

樹是一種連通且無環的圖。

樹的例子 5個頂點,4條邊 非樹(有環) 有環,不是樹
有根樹 Rooted Tree

指定一個頂點作為根(root)的樹,具有層次結構。

森林 Forest

由多棵樹組成的圖(可以不連通)。

二、有根樹的重要術語

有根樹術語示意圖 根 Root 內部 內部 葉子 葉子 內部 葉子 葉子 葉子 Leaves 兄弟 Siblings 子節點 Children 父節點
術語 英文 定義 例子
根 Root 樹的最上層頂點 上圖紅色頂點
內部頂點 Internal Vertex 有子節點的頂點 上圖藍色頂點
葉子 Leaf / Leaves 沒有子節點的頂點 上圖綠色頂點
子節點 Children 某頂點直接向下連接的頂點 一個頂點下方直接相連的點
父節點 Parent 某頂點直接向上連接的頂點 一個頂點上方直接相連的點
兄弟節點 Siblings 有相同父節點的頂點 同一個父節點的子節點們
祖先 Ancestors 從某頂點到根路徑上的所有頂點 往上追溯到根的所有點
後代 Descendants 某頂點下方的所有頂點 某點下方的所有子孫節點

三、m-元樹相關概念

m-元樹 m-ary Tree

每個內部頂點最多有m個子節點的有根樹。

完滿m-元樹 Full m-ary Tree

每個內部頂點恰好有m個子節點的有根樹。

完全m-元樹 Complete m-ary Tree

完滿m-元樹且所有葉子都在同一層。

二元樹 (m=2) 每個內部頂點有2個子節點
三元樹 (m=3) 每個內部頂點有3個子節點

四、重要公式整理

1. 樹的基本性質

邊數 = 頂點數 - 1

E = V - 1

範例:

問:一棵有10,000個頂點的樹有多少條邊?

答:10,000 - 1 = 9,999條邊

2. 完滿m-元樹的葉子數公式

l = [(m-1)n + 1] / m

其中:l = 葉子數,n = 總頂點數,m = 每個內部頂點的子節點數

範例:

問:一棵有100個頂點的完滿3-元樹有多少個葉子?

答:l = [(3-1)×100 + 1] / 3 = [200 + 1] / 3 = 201 / 3 = 67個葉子

3. 森林的邊數公式

邊數 = 總頂點數 - 樹的數量

E = n - t

範例:

問:一個包含5棵樹、總共50個頂點的森林有多少條邊?

答:50 - 5 = 45條邊

4. 完滿二元樹的特殊性質

葉子數 = 內部頂點數 + 1

l = i + 1

五、判斷樹的方法

如何判斷一個圖是否為樹?

  1. 檢查連通性:所有頂點必須相連
  2. 檢查是否有環:不能有任何迴路
  3. 檢查邊數:必須恰好有 n-1 條邊(n是頂點數)

三個條件必須同時滿足!

六、樹的高度與層次

高度 Height

從根到最遠葉子的路徑長度(邊數)。

層 Level

頂點到根的距離。根在第0層。

高度與層次示意圖 第0層 第1層 第2層 第3層 高度 = 3

七、考試技巧總結

解題步驟建議

  1. 看清題目要求:是要判斷、計算還是畫圖?
  2. 識別題型:
    • 樹的判斷 → 檢查連通性和環
    • 計算題 → 套用對應公式
    • 術語題 → 根據定義找答案
  3. 畫圖輔助:特別是有根樹的題目
  4. 驗證答案:檢查是否符合樹的基本性質
常見題型速查表
題型 關鍵字 使用公式/方法
判斷是否為樹 Which graphs are trees? 檢查連通、無環、邊數=n-1
計算邊數 How many edges? E = V - 1
計算葉子數 How many leaves? l = [(m-1)n + 1]/m
森林問題 forest of t trees 邊數 = n - t
術語辨識 parent, children, siblings等 根據定義判斷

八、必背英文術語對照

基本術語

  • Tree - 樹
  • Graph - 圖
  • Vertex/Vertices - 頂點
  • Edge - 邊
  • Connected - 連通的
  • Cycle - 環/迴路
  • Forest - 森林

有根樹術語

  • Root - 根
  • Leaf/Leaves - 葉子
  • Internal vertex - 內部頂點
  • Parent - 父節點
  • Child/Children - 子節點
  • Sibling - 兄弟節點
  • Ancestor - 祖先
  • Descendant - 後代

樹的類型

  • Rooted tree - 有根樹
  • m-ary tree - m元樹
  • Binary tree - 二元樹
  • Full m-ary tree - 完滿m元樹
  • Complete m-ary tree - 完全m元樹
  • Height - 高度
  • Level - 層

祝考試順利!加油!💪

記得:理解概念比死背公式更重要。遇到不會的題目先跳過,把會的題目做完再回來思考。