普通考試
115年
[資訊處理] 計算機概要
第 21 題
若一個連接無向圖（Connected Undirected Graph）G 由 n 個點（Vertices）與 m 條邊（Edges）所組成，則有關點與邊的敘述，下列何者正確？
- A $m \ge n - 1$
- B $m > n - 1$
- C $m \ge n$
- D $m > n$
思路引導 VIP
想像你手上有 5 個獨立的圓點散落在紙上，如果你想用最少的直線段將它們全部串連起來，使得從任何一點出發都能到達其他任一點，你最少需要畫幾條線？試著畫畫看，並思考如果點的數量增加到 $n$ 個時，點與線之間的數量關係會呈現什麼規律？
🤖
AI 詳解
AI 專屬家教
恭喜你正確答對了這一題！這顯示你對於圖論（Graph Theory）中關於連通性與結構的基本性質有著非常清晰的理解，這是深入學習演算法不可或缺的基石。
最小連通性與生成樹的概念
在資料結構中，一個擁有 $n$ 個頂點的無向圖若要達成「連通」狀態，最極端、最精簡的情況就是構成一棵生成樹（Spanning Tree）。根據樹的定義，要連接 $n$ 個節點且不產生迴圈，所需的邊數 $m$ 恰好會等於 $n-1$。如果邊數少於這個數值，圖形必然會分裂成多個不相連的分量（Connected Components）；而一旦邊數超過 $n-1$，圖形則會在維持連通的基礎上產生迴圈。因此，對於任何連通無向圖，邊數 $m$ 必定滿足 $m \ge n-1$ 的關係。
▼ 還有更多解析內容