? asked in 電腦與網際網路軟體 · 1 decade ago

關於資料結構minimum spanning tree的問題

若將一個圖(T1)分成兩個子圖g1.g2,用prim's

algorithm 找出各自MST(minimum spanning tree)後合併,會和圖T1使用prim's algorithm求出的會不同,而且這樣的答案是錯的,why??

在網路上找了很久還是不太清楚,

方便的話可以舉個例子說明更好

麻煩各位嚕,謝謝

1 Answer

Rating
  • Leslie
    Lv 7
    1 decade ago
    Favorite Answer

    你的題目沒有說清楚,

    若 T=(V, E) 分成子圖 G1=(V1, E1) 及子圖 G2=(V2, E2) 時,

    有限制 V=V1 U V2 且 E=E1 U E2 嗎?

    而且 V1 及 V2 是 disjoint 嗎? E1 及 E2 是 disjoint 嗎?

    或是其他限制呢?

    另外, 何謂 "圖的合併"?

    "合併" 在圖論中並不是通用的定義.

    底下是我自己做了合理的假設, 請你看是否是你要的:

    V=V1 U V2 且 V1 及 V2 是 disjoint,

    E1 是 V1 在 V 中的邊, E2 是 V2 在 V 中的邊.

    因此, E = E1 U E2 U E3, 其中 E3 是連接 V1 及 V2 的一些邊, 且

    E1, E2, E3 彼此都 disjoint.

    且 G1 及 G2 都是 connected.

    而, MST 合併必須挑一個連接 V1 及 V2 的最短的邊.

    要證明是錯的, 只要找一個反例就行了, 底下就是一個:

    T 是這圖: 日

    它的邊的重量是:

    上方的 ㄇ 的上, 左, 右, 各為 1, 4, 6,

    下方的 口 的上下左右各為 2, 3, 5, 7,

    若 G1 的 E1 為 4, 5. G2 的 E2 為 6, 7, (E3 是 1, 2, 3)

    則 G1 的 MST 為 G1,

    G2 的 MST 為 G2,

    那麼, 此兩個 MST 合併是 4, 5, 1, 6, 7.

    但是原圖 T 的 MST 卻是 1, 2, 3, 4, 5

    Source(s): Algorithm textbooks
Still have questions? Get your answers by asking now.