离散课件图论课件图论-5.pdfVIP

图 论 §12 树 2001.12 1 图 论 树、有向树、有序树 目的：树的六种定义，了解分支、森林、生成树、生成森 林、最小生成树、枝、弦、基本回路、有向树、有 向森林、二叉树、最优二叉树、有序树、有序森林、 定位二元有序树等概念和性质；掌握求最小生成树、 最优二叉树的算法、定位二元有序树和有序森林的 双射关系，以及有关的证明方法； 重点：树的六种定义，各种概念、算法及基本的证明思 路； 难点：通过树的六种定义方式如何发现树的各种性质，大 量相关知识点在证明种的综合运用。 2001.12 2 图 论 树 非循环的连通无向图称为树。 2001.12 3 图 论 平凡树：只有一个定点的无向图 树叶：树T中，次（度）数为一的顶点称为树叶 分支顶点：树T中，次（度）数大于1的顶点称为分支 顶点 2001.12 4 图 论 定理7.6.1 设 G ＝ 〈Ｖ，Ｅ，Ψ 〉是 n 阶无向图。可以下六个条件等价: i) G 是连通的，又是非循环的。 ii) G 没有自圈，并且对于 G 的任意两结点 v 和 v′，在 G 中 存在唯一的一条从 v 至 v′的基本路径。 iii) G 是连通的，如果 v 和 v′是 G 的两结点，e 不是 G 的边，当令 Ψ′= { 〈e，{v，v ′}〉}时，则 G ＋{e} 有唯一的一条回路。 Ψ′ iv)  G 是连通的，并且对于 G 的任意边 e，G – e 非连通。 v)  G是连通的，并且有 n – 1 条边。 vi)  G是非循环的，并且有 n – 1 条边。 证明参见 P145 – 146 （P193 ）。 2001.12 5 图 论 12.2 T G(n,m) m = n-1 定理 ：设树 是⼀个 图，则 。 证明：用归纳法证明，对T的顶点数 n 进行归纳。 对于n = 1 和n =2，定