農會 資訊管理類電腦概論110 年第 23 題單選題
一個沒方向性的連接圖,節點為N,則其邊的個數不可能為
A正確答案
無向連通圖最少需要 N-1 條邊才能連通所有節點，因此邊數絕對不可能少於 N-1，N-2 條邊必定無法連通。
為什麼答案是 A
連通圖至少需要 N-1 條邊，N-2 條邊無法使所有節點連通，必然形成斷裂的森林，故不可能，此為正解。
考點：連通圖最小邊數考點：生成樹考點：帶環連通圖考點：多環連通圖
載入中…
完整詳解
Pro · 無限重點 無向連通圖最少需要 N-1 條邊才能連通所有節點，因此邊數絕對不可能少於 N-1，N-2 條邊必定無法連通。
連通圖邊數 E ≥ N-1（生成樹）。直觀想像：N個人要手牽手連成一排，最少需要 N-1 次牽手，看到 N-2 直接選！
逐選項分析
A連通圖最小邊數✓ 正確
連通圖至少需要 N-1 條邊，N-2 條邊無法使所有節點連通，必然形成斷裂的森林，故不可能，此為正解。
B生成樹✕
N-1 條邊可構成樹狀結構（生成樹），是連通圖的最小邊數，屬於可能情況。
C帶環連通圖✕
N 條邊可構成帶有一個環的連通圖，所有節點皆可互相抵達，屬於可能情況。
D多環連通圖✕
N+1 條邊可構成帶有多個環的連通圖，節點皆連通且路徑更多，屬於可能情況。
無向連通圖邊數與結構關係
| 邊數 (E) | 圖的結構特徵 | 是否連通 |
|---|
| E < N-1 | 森林（多個不連通子圖） | 否 |
| E = N-1 | 樹（無環連通圖） | 是 |
| E ≥ N | 帶環連通圖 | 是 |
考生易將「節點數 N」與「邊數 N-1」記混，或誤以為邊數越少越好。請牢記「N 個點要連成一線，最少需要 N-1 條線段」的直觀概念，避免掉入數字陷阱。 
