“““
????1）
????反正法，設存在最小生成樹T不包含邊（u?v），有切割（S?V-S）使得?u?in?S?and?v?in?V-S
????則至少有邊（x?y）橫跨此切割，以邊（u?v）替代（x?y）得到最小切割樹T‘
????由（u?v）權重最小可知T‘的權重小于T，與T為最小生成樹矛盾
????故假設不成立，T包含邊（u?v）
“““

“““
????2）
????有邊?（u?v）?（w?x）?（y?z）?都不在A中，權重分別為?1，?2，?3
????S包含?uwy，V-S包含vxz，則三條邊都是安全的，但此切割的輕量級邊只有（uv）
“““
“““
????3）
????反證法，設有分割（S?V-S）?ux?in?S?and?vy?in?V-S，
????有邊（xy）（uv）w（xy）?????有包含（xy）的T‘的權重?????與已知相矛盾，故假設不成立，（uv）為輕量級邊
“““
“““
????4）
????如有（ab）（bc）（ca）三條邊，且w（ab）=w（bc）=w（ca）=1
????S={ab}?V-S={c}?已有邊?A={（ab）（bc）}為最小生成樹，
????（ac）為切割的輕量級邊，但A={（ab）（bc）（ca）}不為最小生成樹
“““
“““
????5）
????顯而易見，必然存在一條能替換掉e從而使得T的權重下降的邊
“““
“““
????6）
????令每個切割的輕量級邊包含在集合A中，圖的最小生成樹存在并包含A中所有的邊
????如若不然，則對于最小生成樹的切割T，可以將A中的邊替換其樹中橫跨分割的邊而使得w降低
????逆論斷：若有唯一的最小生成樹，則對于圖的每個切割存在存在橫跨該切割的唯一輕量級邊
????反例?圖中只有（ab）（bc）兩條邊，且w（ab）=w（bc）=1，有最小生成樹：
???????b
??????/?\
?????a???c
????對于分割S={ac}?V-S={b}則（ab）（bc）都是輕量級邊，顯然輕量級邊不唯一
“““
“““
????7）
????若存在環，則必然可以去掉一條權重最大的邊而保持連接所有節點的屬性不變，
????若有負數的權重，則將所有的權重為負數的邊都加入進來，可能會生成環。
“““
“““
????8）
????設T的序列L={a1a2...an}?T‘的序列為L‘={b1b2...bn}
????從0到n知道遇到兩個不相等ai?!=?bi?ai對應的分割在L‘中的邊的權重為bj
????若?j?????若?j?>?i則可以用ai?替換?bj，權重會降低與T‘為最小生成樹矛盾
????必有?ai?=?bi
“““
“““
????9）
????設?a?in?V-V‘?在T中的葉子上。
????在G中去除a得到G‘‘，并在T中去除連接a的樹邊得到T‘‘?T‘‘為連通的。
????T為G的最小生成樹，樹中的每條邊在分割中不可替換，則去掉a后T‘‘為G‘‘的最小生成樹。
????逐步減少到T‘與G‘，T‘為G‘的最小生成樹。????
“““

“““
????10）
????設（xy）橫跨分割（S?V-S）?由（xy）為T的邊得出（xy）為分割的輕量級邊，
????令w（xy）減小，（xy）依然為分割的輕量級邊，（xy）依然為T的邊，T依然為G的最小生成樹。
“““

“““
????11）
????將這條邊加入的T中必然會形成一個環，去掉這個環中的權重最大的邊，得到一個新的最小生成樹
“““

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件???????3101??2017-01-18?14:57??chapter23\23.1-11.py

?????文件???????4580??2017-01-20?20:52??chapter23\23.2.py

?????文件????????124??2017-01-21?10:18??chapter23\23.2_1.py

?????文件???????2274??2017-01-21?16:57??chapter23\23.2_2.py

?????文件???????1142??2017-01-21?19:10??chapter23\23.2_3-8.py

?????文件???????1212??2017-01-21?21:48??chapter23\23_1.py

?????文件???????1079??2017-01-22?17:03??chapter23\23_2.py

?????文件????????666??2017-01-22?18:47??chapter23\23_3.py

?????文件????????257??2017-01-22?18:58??chapter23\23_4.py

?????目錄??????????0??2017-01-22?18:48??chapter23

-----------?---------??----------?-----??----

????????????????14435????????????????????10