树

树

• 无向树：连通无回路的无向图，简称树。
• 平凡树：平凡图。
• 森林：有若干个不相交的树组成的图。
• 树叶：度为1的节点。
• 分支点：度大于1的节点。

无向树的等价定义

• $G$ 是树（连通无回路）。
• $G$ 中任意两个顶点之间存在惟一的路径。
• $G$ 中无回路且 $m=n-1$.。
• $G$ 是连通的且 $m=n-1$。
• $G$ 是连通的且 $G$ 中任何边均为桥。
• $G$ 中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到惟一的一个含新边的圈.。

无向树的性质

设 $T$ 是 $n$ 阶非平凡的无向树，则 $T$ 中至少有两片树叶。