图论 - 树
树是甚至不包含单个循环的图。它们以图形形式表示层次结构。树属于最简单的图类。尽管它们很简单，但它们具有丰富的结构。
树提供了一系列有用的应用程序，从简单的家谱到复杂的计算机科学数据结构中的树。
树
连接的无环图称为树。换句话说，没有环的连通图称为树。
树的边缘称为分支。树的元素称为节点。没有子节点的节点称为叶节点。
具有“n”个顶点的树有“n-1”条边。如果它比“n-1”多一条边，那么额外的边显然必须与两个顶点配对，从而形成一个循环。然后，它就变成了循环图，这违反了树图。
实施例1
这里显示的图是一棵树，因为它没有循环并且是相连的。它有四个顶点和三个边，即定义中提到的“n”个顶点有“n-1”条边。
注意- 每棵树至少有两个一级顶点。
实施例2
在上面的示例中，顶点“a”和“d”的度数为 1。另外两个顶点 'b' 和 'c' 的度数为 2。这是可能的，因为为了不形成环，图中的任何位置都应该至少有两个单边。它只不过是两条度数为 1 的边。
森林
断开的无环图称为森林。换句话说，不相交的树木集合称为森林。
例子
下图看起来像两个子图；但它是一个单独的断开连接的图。该图中没有循环。因此，显然这是一片森林。
生成树
设 G 是连通图，则 G 的子图 H 称为 G 的生成树，如果 -
- H是一棵树
- H包含G的所有顶点。
无向图 G 的生成树 T 是包含 G 的所有顶点的子图。
例子
在上面的例子中，G是连通图，H是G的子图。
显然，图H没有环，它是一棵有6条边的树，边数比总顶点数少1条。因此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\:\:m1\:\:= \begin{vmatrix 的因子\:\: } 2 & 0 & -1\\0 & 2 & -1\\-1 & -1 & 3\end{vmatrix}$$因此，生成树的数量 = 8。