一個沒方向性的連接網路圖，節點為 N（N>2），則其邊的個數不可能為何？ (A) N-2 (B) N-1 (C) N (D) N+1

正確答案為 A。無向連通圖至少需要 N-1 條邊才能連接所有 N 個節點，故邊數不可能小於 N-1。 (A) 【連通圖最小邊數】邊數 N-2 小於最小連通邊數 N-1，無法形成連通圖，故為本題要選的答案。 (B) 【生成樹邊數】N-1 為生成樹的邊數，是維持 N 個節點連通的最小邊數，可能出現。

農會資訊管理類－九職等以下新進人員電腦概論112 年第 20 題單選題考點：連通圖最小邊數考點：生成樹邊數

一個沒方向性的連接網路圖，節點為 N（N>2），則其邊的個數不可能為何？

AN-2正確答案

BN-1

DN+1

答案與詳解

正確答案

無向連通圖至少需要 N-1 條邊才能連接所有 N 個節點，故邊數不可能小於 N-1。

AN-2連通圖最小邊數✓ 正確

邊數 N-2 小於最小連通邊數 N-1，無法形成連通圖，故為本題要選的答案。

BN-1生成樹邊數✕ 錯誤

N-1 為生成樹的邊數，是維持 N 個節點連通的最小邊數，可能出現。

CN✕ 錯誤

DN+1✕ 錯誤

這題的完整詳解,註冊就能看 · 每天 2 題免費

精選詳解