組合數(shù)學(xué)克魯斯卡爾定理的證明

關(guān)于組合數(shù)學(xué)克魯斯卡爾定理的證明如何證明假設(shè):這個(gè)算法終止于T有n-1條邊那么根據(jù)定理3.20：假設(shè)G是一個(gè)有n個(gè)頂點(diǎn)和e條邊的圖。那么G是樹當(dāng)且僅當(dāng)G沒有回路且n=e+1.證明T是一棵樹，是G的一棵支撐樹。因此，G是連通的圖若算法將終止于沒有找到有n-1條邊的集合T。則G是非連通的圖

第2頁,共14頁，2024年2月25日，星期天分為兩部分證明 1.當(dāng)G為連通圖時(shí) 2.當(dāng)G為非連通圖時(shí)第3頁,共14頁，2024年2月25日，星期天定理13.1：

如果G是n個(gè)頂點(diǎn)的聯(lián)通網(wǎng)絡(luò)，Kruskal算法將終止于一個(gè)有n-1條邊的最小支撐樹T。

如果G是非連通網(wǎng)絡(luò)，那么算法在檢查所有邊之后，T中仍沒有n-1條邊，這時(shí)它將停止并輸出G是非連通的信息。證明思想：1.若G是連通的： (1)證明這個(gè)算法的確給出的是支撐樹 (2)證明這個(gè)支撐樹是最小的。2.若G是非連通的

證明算法終止時(shí)沒有給出有n-1條邊的T第4頁,共14頁，2024年2月25日，星期天證明：

1.當(dāng)G為連通的(1)若算法給出有n-1條邊的T那么根據(jù)定理3.16：假設(shè)G是一個(gè)有n個(gè)頂點(diǎn)和e條邊的圖。那么G是樹當(dāng)且僅當(dāng)G是連通的且n=e+1.則能證明算法給出的T是支撐樹第5頁,共14頁，2024年2月25日，星期天(2)想要證明Kruskal生成的支撐樹T是最小支撐樹125463569191126211234565611141414181616要證明支撐樹T是最小的。反證法:假設(shè)T不是最小支撐樹假設(shè)S是G的一棵最小支撐樹S≠T第6頁,共14頁，2024年2月25日，星期天e1(x,y):為第一條在T中而不在S中的邊這時(shí)會(huì)出現(xiàn)兩種情況情況1：e1的權(quán)值>e2的權(quán)值情況2：e1的權(quán)值<e2的權(quán)值Kruskal生成的支撐樹T12546314165611e1假設(shè)的最小支撐樹S125463141656e2xyXYS中存在一條簡單鏈C(x,y),與e1(x,y)構(gòu)成回路在鏈C(x,y)中存在一條在S中但不在T中的邊e2第7頁,共14頁，2024年2月25日，星期天情況1：e2的權(quán)值<e1的權(quán)值12546314165611e1Kruskal生成的支撐樹T125463141656假設(shè)的最小支撐樹S9e2因?yàn)閑1是第一條在T中但不在S中的邊所以T中在e1之前被找到的邊也一定在S中出現(xiàn)既然e2<e1，為什么T選擇了e1卻沒選擇e2因?yàn)閑2與e1之前出現(xiàn)的邊形成了回路，所以T選擇了邊e1因?yàn)镾是支撐樹，S中不能有回路所以與假設(shè)矛盾那么情況1不成立第8頁,共14頁，2024年2月25日，星期天情況2：e1的權(quán)值<e2的權(quán)值S′:是從S中去除邊e2，加上邊e1的邊的集合S′=S-e2+e1(權(quán)值)125463141656125463141656假設(shè)的最小支撐樹S125463141656e2125463141656125463141656支撐樹S’125463141656e2e1第9頁,共14頁，2024年2月25日，星期天情況2：e1的權(quán)值<e2的權(quán)值S′=S-e2+e1(權(quán)值)125463141656125463141656假設(shè)的最小支撐樹S125463141656e2125463141656125463141656支撐樹S’125463141656又因?yàn)镾是最小支撐樹所以S’權(quán)值和=S權(quán)值和所以S’就是最小支撐樹因?yàn)镾為最小支撐樹所以e2的權(quán)值至少與e1的權(quán)值一樣大e1情況2：e1的權(quán)值≤e2的權(quán)值因?yàn)閑2≥e1(權(quán)值)所以S’的權(quán)值和<=S的權(quán)值和第10頁,共14頁，2024年2月25日，星期天情況2：e1的權(quán)值<e2的權(quán)值≤125463141656125463141656125463141656125463141656e1支撐樹S’Kruskal生成的支撐樹T11e1圖中，支撐樹S’與Kruskal生成的支撐樹T相同就可以證明T是最小支撐樹。這是當(dāng)T=S’的情況，證明完畢。11第11頁,共14頁，2024年2月25日，星期天當(dāng)T≠S’時(shí)，再繼續(xù)找第一條在T中但不在S’中的邊e1’不在T中但在S’中的邊e2’S”=S’-e2’+e1’按照以上的方式重復(fù)做，直到找到T=S”為止1254631416561254631416561254636125463141656e1支撐樹S’Kruskal生成的支撐樹T11e1情況2：e1的權(quán)值<e2的權(quán)值≤11第12頁,共14頁，2024年2月25日，星期天2.若G是非連通的：若這個(gè)算法終止時(shí)沒有給出有n-1條邊的T反證法：假設(shè)G是連通的

∵T中的邊數(shù)少于n-1條 ∴T至少有兩個(gè)分支又∵G是連通的 ∴G中存在一條連接T的兩個(gè)不同分支中的頂點(diǎn)的邊{x,y}

∵現(xiàn)在{x,y}不與T中