图论/树

树是一种连通图。有向图是树，如果它是连通的，没有环，并且所有顶点最多有一个父节点。无向图被认为是树，如果它是连通的，有$|V|-1$条边，并且是无环的（满足其中两个属性的图就满足所有三个属性）。

练习：等价定义 证明以下是对树的等价定义 具有最小边数且连通的图。 具有最大边数且无环的图。 无环图，在其中添加任何边都会创建一个环。 具有 n 个节点和 n-1 条边且连通的图。 任何两个节点都通过唯一的路径连接的图（路径边只能遍历一次）。 提示：为了使总证明简短，以合适的顺序排列定义，然后证明 A=>B=>C=>D=>E=>A。尤其要注意具有零个和一个节点的图。 此外， 图是连通的，并且每条边都是桥。

$tree$

无环且连通的$graph$.
$forest$是无环图。所以，$tree\subseteq forest$

�意义

• 树 : 最小尺寸连通图
• 环 : 最小尺寸 2-连通图