复旦大学 计算机院 赵一鸣 离散数学 第七章 树.ppt

第七章 树§ 7.1树及其性质§ 定义 7.1：一个连通无回路的图称为树,记 为T树中度数为1的顶点称为树叶(或称 悬挂点)度数大于1的顶点称为分枝点 或内点不相交的树的全体称为森林 平凡图也可称为平凡树平凡图即只有 一个点)图 (a)是一棵树；(b)是森林,也就是无回 路的图,它的每个分支是一棵树§ 除了定义 7.1 给出树的定义外还有几个树的等 价定义, 即下面的定理 § 定理7.1：设图T有n个顶点,有下列6条T是树的 等价定义: § (1)T是无回路的连通图; § (2)T是无回路图,且e=n-1,其中e是边数; § (3)T是连通图,且e=n-1; § (4)T是无回路图,且在T的任两个不相邻的顶点 之间添加一边,恰得到一条回路(称T为最大无回 路图); § (5)T是连通图,但删去任一边后,便不连通(称T为 最小连通图); § (6)T的每一对不同的顶点之间有唯一的一条路 § 证明：(1)→(2): T是无回路的连通图要证明T是无回路 图,且e=n-1，即证明e=n-1 § 对顶点数n采用归纳法,n=2时,因为T是无回路的连通图 ，显然只能是下图所示：故结论成立 假设n=k时结论成立,现考察n=k+1时,由于连通无回路以 及定理 5.4 (若图G中每个顶点度数至少为2,则G包含一条回路), 可以知道至少有一个顶点度数为1的点u,它的关联边为 {u,v}。

§ (2)→(3): T是无回路图,且e=n-1,要证明T是连通 图,且e=n-1即证明T是连通图,用反证法,§ (3)→(4):在T是连通图,且e=n-1的条件下, 证明T是无回路图,且在T的任两个不相邻 的顶点之间添加一边,恰得到一条回路 § 1)首先证明T是无回路的 § 对顶点数n采用归纳法, § n=2时e=1,且连通, 只能是下图显然T是无回路的§ 假设n=k-1时结论成立,考察n=k时,由于T是连通 的,所以,每个顶点度数1(e=k-1)可以证明,至少 存在一个顶点u,使 d(u)=1Why?§ 2)再证明如果在连通图T的任两个不相邻顶 点之间添加一边,记为{vi,vj},则该边与T中 从vi到vj的一条路 § (vi,vi1,…, vis,vj) § 构成一条回路(vi,vi1,…, vis,vj,vi) § 若这条回路不唯一，由于T无回路，而 T∪{vi,vj}得到了回路，因此另一条回路C' 也含有边{vi,vj}，§ (4)→(5): 在T是无回路图,且在T的任两个 不相邻的顶点之间添加一边,恰得到一条 回路的条件下证明T是连通图,但删去任 一边后,便不连通 § 若T不连通, 则存在顶点vi和vj,在vi与vj之 间没有路。

显然,若加一边{vi,vj},不会产 生回路,与假设矛盾 § 又由于T无回路,则删去任一边,便不连通§ (5)→(6): 在T是连通图,但删去任一边后, 便不连通的条件下证明T的每一对不同的 顶点之间有唯一的一条路 § 由于T是连通的,任两点之间有一条路 如果某两个顶点之间多于一条路,则T中 必含有回路,(Why?) 删去该回路上任一边 ,图仍连通,与假设矛盾 § (6)→(1): 在T的每一对不同的顶点之间有 唯一的一条路的条件下，证明T是无回路 的连通图显然图是连通的若有回路, 则回路上任两点之间有两条路, 从而导致 矛盾§ 推论：若G是n个顶点个分支的森林, 则G 有n-条边 § 定理7.2:在任一棵非平凡树T中, 至少有两片 树叶 § 证明:由于T是连通的,对T的任一顶点 vi,d(vi)1,并且e=n-1,即所有顶点度数之和 =2(n-1). § 下面证明T中至少有两个顶点的度数为 1 7.2生成树与割集§ 例如下图中给定图G,粗线表示G的生成树 T,它的边集是{e1,e4,e5,e6},的边集是 {e2,e3,e7,e8}§ 定理7.3：G是连通图当且仅当G有生成树。

