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

1、13.1.2 定理13.1的證明如何證明l假設(shè):這個(gè)算法終止于T有n-1條邊那么根據(jù)定理3.20：假設(shè)G是一個(gè)有n個(gè)頂點(diǎn)和e條邊的圖。那么G是樹當(dāng)且僅當(dāng)G沒(méi)有回路且n=e+1.證明T是一棵樹，是G的一棵支撐樹。 因此，因此，G G是連通的圖是連通的圖l若算法將終止于沒(méi)有找到有n-1條邊的集合T。 則則G G是非連通的圖是非連通的圖 分為兩部分證明1.當(dāng)G為連通圖時(shí)2.當(dāng)G為非連通圖時(shí)定理13.1 ： 如果G是n個(gè)頂點(diǎn)的聯(lián)通網(wǎng)絡(luò)，Kruskal算法將終止于一個(gè)有n-1條邊的最小支撐樹T。 如果G是非連通網(wǎng)絡(luò)，那么算法在檢查所有邊之后，T中仍沒(méi)有n-1條邊，這時(shí)它將停止并輸出G是非連通的信息。證明

2、思想：證明思想：1.若G是連通的：(1)證明這個(gè)算法的確給出的是支撐樹(2)證明這個(gè)支撐樹是最小的。2.若G是非連通的證明算法終止時(shí)沒(méi)有給出有n-1條邊的T證明： 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是支撐樹(2)想要證明Kruskal生成的支撐樹T是最小支撐樹125463569191126211234565611141414181616要證明支撐樹T是最小的。反證法反證法: :假設(shè)T不是最小支撐樹假設(shè)S是G的一棵最小支撐樹 STe1(x,y):為第一條在T中而不

3、在S中的邊這時(shí)會(huì)出現(xiàn)兩種情況情況1：e1的權(quán)值e2的權(quán)值情況2：e1的權(quán)值e2的權(quán)值Kruskal生成的支撐樹生成的支撐樹T12546314165611e1假設(shè)的最小支撐樹假設(shè)的最小支撐樹S125463141656e2xyXYS中存在一條簡(jiǎn)單鏈C(x,y),與e1(x,y)構(gòu)成回路在鏈C(x,y)中存在一條在S中但不在T中的邊e2情況情況1 1：e2e2的權(quán)值的權(quán)值e1e1的權(quán)值的權(quán)值12546314165611e1Kruskal生成的支撐樹生成的支撐樹T125463141656假設(shè)的最小支撐樹假設(shè)的最小支撐樹S9e2因?yàn)閑1是第一條在T中但不在S中的邊所以T中在e1之前被找到的邊也一定在S中

4、出現(xiàn)既然e2e1，為什么T選擇了e1卻沒(méi)選擇e2因?yàn)閑2與e1之前出現(xiàn)的邊形成了回路，所以T選擇了邊e1因?yàn)镾是支撐樹，S中不能有回路所以與假設(shè)矛盾那么情況1不成立情況情況2 2：e1e1的權(quán)值的權(quán)值e2e2的權(quán)值的權(quán)值 S:是從S中去除邊e2，加上邊e1的邊的集合 S=S-e2+e1(權(quán)值)125463141656125463141656假設(shè)的最小支撐樹假設(shè)的最小支撐樹S125463141656e2125463141656125463141656支撐樹支撐樹S125463141656e2e1情況情況2 2：e1e1的權(quán)值的權(quán)值 e2 e2的權(quán)值的權(quán)值S=S-e2+e1(權(quán)值)12546314

5、1656125463141656假設(shè)的最小支撐樹假設(shè)的最小支撐樹S125463141656e2125463141656125463141656支撐樹支撐樹S125463141656又因?yàn)镾是最小支撐樹所以S權(quán)值和=S權(quán)值和所以S就是最小支撐樹因?yàn)镾為最小支撐樹所以e2的權(quán)值至少與e1的權(quán)值一樣大e1情況情況2 2：e1e1的權(quán)值的權(quán)值 e2e2的權(quán)值的權(quán)值因?yàn)閑2 e1(權(quán)值) 所以 S的權(quán)值和=S的權(quán)值和情況情況2 2：e1e1的權(quán)值的權(quán)值e2e2的權(quán)值的權(quán)值125463141656125463141656125463141656125463141656e1支撐樹支撐樹SKruskal生成的

6、支撐樹生成的支撐樹T11e1圖中，支撐樹S與Kruskal生成的支撐樹T相同就可以證明T是最小支撐樹。這是當(dāng)T=S的情況，證明完畢。11當(dāng) TS時(shí)，再繼續(xù)找第一條在T中但不在S中的邊e1不在T中但在S中的邊e2S”=S-e2+e1按照以上的方式重復(fù)做，直到找到T=S”為止1254631416561254631416561254636125463141656e1支撐樹支撐樹SKruskal生成的支撐樹生成的支撐樹T11e1情況情況2 2：e1e1的權(quán)值的權(quán)值e2假設(shè)不成立，只有當(dāng)G是非連通的時(shí)候才會(huì)出現(xiàn)這種情況12546314511262118當(dāng)圖當(dāng)圖G G為非連通圖時(shí)，為非連通圖時(shí)，T T中會(huì)只中會(huì)只有這幾個(gè)邊有這幾個(gè)邊若若G G為連通圖時(shí)，至少會(huì)有一為連通