19 下圖之邊長（edge length）均為不一樣的整數，邊上之數字表示長度。..-阿摩線上測驗

上一題

19 下圖之邊長（edge length）均為不一樣的整數，邊上之數字表示長度。若其最小生成樹（minimum spanning tree）含有連接 b 與 c 的邊(b, c)，則(b, c)之長度最大值為何？

(A)19
(B)25
(C)27
(D)29

答案：B
難度： 困難

最佳解!
	Moonforget Wh 小二上 (2016/11/25) 從最小邊開始建樹，而後必須從有相鄰的邊中選擇(1)c-d 12 如果b-c比較小(11)可以建樹:c-d (2)a-c 14 如果b-c比較小(13)可以建樹:a-c-d (3)d-g 26 .....觀看完整全文，請先登入檢舉

	2F gtaped07862 高一上 (2017/03/30) 先連BC,CD,AC,EF,BG,GF 如果先連DG 那BCDG會連成一循環所以不可以連為了使此樹必連BC 所以BC要小於DG的26 所以BC的最大值=25 檢舉
	3F gtaped07862 高一上 (2020/02/06) 樓上由於是最小生成樹所以數字小的都會連起來(不形成循環的情況下) 所以會依照以下順序進行連接 CD 12 > AC 14 >EF 18 >BG 20 由於BC為必連接所以連接DG會造成循環為了使BC能連接所以BC必須小於DG的26 所以 BC最大數為25 檢舉
	4F 109年中華電信已錄取高三上 (2020/04/25) 回上面如果你真的有把BC用25代入驗證的話，你會發現DG變成不會連線(避免形成迴圈)，一樣可生成最小生成樹所以答案最大可到25無誤檢舉

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

19 下圖之邊長（edge length）均為不一樣的整數，邊上之數字表示長度。..-阿摩線上測驗

計算機概論、大意(資訊科學概論,電腦常識,電子計算機概論)題庫下載題庫