§ 证明：1) G有生成树证明G是连通图因为 生成树是连通图,生成子图连通，则原图一 定连通 § 2) G是连通图证明G有生成树 § 设G是连通图,若G没有回路,则G本身就是生 成树； § 若G只有一条回路,从这条回路中删去一条 边, 仍保持连通, 得到一棵生成树； § 若G中有多条回路, 则重复上述过程, 直到得 到一棵生成树为止§ 设连通图G有n个顶点, e条边, 那么G的任一棵 生成树有n-1条枝, e-n+1条连枝 § 设图G有n个顶点,e条边, 个分支, n,e,之间有 两个简单的关系式: § n-0; § e-n+0 § 定义 7.3:设图G有n个顶点, e条边, 个分支, 称n -为G的秩, 称e-n+为图G的零度 § 显然G的秩是G的各分支中生成树的枝数之和, G的零度是G的各分支中生成树的连枝数之和 § 对于连通图G来说, 它的秩为n-1, 零度为e-n+1 § 二、割集与断集 § 定义7.4：设D是图G的一个边集, 若在G中删 去D的全部边后所得图的秩减少 1 , 而删去D 的任何真子集均无此性质, 称D为G的割集图 (a) 中边集{e1, e3,e5,e6,e8}是 割集，但删去任何真子集不 具有此性质§ 图(b)中边集{e1, e2} 是割集 § 边集{ e1,e2,e3,e4} 不是割集,§ 定义7.5:设图G的顶点非空真子集为V1V, 在G 中一个端点在V1中, 另一端点在V(G)-V1中的所 有边组成的集合称为G的一个断集或称边割,记 为 E(V1(V(G)-V1)), 简记为(V1, V(G)-V1)。

§ 当|(V1, V(G)-V1)|=1时, (V1, V(G)-V1)中的那条 边称为割边或 桥 图 7.2(b) 中边集 {e1,e2}和 {e1,e2,e3,e4}都是 断集(边割) 割集是断集, 反 之不一定§ 定义7.5:设图G的顶点非空真子集为V1V, 在G 中一个端点在V1中, 另一端点在V(G)-V1中的所 有边组成的集合称为G的一个断集或称边割,记 为 E(V1(V(G)-V1)), 简记为(V1, V(G)-V1) § 当|(V1, V(G)-V1)|=1时, (V1, V(G)-V1)中的那条 边称为割边或 桥 图 7.2(b) 中边集 {e1,e2}和 {e1,e2,e3,e4}都是 断集(边割) 割集是断集, 反 之不一定§ 对于连通图G(V,E), 删去一个割集D, 得到 两个分支, § 顶点集分别为V1和V(G)-V1, § 割集D是G中一个端点在V1中, 另一端点 在V(G)-V1中的边的全体 § 如果在连通图G中, 删去一个断集而不是 一个割集, 那么将得到多于两个分支§ 三、割集与回路 § 定理7.4：任何一条回路和任何生成树的余树至 少有一条公共边。

§ 证明：如果一条回路和一棵生成树的余树没有 公共边, 则这回路含在该生成树中, 这是不可能 的 § 定理7.5：任何一个割集和任何生成树至少有一 条公共边 § 证明：如果一个割集和一棵生成树没有公共边, 则删去该割集后留下一棵完整的生成树, § 也就是说, 删去一个割集后, 不能将图G分为两 个分支, 这与割集的定义相矛盾§ 定理7.6：任何一个回路和任何一个割集有 偶数条公共边 § 证明：从连通图G中删去一个割集D后, 得到 两个顶点子集V1和V2, § 考察G中任一条回路C : § (1) 如果C中所有顶点在V1(或V2)中, 则C与D 没有公共边 § (2)如果C中顶点既有一些在V1中, 又有一些 在V2中, 先看D中任何一边, § 它的一个端点在V1中, 另一个端点在V2中, 且G中除D中边以外, 不再有任何边连接V1 与V2中的顶点§ 定义7.6：设连通图G中给定生成树T, 对 于只包含T中一条枝的割集,称此割集为 关于T的基本割集 § 在连通图G中, 对于给定的生成树T, 每一 枝恰对应唯一的一个基本割集 § 因为从生成树T中删去一条枝, 将T分为 两棵树, 它将G的顶点集V划分为V1和V- V1, 在G中这两个顶点集之间的连边, 便对 应这一枝的唯一的基本割集。

