树或连通无环图

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

树提供了一系列有用的应用，从简单的家谱到计算机科学数据结构中的复杂树。

树

一个**连通无环图**称为树。换句话说，一个没有循环的连通图称为树。

树的边称为**分支**。树的元素称为它们的**节点**。没有子节点的节点称为**叶子节点**。

具有'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 的生成树。

Mahesh Parahar

更新于： 2019年8月23日

2K+ 浏览量

开启你的 职业生涯

通过完成课程获得认证

开始学习