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

1、關(guān)于組合數(shù)學(xué)克魯斯卡爾定理的證明第一張，PPT共十四頁(yè)，創(chuàng)作于2022年6月如何證明假設(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是非連通的圖 第二張，PPT共十四頁(yè)，創(chuàng)作于2022年6月分為兩部分證明1.當(dāng)G為連通圖時(shí)2.當(dāng)G為非連通圖時(shí)第三張，PPT共十四頁(yè)，創(chuàng)作于2022年6月定理13.1 ： 如果G是n個(gè)頂點(diǎn)的聯(lián)通網(wǎng)絡(luò)，Kruskal算法將終止于一個(gè)有n-1條邊的最小支撐樹T。 如果G是非連通網(wǎng)絡(luò)

2、，那么算法在檢查所有邊之后，T中仍沒有n-1條邊，這時(shí)它將停止并輸出G是非連通的信息。證明思想：1.若G是連通的：(1)證明這個(gè)算法的確給出的是支撐樹(2)證明這個(gè)支撐樹是最小的。2.若G是非連通的證明算法終止時(shí)沒有給出有n-1條邊的T第四張，PPT共十四頁(yè)，創(chuàng)作于2022年6月證明： 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是支撐樹第五張，PPT共十四頁(yè)，創(chuàng)作于2022年6月(2)想要證明Kruskal生成的支撐樹T是最小支撐樹1254635691911262112

3、34565611141414181616要證明支撐樹T是最小的。反證法:假設(shè)T不是最小支撐樹假設(shè)S是G的一棵最小支撐樹 ST第六張，PPT共十四頁(yè)，創(chuàng)作于2022年6月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中存在一條簡(jiǎn)單鏈C(x,y),與e1(x,y)構(gòu)成回路在鏈C(x,y)中存在一條在S中但不在T中的邊e2第七張，PPT共十四頁(yè)，創(chuàng)作于2022年6月情況1：e2的權(quán)值e1的權(quán)值12546314165

4、611e1Kruskal生成的支撐樹T125463141656假設(shè)的最小支撐樹S9e2因?yàn)閑1是第一條在T中但不在S中的邊所以T中在e1之前被找到的邊也一定在S中出現(xiàn)既然e2e1，為什么T選擇了e1卻沒選擇e2因?yàn)閑2與e1之前出現(xiàn)的邊形成了回路，所以T選擇了邊e1因?yàn)镾是支撐樹，S中不能有回路所以與假設(shè)矛盾那么情況1不成立第八張，PPT共十四頁(yè)，創(chuàng)作于2022年6月情況2：e1的權(quán)值e2的權(quán)值 S:是從S中去除邊e2，加上邊e1的邊的集合 S=S-e2+e1(權(quán)值)125463141656125463141656假設(shè)的最小支撐樹S125463141656e212546314165612546

5、3141656支撐樹S125463141656e2e1第九張，PPT共十四頁(yè)，創(chuàng)作于2022年6月情況2：e1的權(quán)值 e2的權(quán)值S=S-e2+e1(權(quán)值)125463141656125463141656假設(shè)的最小支撐樹S125463141656e2125463141656125463141656支撐樹S125463141656又因?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)值和第十張，PPT共十四頁(yè)，創(chuàng)作于2022年6月情況2：e1的權(quán)值e2的權(quán)值125463141656125463141656125463141656125463141656e1支撐樹SKruskal生成的支撐樹T11e1圖中，支撐樹S與Kruskal生成的支撐樹T相同就可以證明T是最小支撐樹。這是當(dāng)T=S的情況，證明完畢。11第十一張，PPT共十四頁(yè)，創(chuàng)作于2022年6月當(dāng) TS時(shí)，再繼續(xù)找第一條在T中但不在S中的邊e1不在T中但在S中的邊e2S”=S-e2+e1按照以上的方式重復(fù)做，直到找到T=S”為止1254631416561254631416561254636125463141656e1支撐樹SKruskal生成的支