問題詳情

35 若G為一非多重圖形(non-multigraph)、無自身邊線(Self edge)之無向圖形(Undirected graph)結構,並以nG表示G之頂點 Vertex) ( 數,以eG表示G之邊線 Edge) ( 數,且TG為基於G之生成樹 Spanning ( tree)。下列為有關G與其生成樹TG之敘述:  ①生成樹TG可經由對G使用Kruskal演算法或Prim演算法產生。  ②若以nT表示生成樹TG之節點(Node)數,則nT = nG。  ③若以eT表示生成樹TG之邊線(Edge)數,則eT < eG。  ④若以hT表示生成樹TG之高度(Height),則log2nG ≤ hT ≤ nG。[註:僅有樹根(Root)節點之樹狀( Tree)結構其高度為 1。]  ⑤ 若TG為基於G之唯一生成樹(Spanning tree),則G為一樹狀(Tree)結構。 請選出最適合之選項:
(A)②③正確;①⑤錯誤
(B)①②正確;③④錯誤
(C)①④錯誤
(D)②④正確

參考答案

答案:B
難度:困難0.387755
統計:A(3),B(19),C(8),D(11),E(0)

內容推薦

內容推薦