第三章树3.1树的有关定义给定一个图G=(V,E)，如果它不含任何回路我们就叫它是林，如果G又是连通的，即这个林只有一个连通支，就称它是树
第三章 树 3.1 树的有关定义 ⚫ 给定一个图 ，如果它不含任何回路， 我们就叫它是林，如果 又是连通的，即这个林 只有一个连通支，就称它是树。 G = (V,E) G
树的有关定义定义3.1.1一个不含任何回路的连通图称为树，用T表示T中的边称为树支，度为1的节点称为树叶。树的每条边，都不会属于任何回路。这样的边叫割边
树的有关定义 ⚫ 定义3.1.1 一个不含任何回路的连通图称为树，用 表示。 中的边称为树支，度为1的节点称为树叶。 树的每条边，都不会属于任何回路。这样的边叫 割边。 T T
树的有关定义定义3.1.2设e是G的一条边，若G=G一e比G的连通支树连通支数增加，则称e是G的一条割边显然，图G删去割边e=(u,V)之后，结点u,v分属于不同的分支
树的有关定义 ⚫ 定义3.1.2 设 是 的一条边，若 比 的连通支树连 通支数增加，则称 是 的一条割边。 显然，图 删去割边 之后，结点 分属 于不同的分支。 e G G' = G−e G e G G e = (u,v) u, v
树的有关定义定理3.1.1e=(u,v)是割边，当且仅当e不属于G的任何回路。证明：若e=(u,v)属于G的某个回路，则G=G-e中仍存在u到v的道路，故结点u和v属于同一连通支，e不是割边。反之，若e不是割边，则G与G的连通支数一样。于是u和V仍属于同一连同支，故G中存在道路 P(u,v),P(u,v)+e就是G的一个回路
树的有关定义 ⚫ 定理3.1.1 是割边，当且仅当 不属于 的任何回路。 证明：若 属于 的某个回路，则 中仍存在 到 的道路，故结点 和 属于同一连通 支， 不是割边。反之，若 不是割边，则 与 的 连通支数一样。于是 和 仍属于同一连同支，故 中存在道路 就是 的一个回路。 u e = (u,v) e G G' = G−e G G' e = (u,v) G v G' u v e e u v P(u,v),P(u,v)+e G
树的有关定义定理3.1.2设T是结点数为n≥2的树，则下列性质等价：T连通且无回路1.T连通且每条都是割边2.T连通且有n1条边3.T有n-1条边且无回路4.T的任意两结点间有唯一道路5.T无回路,但在任两结点间加上一条边后恰有一6.个回路
树的有关定义 ⚫ 定理3.1.2 设 是结点数为 的树，则下列性质等价： 1. 连通且无回路 2. 连通且每条都是割边 3. 连通且有 条边 4. 有 条边且无回路 5. 的任意两结点间有唯一道路 6. 无回路,但在任两结点间加上一条边后恰有一 个回路 T n 2 T T T T T T n−1 n−1