# Kruskal 演算法證明：為什麼產生的生成樹是最小花費？

## 目標

我們要證明：
1. Kruskal 演算法一定會產生一棵生成樹。
2. 這棵生成樹的花費是最少的。

---

## 記號說明

- **T**：Kruskal 演算法產生的生成樹。
- **U**：假設的一棵最小花費的生成樹。
- **e**：T 中的某一條邊，但不在 U 中。
- **f**：U 中的某一條邊，但不在 T 中。

---

## 目標 1：Kruskal 演算法會產生一棵生成樹

1. Kruskal 演算法的過程是選擇圖中不會形成迴路的邊，從最小權重開始，直到選出 n-1 條邊為止（n 是節點的數量）。
2. 如果 G 是一個連通圖，演算法一定能選出一個連通的邊集合，並在選滿 n-1 條邊後停止。
3. 因此，Kruskal 演算法一定會產生一棵生成樹。

---

## 目標 2：Kruskal 演算法產生的生成樹是最小花費

### 證明思路

1. 假設 T 是 Kruskal 演算法生成的生成樹，U 是假設的最小花費生成樹。
2. 假設 T 和 U 不相同，我們可以通過轉換 U 使其逐步變成 T，並保持轉換過程中的花費不變。
3. 最後證明 T 的花費和 U 一樣，這樣就證明了 T 也是最小花費的生成樹。

---

### 具體步驟

1. **初始狀態**：
- T 是 Kruskal 演算法生成的生成樹。
- U 是我們假設的最小花費生成樹。
- T 和 U 之間有 k 條不同的邊（即 T 中有 k 條邊不在 U 中，U 中有 k 條邊不在 T 中）。

2. **選擇邊**：
- 從 T 中選一條不在 U 中的邊 e，將它加入 U 中。
- 加入 e 後，U 會形成一個唯一的迴路。

3. **解決迴路**：
- 在這個迴路中選一條不在 T 中的邊 f，從 U 中移除，這樣 U 又回到生成樹的狀態。
- 此時，U 中不在 T 中的邊數減少一條。

4. **重複步驟**：
- 重複上述操作，直到 U 完全變成 T。

---

### 為什麼花費不會變？

- **情況 1**：如果 e 的花費比 f 小，那麼 U 的花費會變小，這與 U 是最小花費的假設矛盾。
- **情況 2**：如果 e 的花費比 f 大，那麼在 Kruskal 演算法中，f 早就應該被選擇，而不是 e，這也導致矛盾。
- **唯一可能**：e 和 f 的花費相同，因此 U 的花費不變。

經過 k 次這樣的交換操作後，U 會變成 T，並且 U 的花費保持不變。這證明了 T 的花費和 U 相同，證明了 T 是最小花費的生成樹。

---

### 圖示化過程

假設初始的生成樹 T 和 U 如下：

T 的邊集合：{a, b, c}
U 的邊集合：{d, b, c}