平面連通圖是一個二維網絡,網絡由節點和邊組成,比如我随手畫了一個:
也可以是這樣:
它并不是一個空間連通圖因為他可以拓撲變換成這樣:
但如果這種圖就不行了:
這樣的連通圖隻能出現在三維空間中,是以無法滿足歐拉公式.
前期準備：
kruskal算法是由一個個遞進的循環周期組成的，每個循環周期的步驟如下：
然後給一個過程圖，大家自己意會：
根據之前對生成樹下的定義，首先要覆寫所有點，其次不能有環，最後不能有斷路。
第一點：很容易，既然通過集合A、B、C包含所有邊的洗牌過程，自然照顧到了G中所有的點。
第二點：更容易，每個循環中都要檢查一遍是否與之前的”小樹苗“形成環路，最後肯定無環。
第三點：可以用反證法，假設最後生成了互相隔離的兩棵樹，因為總共循環了x次（每條邊各一次），兩棵樹中間的那些邊（C中可以連接配接兩棵樹的邊）當初被審查的時候肯定會被納入B，與“納入C”沖突，是以不可能生成兩棵樹。
這個地方考驗大家的空間想象能力，如果想不出來可以畫圖。
同樣是反證法：
現在開始做一系列的變換,将K變換成T:
prim算法見下文