Kruskal演算法證明 - 筆記長也

Kruskal演算法證明

2018-01-15 20:34:08   資料結構

    Kruskal為一種形成最小花費生成樹的演算法,它的基本步驟如下:

    1.T是邊的集合,初始為空

    2.從原圖中選取目前還未被選取的邊中花費最小者

    3.若加入此邊不會與集合E構成迴路則將之加入集合

    4.重複步驟3直到所有邊被選取完畢

 

    這邊有兩個關於Kruskal演算法的證明:

    (1)原圖為連通時,Kruskal必定能形成一個生成樹

    (2)該生成樹必為最小花費生成樹

 

    (1)必定能生成樹證明       

    假設原圖為一連通圖

    假設得到的並非生成樹,根據定義有兩種情形,一是圖是有環的,二是得到的圖不連通
    由於根據Kruskal步驟,每次執行時加入的邊都必須不形成環,因此第一種情況不存在


    假設得到圖是不連通的,代表至少包含兩個獨立邊集合,假設其中一個為E,則E中邊對應所有點都無法

    到達其他邊集合對應的點

    這與原圖是連通產生矛盾,因此第二種情況也不存在

    (2)最小生成樹證明

    設圖有n個頂點,生成樹必具有n-1條邊

    假設最小生成樹為U   

    以Kruskal形成的樹為T   

    假設兩樹不同的邊數為k,有n-1-k條邊相同構成集合E

    在T中而不在U中的邊按花費依次排序為:a1,a2,…,ak

    在U中不在T中的邊按花費依次為:x1,x2…,xk

    現在把U轉換為T證明兩者具有相同花費(cost(U) = cost(T))

    首先,將a1移入U中,因為U本身為生成樹,加入任何一條邊都會構成迴路

    這條迴路必然包含x1,x2…,xk中的一個邊(若非如此,代表與E的邊構成迴路,這使得T中本身就有迴路,

    與條件矛盾)

    在這個迴路中刪除屬於x1,x2…,xk且花費為最大邊的xi 構成一個新的生成樹V

    假設a1花費小於xi,則V的花費小於U(cost(V) = cost(U)+a1 - x1 < cost(U)),這與U為最小生成樹矛

    盾,因此不成立

    假設a1花費大於xi,按照Kruskal演算法,會先考慮花費小的邊,xi應該會在a1之前考慮

    而a1又在a2,…,ak之前考慮

    所以考慮xi時,T中的邊只會有E集合的邊,而既然xi沒加入樹T,就說明xi必然與E中的某邊構成迴路

    但xi和E又存在於樹U中,代表樹U應該有迴路,而這與U是最小花費生成樹的條件矛盾

    因此,a1也不可能大於xi
    因此得到的新樹V與T具有相同花費   

    依此類推,將a1,a2,…,ak逐個加入U中,最終發現T和U花費相同       

    故Kruskal產生的樹必定為最小花費生成樹

關於作者