2.1树的基本性质描述.ppt

二、树的中心点 问题的提出：有下列若干居民区，居民 区间的距离如下图所示，问医院应建在哪 个居民区才能使最远居民区的人到医院看 病所走的路最短？ 证明： （1）由于树 中只有唯一的一条 路 ，故 ，又因 是树 的一条最 长路，故 即为 的直径。 （2）分二步进行： 1。证明 ，有 ： 事实上， ，我们有 2。证明 和 ： 事实上，对每个 ，若 ，明显 的有 。 若 ；取 中一条 路 。 令 与 的第一个交点为 。记 由 的最长性，有 和 。 下分 和 ，可以证明 3。证明任意一条长为 的路一定通过 和 该定理说明了树的中心点必定出现树的最长路上，且中心点只有1个或2个 求树的中心点方法： 首先将树 中的叶全部删除 ，所得到的树 与 有相同的中心点，照此进行，直到留下1 个点或2个点，即为 中心点。 * CH 2 树 §2.1 树的特性 定义2.1.1 没有回路的连通图称为树，一般用 表示一棵树。 例：左图是两棵有4个顶点的树。 注: 只有一个顶点的树就是K1 这一节我们介绍一类特殊的连通图——树。 返回 结束 一、树的特征 是树，则若 ，就有 。事实上，由于 连通且 ，必有 。若 ，利用定理2.1.1， 中有回路，与 是树矛盾。从而 是树，若 ，就有 。 定理2.1.1 一个简单图 是树当且仅当 中任意两个不同顶点之间有且只有一条路连接。 注： 若一个图 是树，且设 中 两个不同顶点 的 路为 ， 则 。 返回 结束 性质 是树 若 ，就有 ； 定理2.1.2 下述论断是等价的： 1.??图 是树（连通，无回路）； 2.?????? 连通且 ； 3.?????? 无回路且 ； 4.?????? 连通且 的每一条边都是割边； 5.?????? 无回路且对 中任意两个不相邻的顶点 ， 有且只有一个回路。 注： 1. 由定理2： 连通，则 。可见树是边数最少的连通图。事实上，树 也是最简单的连通图； 2. 由论断1，2与3可知，连通、无回路与 这三条性质中的任意两条都足以保证 是树，因而都可以作为树的定义。 返回 结束 下面我们证1，2，3，4，5等价。证明方法 。 证： 设 是树，对 用归纳法证明。 时， 成立。 假设 时命题成立（即有 ）。则考虑 阶树 。由于 无回路，由前面性质有 。设