圖論 - 樹
樹是不包含任何環的圖。它們以圖形形式表示層次結構。樹屬於最簡單的圖類。儘管它們很簡單，但它們具有豐富的結構。
樹提供了各種有用的應用，從簡單的家譜到計算機科學中資料結構中的複雜樹。
樹
一個連通無環圖稱為樹。換句話說，一個沒有環的連通圖稱為樹。
樹的邊稱為分支。樹的元素稱為節點。沒有子節點的節點稱為葉子節點。
一個有'n'個頂點的樹有'n-1'條邊。如果它比'n-1'多一條邊，那麼這條額外的邊顯然必須與兩個頂點配對，從而形成一個環。然後，它就變成了一個迴圈圖，這違反了樹圖的定義。
示例 1
此處顯示的圖是一個樹，因為它沒有環並且是連通的。它有四個頂點和三條邊，即對於'n'個頂點有'n-1'條邊，如定義中所述。
注意 - 每棵樹至少有兩個度數為一的頂點。
示例 2
在上面的示例中，頂點'a'和'd'的度數為一。而其他兩個頂點'b'和'c'的度數為二。這是可能的，因為為了不形成環，圖中應該至少有兩個單邊。它只不過是兩個度數為一的邊。
森林
一個不連通無環圖稱為森林。換句話說，樹的互不相連的集合稱為森林。
示例
下面的圖看起來像兩個子圖；但它是一個單獨的不連通圖。此圖中沒有環。因此，它顯然是一個森林。
生成樹
設 G 為一個連通圖，則 G 的子圖 H 稱為 G 的生成樹，如果 -
- H 是一棵樹
- H 包含 G 的所有頂點。
無向圖 G 的生成樹 T 是包含 G 所有頂點的子圖。
示例
在上面的示例中，G 是一個連通圖，H 是 G 的子圖。
顯然，圖 H 沒有環，它是一棵有六條邊的樹，比頂點總數少一條。因此，H 是 G 的生成樹。
迴路秩
設'G'為一個有'n'個頂點和'm'條邊的連通圖。G 的生成樹'T'包含 (n-1) 條邊。
因此，為了得到生成樹，你需要從'G'中刪除的邊的數量 = m-(n-1)，這稱為 G 的迴路秩。
這個公式是正確的，因為在生成樹中，你需要有'n-1'條邊。在'm'條邊中，你需要在圖中保留'n–1'條邊。
因此，從'm'中刪除'n–1'條邊得到需要從圖中刪除的邊，以獲得生成樹，這應該不會形成環。
示例
看看下面的圖 -
對於上面示例中給出的圖，你有 m=7 條邊和 n=5 個頂點。
則迴路秩為 -
示例
設'G'為一個有六個頂點的連通圖，每個頂點的度數為三。求'G'的迴路秩。
根據頂點度數和定理，
基爾霍夫定理
基爾霍夫定理用於求解從連通圖中可以形成的生成樹的數量。
示例
矩陣'A'填充如下，如果兩個頂點之間有邊，則應將其設定為'1'，否則為'0'。
$$A=\begin{vmatrix}0 & a & b & c & d\\a & 0 & 1 & 1 & 1 \\b & 1 & 0 & 0 & 1\\c & 1 & 0 & 0 & 1\\d & 1 & 1 & 1 & 0 \end{vmatrix} = \begin{vmatrix} 0 & 1 & 1 & 1\\1 & 0 & 0 & 1\\1 & 0 & 0 & 1\\1 & 1 & 1 & 0\end{vmatrix}$$利用基爾霍夫定理，應將其更改為將主對角線上的值替換為頂點的度數，其他所有元素替換為 -1.A
$$=\begin{vmatrix} 3 & -1 & -1 & -1\\-1 & 2 & 0 & -1\\-1 & 0 & 2 & -1\\-1 & -1 & -1 & 3 \end{vmatrix}=M$$ $$M=\begin{vmatrix}3 & -1 & -1 & -1\\-1 & 2 & 0 & -1\\-1 & 0 & 2 & -1\\-1 & -1 & -1 & 3 \end{vmatrix} =8$$ $$Co\:\:factor\:\:of\:\:m1\:\:= \begin{vmatrix} 2 & 0 & -1\\0 & 2 & -1\\-1 & -1 & 3\end{vmatrix}$$因此，生成樹的數量 = 8。