树的等价定义-Read.PPT

第 五 章 图 论 5.3 树 1. 无向树 2. 有向树 3. 周游算法 4. 前缀码与最优树 5.3.1 无向树 树的定义（6个等价定义） 树的性质 生成树的定义 求最小生成树的算法 树的基本概念 由英国数学家亚瑟·凯来（Arthur Cay ley，1821-1895）在试图列举形为CnH2n+2的化合物的同分异构体时发现了树图。 树具有广泛的应用，特别是在计算机科学和管理科学中。如： 用树构造存储和传输数据的有效编码 用树模拟决策过程 无向树的定义 [定义]（无向）树 一个连通且无回路的无向图称为无向树，或简称为树。 树中度数为1 的结点称为树叶，度数大于1的结点称为内结点或分枝点。 每个连通分支都是无向树的图称为森林。 无向树的等价定义 给定无向图T=(V,E)，以下语句是等价的： （1）T是无向树； （2）T是无回路，并且|E| = |V| - 1的图； （3）T是连通的，并且|E| = |V| - 1的图； （4）T是无回路，但增加任一新边，得到一个且仅有一个回路的图； （5）T是连通的，但删去任一边后便不连通的图； （6）T是每一对结点间有一条且仅有一条路的图。 无向树的等价定义（证明1） 证：（1）? （2） 即：T是无向树 ? T是无回路并且|E| = |V| -1的图 证明：从顶点数考虑，作归纳证明。 ① 当|V| = 2时，由T是无回路的连通图可知：T中边数|E| = 1，∴ |E| = |V| -1成立 ② 假设当|V| = k - 1时命题成立。 ③ 则当v = k时，∵图T连通且无回路，故至少有一条边的一个端点u的度数为1。 无向树的等价定义（证明1）续1 证：（1）? （2） 即：T是无向树 ? T是无回路并且|E| = |V| -1的图 证明(续)：续③. 设与u相关联的边为eu，在T中删去顶点u (u的度为1)及eu，得k-1个顶点的连通且无回路的图T?=V’, E’。 由归纳假设，图T?的边数: /* ② 中假设“当|V| = k-1时命题成立”*/ |E?| = |V?| -1 =（k-1）- 1 = k-2。 于是原图T的边数为 |E| = |E?| + 1 =（k-2）+ 1 = k-1 ， 结点数 : |V| = |V?| + 1 =（k-1）+ 1 = k ∴ |E| = |V| -1成立。 无向树的等价定义（证明2） 证：（2）? （3） 即：T是无回路，并且|E| = |V| -1的图 ? T是连通且|E| = |V| -1的图 证：反证法. 设T(V, E)不连通，有k个连通分支T1 ... Tk (k≥2)，顶点数为|V1| ... |Vk|, 边数为|E1|...|Ek|。而每个连通分支是无回路连通图，则由(1) ?(2)得: |Ei| = |Vi| - 1。 而: |V| = |V1| + |V2| + …+ |Vk|, |E| = |E1| + |E2| + …+ |Ek| = (|V1| -1) + (|V2| -1) + …+ (|Vk| -1) = |V| - k（k≥2） 但这与前提|E| = |V| -1相矛盾。 故T是连通且|E| = |V| -1的图 树的等价定义（证明3） 证：（3）?（4） 即：T是连通且|E| = |V| -1的图 ? T是无回路，但增加任一新边，得到一个且仅有一个回路的图。 证明： (归纳法) 。 ① 当|V| = 2时，|E| = |V| -1 = 1，故T必无回路。如增加一边，得到一个且仅得到一个回路。 ② 假设当v = k-1时命题成立。 树的等价定义（证明3）续1 证：（3）?（4） 即：T是连通且|E| = |V| -1的图 ? T是无回路，但增加任一新边，得到一个且仅有一个回路的图。 证明（续）： ③当|V| = k时 因T是连通且|E| = |V| -1。故每个结点u有d(u)?1。 断言1：至少有一个结点u0满足：d(u0)= 1。 如果断言不成立，则所有的结点u都有d(u)?2。 则2|E| ?2|V| ，即|E| ? |V| 。与前提|E| = |V| -1矛盾。 无向树的等价定义（证明3）续2 证明（续）： ④