图论 - 树
树是不包含任何环的图。它们以图形形式表示层次结构。树属于最简单的图类。尽管它们很简单，但它们具有丰富的结构。
树提供了各种有用的应用，从简单的家谱到计算机科学中数据结构中的复杂树。
树
一个连通无环图称为树。换句话说，一个没有环的连通图称为树。
树的边称为分支。树的元素称为节点。没有子节点的节点称为叶子节点。
一个有'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。