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

答案：登入後查看
統計： A(141), B(218), C(74), D(69), E(0) #1428011

詳解 (共 4 筆)

#1529108

從最小邊開始建樹，而後必須從有相鄰的邊中選擇

(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 


29
1
#1856388

先連BC,CD,AC,EF,BG,GF

如果先連DG 那BCDG會連成一循環

所以不可以連

為了使此樹必連BC

所以BC要小於DG的26

所以BC的最大值=25


11
2
#3905069
回上面如果你真的有把BC用25代入驗證的...
(共 67 字，隱藏中）
前往觀看
2
0
#3763995

樓上 由於是最小生成樹

所以數字小的都會連起來(不形成循環的情況下)

所以 會依照以下順序進行連接

CD 12 > AC 14 >EF 18 >BG 20

由於BC為必連接 所以連接DG會造成循環

為了使BC能連接 所以BC必須小於DG的26

所以 BC最大數為25 

1
1