試題詳解

19 已知一連通圖（connected graph），圖中一個子樹、一個生成圖（spanning graph，即含原圖中所有節點的連 通子圖）與一個最小生成樹（spanning tree），下列敘述何者正確？
(A)子樹邊數 ≦ 生成圖的邊數 ≦ 最小生成樹的邊數
(B)子樹邊數 ≦ 最小生成樹的邊數 ≦ 生成圖的邊數
(C)最小生成樹的邊數 ≦ 生成圖的邊數 ≦ 子樹邊數
(D)最小生成樹的邊數 ≦ 子樹邊數 ≦ 生成圖的邊數