生成樹

什麼是生成樹？

生成樹是圖G的一個子集，它包含所有頂點，並且邊數最少。因此，生成樹不包含環路，並且不能是斷開的。

根據這個定義，我們可以得出結論，每個連通且無向的圖G至少有一棵生成樹。斷開的圖沒有任何生成樹，因為它無法擴充套件到所有頂點。

我們找到了一個完整圖的三個生成樹。一個完整的無向圖最多可以有n^n-2個生成樹，其中n是節點數。在上面提到的例子中，n是3，因此可以有3³⁻² = 3個生成樹。

生成樹的一般屬性

現在我們瞭解了一個圖可以有多個生成樹。以下是與圖G相關的生成樹的一些屬性：

• 一個連通圖G可以有多個生成樹。

• 圖G的所有可能的生成樹具有相同數量的邊和頂點。

• 生成樹不包含任何環路（迴路）。

• 從生成樹中移除一條邊將使圖斷開，即生成樹是最小連通的。

• 向生成樹中新增一條邊將建立一個迴路或環路，即生成樹是最大無環的。

生成樹的數學性質

• 生成樹有n-1條邊，其中n是節點（頂點）的數量。

• 從一個完整圖中，透過移除最多e - n + 1條邊，我們可以構建一棵生成樹。

• 一個完整圖最多可以有n^n-2個生成樹。

因此，我們可以得出結論，生成樹是連通圖G的一個子集，而斷開的圖沒有生成樹。

生成樹的應用

生成樹主要用於找到連線圖中所有節點的最小路徑。生成樹的常見應用包括：

• 民用網路規劃

• 計算機網路路由協議

• 聚類分析

讓我們透過一個簡單的例子來理解這一點。假設城市網路是一個巨大的圖，現在計劃以最少的線路部署電話線路，以便連線到所有城市節點。這就是生成樹發揮作用的地方。

最小生成樹 (MST)

在帶權圖中，最小生成樹是指權重小於同一圖中所有其他生成樹的生成樹。在現實情況下，此權重可以測量為距離、擁塞、交通負載或分配給邊的任何任意值。

最小生成樹演算法

我們將在本文中學習兩種最重要的生成樹演算法：

• 克魯斯卡爾演算法

• 普里姆演算法

這兩種演算法都是貪心演算法。