离散数学课件-16-树.pdfVIP

第十六章 树 §1 无向树及性质 定义 连通且无圈的无向图称为无向树，简称 树。至少有两个连通分支的无圈的无向图称为森林， 平凡图称为平凡树。 无向树中，悬挂点称为树叶，度大于或等于 2 的顶点称为分支点。 定理 非平凡无向树至少有两片树叶。 证明 设 T 是平凡无向树，有x 片树叶，则 2(| V(T) | −1) Σ d( v) =≥ x +2(| V(T) | −x) v∈V (T ) 由此得x ≥2 。 定理 设 G= 〈V,E 〉是一个有 m 条边的 n 阶无 向图，则下面说法等价： (1) G 是树 (2) G 中任意两顶点间存在唯一路径 1 (3) G 中无圈且m=n-1 (4) G 连通且 m=n-1 (5) G 连通且 G 的每条边都是割边 (6) G 不含圈，但 G 中任两个顶点间加一条新 边，在所得图中得到唯一的一个含新边的图。 例、画出全部 6 阶非同构的无向树 解 设 T 是一棵 6 阶无向树，则 | E (T ) | 5, δ(T ) =≥1, Δ(T ) ≤5 因此，T 的度序列只可能为 (1)1,1,1,1,1,5 (2)1,1,1,1,2,4 (1) (3)1,1,1,1,3,3 (4)1,1,1,2,2,3 (5)1,1,2,2,2,2 (2) (5) (3) (4) ， 2 例 已知一棵7 阶无向树有三片树叶，一个 3 度 点，其余顶点的度非 1、非 3 。画出对应的非同构的 无向树。 解 若 T 是 7 阶无向树，则 |E(T)|=6 。设其余3 个顶点为 v ,v ,v ，则 1 2 3 2×6=1×3+3×1+d(v )+d(v )+d(v ) 1 2 3 从而 d(v )+d(v )+d(v )=6 1 2 3 已知 1d(v )≤6，故它们只可能取2,2,2 ，据此得 i T 的度序列为 1,1,1,2,2,2,3 §2 生成树 定义 设 G 是一个无向图，T 是 G 的生成子图。 若 T 是树，则称 T 是 G 的生成树。 3 注 ① ∀e ∈E(G) ， 树枝 e ∈E (T ) ， 弦 e ∉E (T ) ② G[E(G)-E(T)]称为 T 的余树，记为T 定理 无向图 G 有生成树 ⇔G 连通 推论 (1) 若 G 是连通无向图，则 |E(G)|≥|V(G)|-1； (2) 若 G 是连通无向图，T 是 G 的生成树，则 T 有 |E(G)|-|V(G)|+1 条弦； (3) 若 G 是连通无向图，T 是 G 的生成树，C 是 G 的一个圈，则E (T ) ∩E (C ) ≠∅； (4)