高普考題庫
101 年 101年公務人員高等考試三級考試暨普通考試・計算機概要
35若G為一非多重圖形(non-multigraph)、無自身邊線(Self edge)之無向圖形(Undirected graph)結構,並以nG表示G之頂點(Vertex)數,以eG表示G之邊線(Edge)數,且TG為基於G之生成樹(Spanningtree)。下列為有關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)結構。請選出最適合之選項: