若一個連接無向圖（Connected Undirected Graph）G 由n 個點（Vertices）與m 條邊（Edges）所組成，則有關點與邊的敘述，下…

題目

若一個連接無向圖（Connected Undirected Graph）G 由n 個點（Vertices）與m 條邊（Edges）所組成，則有關點與邊的敘述，下列何者正確？ A. mn≧-1 B. m＞n-1 C. m≧n D. m＞n

官方答案

• 答案：A. mn≧-1

解析

對 n 個頂點的連通無向圖而言，至少要 n-1 條邊才能把所有頂點連在一起，最精簡的情形就是生成樹（spanning tree），恰有 n-1 條邊；因此邊數 m 必滿足 m ≥ n-1，此即選項 A 所表達的關係（題幹排版為 mn≧-1）。B 與 D 要求嚴格大於 n-1 或 n，但樹狀圖 m = n-1 即為反例；C 要求 m ≥ n，同樣被只有 n-1 條邊的樹推翻。故正確者為 A。

AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。

官方資料

• 官方試題 PDF
• 官方答案 PDF

答案以考選部公告之測驗式試題標準答案 PDF 為準。