图论 王智慧 复旦大学计算机学院
图论 王智慧 复旦大学计算机学院
树 无向树及其性质 ·生成树 根树及其应用
2 树 • 无向树及其性质 • 生成树 • 根树及其应用
无向树的定义 定义1 连通无回路的无向图称为无向树,或简称树,常用T表示树 平凡图称为平凡树;若无向图G至少有两个连通分支,每个连通 都是树,则称G为森林 在无向树中,悬挂顶点称为树叶;度数大于或等于2的顶点 称为分支点
3 无向树的定义 定义1. 连通无回路的无向图称为无向树, 或简称树, 常用T表示树 平凡图称为平凡树; 若无向图G至少有两个连通分支, 每个连通 都是树, 则称G为森林. 在无向树中, 悬挂顶点称为树叶; 度数大于或等于2的顶点 称为分支点
无向树的性质 无向树有许多性质,其中一些是树的充要条件,可看作是树的 等价定义 定理1.设G=<V,E>是n阶m条边的无向图,则下面各命题是等价的: (1)G是树 (2)G中任意两个顶点之间存在唯一的路径 (3)G中无回路,且m=n-1 (4)G是连通的,且m=n-1 (5)G是连通的,且G中任何边均为桥 (6)G中没有回路,但在任何两个不同的顶点之间加一条新边,在 所得图中得到唯一的一个含新边的圈
4 无向树的性质 (1) G是树 (2) G中任意两个顶点之间存在唯一的路径 (3) G中无回路, 且m = n-1 (4) G是连通的, 且m = n-1 (5) G是连通的, 且G中任何边均为桥 (6) G中没有回路, 但在任何两个不同的顶点之间加一条新边, 在 所得图中得到唯一的一个含新边的圈 无向树有许多性质, 其中一些是树的充要条件, 可看作是树的 等价定义。 定理1. 设G = <V, E>是n阶m条边的无向图, 则下面各命题是等价的:
无向树的性质 定理1 (1)G是树;(2)G中任意两个顶点之间存在唯一的路径 证明:(1)→(2) 由树的定义可知u,v∈G(V),u与V之间存在路径。若路径 不是唯一的,设∏1与2都是u到v的路径,那么必存在由1和2上边 构成的回路,这就与G中无回路矛盾 5
5 无向树的性质 证明: (1) ⇒ (2). 由树的定义可知 ∀u,v∈G(V), u与v之间存在路径。若路径 不是唯一的, 设Γ1与Γ2都是u到v的路径, 那么必存在由Γ1和Γ2上边 构成的回路, 这就与G中无回路矛盾。 定理1. (1) G是树; (2) G中任意两个顶点之间存在唯一的路径