問題詳情

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

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

參考答案

答案：B
難度：困難0.32872
統計：A(76),B(95),C(47),D(31),E(0)

用户評論

【用戶】Moonforget Wh

【年級】小二上

【評論內容】從最小邊開始建樹，而後必須從有相鄰的邊中選擇(1)c-d  12                 如果b-c比較小(11)可以建    樹:c-d                 (2)a-c  14                 如果b-c比較小(13)可以建    樹:a-c-d        (3)d-g  26                 如果b-c比較小(25)可以建    樹:a-c-d-g    (4)g-b  20                 如果b-c比較小(19)可以建    樹:a-c-d-g-b  這時候如果還沒建b-c，已經來不及了，因為b c都已經連上所以倒退回到上一步(3)b-c  25(最大值)註:如果(1)或(2)就建b-c最大值只有11或13 

【用戶】gtaped07862

【年級】小六下

【評論內容】先連BC,CD,AC,EF,BG,GF如果先連DG 那BCDG會連成一循環所以不可以連為了使此樹必連BC所以BC要小於DG的26所以BC的最大值=25