下列之無向圖（undirected graph）中，共有多少個不同的生成樹（spanning trees）？
A6
B8
C9
D12正確答案
答案與詳解
為什麼答案是 D
正確答案。左三角形(a-b、b-c、a-c三邊)去任一條→3種；右四環(d-e、e-f、f-g、g-d四邊)去任一條→4種；橋邊c-d必須保留；3×4=12種生成樹。
考點：生成樹計數低估考點：cycle去邊數誤算考點：四環生成樹數誤算考點：生成樹乘法原理
載入中…
正確答案。左三角形(a-b、b-c、a-c三邊)去任一條→3種；右四環(d-e、e-f、f-g、g-d四邊)去任一條→4種；橋邊c-d必須保留；3×4=12種生成樹。
