John
Lv 4
John asked in 電腦與網際網路程式設計 · 6 years ago

spanning tree問題,求詳細解題說明,謝謝!!

在一個有5個點的完全圖(complete graph)裡,若每條邊長度相等,則此圖共有幾個最小成本生成樹(minimum-costspanning tree)? (A)20 (B)42 (C)120 (D)125

正確答案是 D

不知道怎麼算出來的,求詳細解題說明,謝謝!!

Update:

謝謝Diamond Liu大師,您算出來是共有24個最小成本生成樹,可是正解怎會是125個?

Update 2:

這是新北市立國民中學 102 學年度教師聯合甄選試題

公布正解是(D)125

好想知道是怎麼算的,敬請各位賜教。

1 Answer

Rating
  • 6 years ago
    Favorite Answer

    在一個有5個點的完全圖(complete graph)裡,若每條邊長度相等,則此圖共有幾個最小成本生成樹(minimum-cost spanning tree)?

    (A)20 (B)42 (C)120 (D)125

    正確答案是 D

    參考看看,有誤請指正。

    完全圖(complete graph)http://en.wikipedia.org/wiki/Complete_graph

    每一點至其他各點均有連線。

    最小成本生成樹(minimum-cost spanning tree)http://en.wikipedia.org/wiki/Minimum_spanning_tree

    連結各點的最小成本子樹。

    依題意及定義,因為每條邊長度相等,故所有子樹均為最小成本生成樹。

    由於此為完全圖,依組合公式,故共有4*3*2*1=4!個子樹,均為最小成本生成樹。

    得證:此圖共有24個最小成本生成樹(minimum-cost spanning tree)

    2014-10-02 10:02:18 補充:

    1.我的答案係依wikipedia及本身認知計算而得,純粹僅供參考,或有其他大大可提供正確答案。

    2.John大大所謂的正確答案是 D,不知其依據為何?可否提示一二。

    2014-10-03 11:13:28 補充:

    依生成樹(spanning tree)之定義,從一張圖上分離出一棵包含圖上所有點的樹,便是這張圖的生成樹。

    http://en.wikipedia.org/wiki/Spanning_tree

    http://en.wikipedia.org/wiki/Cayley%27s_formula

    For a complete graph with n vertices, Cayley's formula gives the number of spanning trees as n^(n − 2).

    故5個點的完全圖共有5^(5-2)=125個spanning trees

    2014-10-03 11:17:56 補充:

    http://en.wikipedia.org/wiki/Spanning_tree之說明,span... tree之計算,依不同連結順序方式而有所區別。故For a complete graph with n vertices, Cayley's formula gives the number of spanning trees as n^(n − 2).

    Cayley's的公式 n^(n − 2)

Still have questions? Get your answers by asking now.