树或连接的非循环图

树是甚至不包含单个循环的图。它们以图形形式表示层次结构。树属于最简单的图类。尽管它们很简单，但是它们具有丰富的结构。

树提供了一系列有用的应用程序，例如从家族树到计算机科学数据结构中的树，都非常简单。

树

阿连接无环图被称为一个树。换句话说，没有周期的连接图称为树。

一棵树的边缘被称为树枝。树的元素称为它们的节点。没有子节点的节点称为叶节点。

具有“ n”个顶点的树具有“ n-1”个边。如果它的边缘比“ n-1”多一个，则该明显的边缘显然必须与两个顶点配对，从而形成一个循环。然后，它变成一个循环图，它违反了树图。

例子1

此处显示的图是一棵树，因为它没有循环并且已连接。它具有四个顶点和三个边缘，即定义中提到的'n'个顶点'n-1'个边缘。

注-每棵树至少有两个度数为1的顶点。

例子2

在上面的示例中，顶点“ a”和“ d”的度为一。而另外两个顶点“ b”和“ c”具有第二度。这是可能的，因为为了不形成循环，图形中的任何地方都应该至少有两个单边。它不过是两个边缘的一阶边缘。

森林

一个断开无环图被称为林。换句话说，不相交的树木集合称为森林。

示例

下图看起来像两个子图；但这是一个断开的图。该图中没有周期。因此，显然这是一片森林。

生成树

假设G是一个连通图，则在以下情况下，G的子图H称为G的生成树：

• H是一棵树

• H包含G的所有顶点。

无向图G的生成树T是包含G的所有顶点的子图。

示例

在上面的示例中，G是连接图，H是G的子图。

显然，图H没有循环，它是一棵有六个边的树，比顶点总数少一个。因此H是G的生成树。