§ 设连通图G有e条边, n个顶点, 给定的生成树T 应有n-1条枝, 所以恰有n-1个基本割集, 这些基 本割集的全体称为生成树T基本割集组 § 定义7.7:设连通图G中给定生成树T, 在T中加 一条弦, 恰产生一条回路, 称此回路为关于T的 基本回路 § 由定理 7.1 的等价定义 (4) , 可知在T中加一 弦, 产生唯一的回路 § 设连通图G有e条边, n个顶点, 给定的生成树 应有n-1条枝, e-n+1条弦, 所以恰有e-n+1条基 本回路, 这些基本回路的全体称为生成树T的 基本回路组例如图(a)中给定T={e1,e4,e5,e6}, 关于T的基本割集 组: {e1,e2,e8},{e4,e3,e2,e8},{e5,e3, e2, e7}, {e6,e7} 基本回路组: {e2,e1,e4,e5},{e3, e4, e5},{e7,e5,e6},{e8,e1,e4,}7.3最小生成树§ 定义7.10:设G(V,E,w)是带权连通简单图, w是 从E到实数集的函数又设T是G的一棵生成 树,T中所有枝的权之和称为T的权,记为W(T) 具有权 minTW(T)的生成树称为最小生成 树。

§ 这个问题是具有实际意义的例如G的顶点 表示城市, G的边表示城市间的道路,边的权 表示对应道路的长度, 现在沿着道路架设通讯 线路, 将这些城市联系起来, 要求架设的线路 最短, 这个问题就是求一棵最小生成树的问题§ 克鲁斯科尔算法的步骤, 通俗地说, 就是先将G 中的边按权从小到大顺序排列, 再从小到大依 次取出每一边作检查 § 一开始取权最小的边{v1,v6}为e1,且w(e1)=l,由e1 导出一个部分子图,然后依次每取一边加入已得 部分子图 § 若保持无回路, 将该边与原有部分子图中边导 出一个新的部分子图;若得到回路, 将该边放弃 § 上述过程继续进行, 直到所有边均检查完, 得到 的部分子图就是所求的一棵最小生成树, § 如图(b)所示, 这里e1={v1,v6}和e2={v7,v2}取出后, 取e3为{v2,v3},;若改取e3为{v3,v7},可得到另一棵最小生成树求最小生成树的克鲁斯科尔(Kruskal)算法§ 克鲁斯科尔算法:设G(V,E,w)是有n个顶点的带 权连通简单图 § (1)选取G的一边e1,使w(e1)最小,令E1={e1},1i § (2)若已选Ei={e1,e2,,ei},那么从E-Ei中选取一 边ei+1,满足: § 1)Ei∪{ei+1}的导出子图中不含有回路; 同时 § 2)w(ei+1)为满足1)E-Ei中的最小; § 3)若ei+1存在,则令Ei+1=Ei∪{ei+1},i+1i,转(2); § 若ei+1不存在,则停,此时Ei导出的子图就是所求 的最小生成树,记为T。

§ 定理7.8:克鲁斯科尔算法所得到的图T是 最小生成树 § 证明:首先由定理7.1等价定义(4)(T是无回 路图,且在T的任两个不相邻的顶点之间 添加一边,恰得到一条回路)知T是G的一 棵子树 § 并由等价定义(2)可知边数为n-1(T是无回 路图,且e=n-1)，所以为G的生成树 § 下面证明T是最小生成树即可§ 用反证法证明, 假设T不是G的最小生成树,而S是 G的生成树, 并且 W(S)