A-level 數學/OCR/D1/節點圖/生成樹
在本模組中，我們將介紹生成樹的概念，最小生成樹，以及找到最小生成樹的一些方法。
首先，我們必須說明我們所說的樹是什麼意思。樹是一個圖，其中任意一對頂點之間只有一條路徑。這意味著樹是連通的，即每對點之間至少存在一條路徑。
樹是連線一組頂點的最有效方式，從某種意義上說，如果我們有一棵樹，那麼每條邊都是必要的，因為如果我們移除任何邊，那麼圖就不再是連通的。此外，所有具有 n 個頂點的圖上的樹都恰好有 n - 1 條邊。
如果我們有一個連通圖 G，那麼另一個圖 H 是 G 的生成樹，如果它是與 G 具有相同頂點的樹，並且 H 的所有邊都是 G 的邊。
最後，我們將介紹最小生成樹的概念。為了使這有意義，我們必須考慮稱為網路的圖。網路是圖，其中每條邊都有一個權重。權重可以是邊的長度，或兩點之間的距離，或者可以表示兩點之間移動的難度，或者成本。在任何情況下，權重都是一個數字。它通常是正的（或非負的，零是可能的），但如果我們允許負數，數學原理也是相同的。由於圖的每條邊都被分配了一個距離，而不是頂點對本身，因此沒有為沒有邊連線的頂點對分配距離。
給定一個圖 G，其邊分配有距離，那麼最小生成樹 H 是 G 的生成樹，其中邊的權重之和儘可能低。可能存在多個最小生成樹。舉一個簡單的例子，任何具有所有權重為 1 的圖 G 的生成樹都將是一個最小生成樹，相關總和等於 n-1，其中 n 是原始圖的頂點數。
克魯斯卡爾演算法是為網路 G 尋找最小生成樹的一種方法。我們從一個由 G 的所有頂點組成的圖 H 開始，但沒有邊。然後我們按照以下說明進行
- 考慮 G 中的邊集 E，這些邊在新增到 H 時將連線端點
- 找到 E 中權重最低的成員。如果有多個這樣的成員，選擇任意一個。
- 將此邊新增到 H 中
- 如果 H 未連線，則返回步驟 1。否則，H 是 G 的最小生成樹。
上面是圖的圖 (圖 1)，將使用克魯斯卡爾演算法為其構建生成樹。每條邊都給出了權重。這些線是點狀的，因為生成樹的邊將用實線表示。
下面是圖 2 到 5，它們指示生成樹構建的階段。
在圖 2 中，我們添加了一條權重為 2 的邊，因為它是權重最低的邊。對於圖 3，有兩個選項，權重均為 3，可以新增。請注意，新增的邊未連線到第一條邊。在該演算法下允許這樣做，但在下面描述的普里姆演算法下不允許這樣做。在圖 4 中，添加了另一個權重為 3 的邊。最後，在圖 5 中，我們添加了一條權重為 6 的邊，其中有兩個允許的邊。存在權重更低的邊，例如權重為 4 的邊，但它們都連線了我們已經連線的邊。最終的生成樹在下面的圖 6 中給出，原始圖中的其他邊及其權重未給出。總權重為 2+3+3+6 = 14。
普里姆演算法是為網路 G 尋找最小生成樹的另一種方法。我們再次從一個由 G 的所有頂點組成的圖 H 開始，但沒有邊。然後我們按照以下說明進行
- 在圖中選擇任意頂點 v
- 使其成為集合 S 的唯一成員
- 考慮連線 S 的一個成員到不在 S 中的頂點的邊集 E。
- 找到 E 中權重最低的成員。如果有多個這樣的成員，選擇任意一個。
- 將此邊新增到 H 中，並將不在 S 中的頂點新增到 S 中。
- 如果 H 未連線，則返回步驟 3。否則，H 是 G 的最小生成樹。
上面是圖 7，它與圖 1 相同，是用於克魯斯卡爾演算法示例的圖。我們將構建一個不同的生成樹，儘管可以保證總權重將相同。第一步是選擇一個頂點作為起點。這將是最上面的頂點。下面是圖 8 到 11，生成樹構建的階段。
在開始時，只有最上面的頂點在 S 中。S 與其他頂點之間權重最低的邊是那些權重為 6 的邊，因此在圖 8 中選擇了一個邊，從而將中間右邊的頂點新增到 S 中。在圖 9 中，添加了權重為 2 的邊，將右下方的頂點新增到 S 中。在圖 10 中，添加了一個權重為 3 的邊，另一個邊在兩端都沒有 S 中的頂點。然後在圖 11 中添加了此邊。現在允許這樣做，因為中間左邊的頂點在圖 10 中被新增到 S 中。最終的生成樹在下面的圖 12 中給出。總權重再次為 2+3+3+6=14，儘管實際的生成樹與克魯斯卡爾演算法不同。
當我們感興趣的圖是矩陣形式時，找到最小生成樹的另一種方法。在這種情況下，矩陣只是一個數字表，這些數字對應於邊的權重。例如，下面是表 1，是我們一直在示例中使用的圖的矩陣形式，以及圖 13，熟悉的圖形表示
|
|
這些頂點被賦予 1 到 5 的數字，其中 1 是最上面的頂點，2 和 3 是中間左側和中間右側的頂點，而 4 和 5 是左下和右下方的頂點。行和列標題對應於這些數字，其他數字是相應邊的權重。例如，第 1 行第 2 列中的數字 8 是頂點 2 和 3 之間邊的權重 8。請注意，矩陣中存在對稱性，例如第 2 行第 1 列也是 8。這是因為例如，頂點 1 和 2 之間的邊也是頂點 2 和 1 之間的邊。此外，頂點與自身之間沒有邊，因此第 1 行第 1 列、第 2 行第 2 列等都是空的。
使用這種形式，我們可以應用普里姆演算法來找到最小生成樹。我們將從頂點 4 開始，使其成為 S 的唯一成員。為了表示這一點，我們將它加粗，以後也會對 S 的其他成員進行加粗。你可以使用任何你想要的方法來表示 S 的成員，例如畫圈。下面是表 2，其中頂點 4 被標記為 S 的成員。
| 1 | 2 | 3 | 4 | 5 | |
| 1 | 8 | 6 | 6 | 9 | |
| 2 | 8 | 3 | 3 | 4 | |
| 3 | 6 | 3 | 5 | 2 | |
| 4 | 6 | 3 | 5 | 7 | |
| 5 | 9 | 4 | 2 | 7 |
現在，我們必須選擇下一條邊。它將有一個頂點在 S 中，一個頂點不在 S 中。這些對應於第 4 行（加粗的）中的數字，它不與第 4 列（也加粗的）交叉。這給出了數字 6、3、5 和 7，其中最小的是 3，對應於第 4 行第 2 列，因此是頂點 4 和 2 之間的邊。因此，我們將此新增到我們的樹中，並將 2 新增到 S 中。下面是表 3，其中 2 和 4（S 的成員）都加粗了。
| 1 | 2 | 3 | 4 | 5 | |
| 1 | 8 | 6 | 6 | 9 | |
| 2 | 8 | 3 | 3 | 4 | |
| 3 | 6 | 3 | 5 | 2 | |
| 4 | 6 | 3 | 5 | 7 | |
| 5 | 9 | 4 | 2 | 7 |
現在，要選擇的邊對應於第 2 行和第 4 行（加粗的）中的數字，但不對應於第 2 列和第 4 列中的數字。這給出了數字 8、3、4、6、5 和 7。最小的是 3，對應於頂點 2 和 3 之間的邊。因此，我們將 3 新增到 S 中，並將此邊新增到我們的樹中。下面是表 4，其中 3 現在加粗了。
| 1 | 2 | 3 | 4 | 5 | |
| 1 | 8 | 6 | 6 | 9 | |
| 2 | 8 | 3 | 3 | 4 | |
| 3 | 6 | 3 | 5 | 2 | |
| 4 | 6 | 3 | 5 | 7 | |
| 5 | 9 | 4 | 2 | 7 |
現在，我們有數字 8、4、6、2、5 和 7。最小的是 2，對應於頂點 3 到 5 之間的邊。因此，我們將此邊新增到我們的樹中，並將頂點 5 新增到 S 中。在表 5 中，此頂點被新增到 S 中，因此加粗了。
| 1 | 2 | 3 | 4 | 5 | |
| 1 | 8 | 6 | 6 | 9 | |
| 2 | 8 | 3 | 3 | 4 | |
| 3 | 6 | 3 | 5 | 2 | |
| 4 | 6 | 3 | 5 | 7 | |
| 5 | 9 | 4 | 2 | 7 |
這裡，數字分別是 8、6、6 和 9。因此，有兩個可能的邊，分別是 1 與 3 或 4 之間的邊。之前的邊分別為 4 與 2、2 與 3 以及 3 與 5 之間的邊。以下是圖 14 和 15，它們分別顯示了選擇其中一條邊形成的生成樹。圖 14 中的邊連線了頂點 1 和 3，而圖 15 中的邊連線了頂點 1 和 4。
注意，這些分別是普里姆演算法和克魯斯卡爾演算法生成的生成樹。還要注意，在尋找最小數字時，我們只考慮了 S 的成員是行，非成員是列的情況。這樣就忽略了 S 的成員是列，非成員是行的可能性。然而，正如我們之前討論的那樣，每條邊都會列出兩次，而我們考慮元素的方式只包含每條邊一次。例如，如果 1 在 S 中，而 2 不在 S 中，那麼我們將它們之間的邊包含在第 1 行第 2 列，但不包含在第 2 行第 1 列。