唯一性
最小生成樹在一些情況下可能會有多個。例如，當圖的每一條邊的權值都相同時，該圖的所有生成樹都是最小生成樹。
如果圖的每一條邊的權值都互不相同，那麼最小生成樹將只有一個。
proof:
- 假設有兩個MST A,B, 有一條edge屬於A而不屬於B, 令為ek,
- (ek聯集B)必會形成一個cycle C, 此環C中, 任意取走一條邊, 仍然兩兩連通
- C中必存在一個邊em,權重大於ek,
- 表示B如果用ek取代em, 會形成一個更小的生成樹, 但這跟一開始的assumption相矛盾
環定理cycle property
對於連通圖中的任意一個環 C：如果 C中有邊 e的權值大於該環中任意一個其它的邊的權值，那麼這個邊不會是最小生成樹中的邊
| hw1 | hw2 | hw3 | hw4 | hw5 | hw6 |
| 70 | 100 | 100 | 100 | 85 | 100 |
hw7
|
hw8
|
hw9
|
hw10
|
hw11
|
hw12
|
95*0.7
=67
|
100
| 100 |
80
|
87
|
沒有留言:
張貼留言