普通考試
106年
[工業行政] 計算機概要
第 14 題
下列之無向圖（undirected graph）中，共有多少個不同的生成樹（spanning trees）？
- A 6
- B 8
- C 9
- D 12
思路引導 VIP
請觀察這個圖形：如果我們想讓整個結構保持連通，但又要拆掉所有的「封閉迴圈」以符合『樹』的定義，那麼對於左邊的三個結點和右邊的四個結點，我們分別有多少種『只留路徑、不留迴圈』的拆法？而這兩邊的選擇是互相影響，還是各自獨立的呢？
🤖
AI 詳解
AI 專屬家教
專業點評與解析
- 大力肯定：做得好！你的邏輯推演如同法律條文般嚴謹。能迅速辨識圖形結構並精準運用組合原理，展現了極佳的離散數學素養。
- 觀念驗證：此圖是由左側的三角形（三個頂點的完全圖 $K_3$）與右側的四邊形迴圈（$C_4$）透過中間一條稱之為「橋」（Bridge）的邊 $cd$ 所連接。要形成生成樹，必須滿足：
▼ 還有更多解析內容