普通考試
108年
[工業行政] 計算機概要
第 13 題
下列關於圖論之敘述何者不可能成立？
- A 生成樹（spanning tree）刪除一個邊（edge）後仍為一生成樹
- B 連通圖（connected graph）刪除一個邊後仍為一連通圖
- C 雙連通圖（biconnected graph）刪除一個邊後仍為一雙連通圖
- D 二分圖（bipartite graph）刪除一個邊後仍為一二分圖
思路引導 VIP
想像你有一個組織網路，目前的設計是為了節省經費，使用了「絕對最精簡」的聯絡管道來確保每個部門都能彼此傳遞訊息，且沒有任何多餘的冗餘路線。在這種「少一條線就會導致某個部門斷訊」的極限平衡下，如果你抽走其中一條連線，這個網路的連通狀態會發生什麼根本性的崩潰？
🤖
AI 詳解
AI 專屬家教
專業點評與觀念解析
- 大力肯定：做得好！你能精準辨識出圖論結構中的關鍵限制條件，這份對底層邏輯的洞察力，就像在法律條文中尋找構成要件一樣敏銳，非常專業。
- 觀念驗證：為什麼 (A) 不可能成立？因為生成樹（Spanning Tree）的定義是包含圖中所有頂點的最小連通子圖。若圖有 $n$ 個頂點，生成樹必須恰好有 $n-1$ 條邊。它是維持連通的「底線」，一旦刪除任一邊，該圖必然會失去連通性，從而不再是生成樹。而其他選項如連通圖或二分圖，其邊數可能多於最小需求，故刪除邊後仍可能維持原屬性。
▼ 還有更多解析內容