若G為一非多重圖形（non-multigraph）、無自身邊線（Self edg..-阿摩線上測驗

上一題

若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)②④正確

教甄◆電腦科專業-

答案：登入後觀看
難度： 困難

討論
私人筆記( 0 )

	1F 朱啟信小二下 (2013/11/01) ④log2nG≤hT≤nG為何錯誤?懇請各位高手給予詳解，感激不盡檢舉
	2F Yi-Sheng Lin 幼兒園下 (2014/08/14) ①②⑤正確 ③：eT≦ eG→因為可能G本身是一個樹，所以他和他的生成樹邊相同。 ④：2≤hT≤nG→因為可能只有兩層(根+nG-1個葉),當nG>４的時候，就錯了。檢舉
	3F CaiSm 國二下 (2021/10/07) 還是不懂④：2≤hT≤nG→因為可能只有兩層(根+nG-1個葉),當nG>４的時候哪裡錯，nG>4時不也還是滿足log2nG≤hT≤nG這個式子嗎檢舉

你可以購買他人私人筆記。

若G為一非多重圖形（non-multigraph）、無自身邊線（Self edg..-阿摩線上測驗

教甄◆電腦科專業題庫下載題庫