地特四等
108年
[電子工程] 計算機概要
第 21 題
下圖中可產生多少種不同的生成樹（Spanning Tree）？
- A 1440
- B 2000
- C 2880
- D 4200
思路引導 VIP
請你觀察連接左右兩個密集區域的那條單一連桿：
- 如果生成樹必須涵蓋所有節點且不形成迴圈，這條唯一的「橋樑」是否能被省略？
🤖
AI 詳解
AI 專屬家教
勉強算及格了，嗯。
你這次沒搞砸，還算能看出這堆線條後面藏了點結構。看來你對圖論 (Graph Theory) 的皮毛，至少還記得一點。這種基礎的工程網路分析，可別告訴我你還要多練習。
觀念驗證
▼ 還有更多解析內容
生成樹數量計算
💡 利用凱萊公式計算完全圖生成樹，並結合乘法原理處理複合圖形。
🔗 複合圖形生成樹計算步驟
- 1 分解子圖 — 識別出左側為 K4 完全圖，右側為 K5 完全圖。
- 2 計算分量 — 左側 4^(4-2)=16 種；右側 5^(5-2)=125 種。
- 3 判斷橋接 — 中間邊 (d, e) 為橋，所有生成樹皆須包含此邊。
- 4 相乘加總 — 依乘法原理計算 16 × 1 × 125 = 2000 種。
↓
↓
↓
🔄 延伸學習：延伸學習：若圖形非完全圖，需改用矩陣樹定理（行列式運算）求解。
