什么是有向树?

Question

如题所述

Answer 1

如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一棵有向树。

示例：

1、无向图中的极大连通子图称为连通分量。强调：要是子图；子图要是连通的；连通子图含有极大顶点数；具有极大顶点数的连通子图包含依附于这些顶点的所有边。

2、从Vi到Vj和从Vi到Vj都存在路径，则称G是强连通图。有向图中的极大强连通子图称作有向图的强连通分量。

3、一个连通图的生成树是一个极小的连通子图，它含有图中全部的n各顶点，但只有足以构成一棵树的n-1条边。

4、如果一个图有n个顶点和小于n-1条边，则是非连通图，如果它多于n-1条边，必定构成一个环。不过有n-1条边并不一定是生成树。

5、如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一棵有向树。

6、一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不想交的有向树的弧。

扩展资料

1、图按照有无方向分为无向图和有向图。无向图由顶点和边构成，有向图由顶点和弧构成。弧有弧尾和弧头之分。

2、图按照边或弧的多少分稀疏图和稠密图。如果任意两个顶点之间都存在边叫完全图，有向的叫有向完全图。若无重复的边或顶点到自身的边则叫简单图。

3、图中顶点之间有领接点、依附的概念。无向图顶点的边数叫做度，有向图顶点分为入度和出度。

4、图上的边或弧上带权则称为网。

5、图中顶点间存在路径，两顶点存在路径则说明是连通的，如果路径最终回到起始点则称为环，当中不重复叫简单路径。若任意两顶点都是连通的，则图就是连通图，有向则称强连通图。图中有子图，若子图极大连通则就是连通分量，有向则称强连通分量。

6、无向图中连通且n个顶点n-1条边叫生成树。有向图中一顶点入度为0，其余顶点入度为1的叫有向树。一个有向图由若干棵有向树构成生成森林。