一個無向連通圖（Undirected connected graph）G，若具有下列何項條件則成為一棵樹？

題目

一個無向連通圖（Undirected connected graph）G，若具有下列何項條件則成為一棵樹？ A. 每個頂點的分支度（Degree）都是偶數 B. 不包含迴路（Cycles） C. 有一個分支度（Degree）是奇數的頂點 D. 非完全連通（Completely connected）

官方答案

• 答案：B. 不包含迴路（Cycles）

解析

樹的定義為「連通且無迴路（Acyclic）的無向圖」。題目已給 G 為無向連通圖，故只要再滿足「不包含迴路（Cycles）」即為一棵樹，選 B。選項 A「每個頂點分支度皆偶數」是歐拉圖（Eulerian graph）的條件，與樹無關；C「有一個奇數分支度頂點」樹中葉節點度為 1（奇數）很常見，但此條件不足以定義樹；D「非完全連通」更與樹的連通性矛盾。重點：連通 + 無環 = 樹；等價地，n 個頂點的連通無向圖若恰有 n−1 條邊亦為樹。

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

官方資料

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

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