离散数学离散第10

1、电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程离离 散散 数数 学学电子科技大学电子科技大学计算机科学与工程学院计算机科学与工程学院示示 范范 性性 软软 件件 学学 院院20222022年年3 3月月2525日星期五日星期五电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82-82-2 22022-3-252022-3-25第第1010章章 树树 树是图论中的一个非常重要的概念，而在计算树是图论中的一个非常重要的概念，而在计算机科学中有着非常广泛的应用，例如现代计算机操机科学中有着非常广泛的应用，例如现代计算机操作系统均采用树形结构来

2、组织文件和文件夹，本章作系统均采用树形结构来组织文件和文件夹，本章介绍树的基本知识和应用。介绍树的基本知识和应用。 在本章中，所谈到的图都假定是简单图；所谈在本章中，所谈到的图都假定是简单图；所谈到的回路均指简单回路或基本回路。并且同一个图到的回路均指简单回路或基本回路。并且同一个图形表示的回路形表示的回路( (简单的或基本的简单的或基本的) )，可能有不同的交，可能有不同的交替序列表示方法，但我们规定它们表示的是同一条替序列表示方法，但我们规定它们表示的是同一条回路。回路。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82-82-3 32022-3-252022

3、-3-2510.0 10.0 内容提要内容提要 1.1. 与树相关的概念：与树相关的概念： 树、森林、根树、根、叶、树、森林、根树、根、叶、分支点、生成树、最小生成树、分支点、生成树、最小生成树、k k元树、元树、k k元完元完全树子树、有序树、祖先与后代、父亲与儿子、全树子树、有序树、祖先与后代、父亲与儿子、最优树等；最优树等；2.2. 树的基本性质：树的基本性质：m = n-1m = n-1等；等；3.3. 树的算法：求生成树与最小生成树的算法、求树的算法：求生成树与最小生成树的算法、求最优树的算法、二元树遍历的算法、根树与二最优树的算法、二元树遍历的算法、根树与二元树相互转化的算法等；元

4、树相互转化的算法等；4.4. 树的应用。树的应用。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82-82-4 42022-3-252022-3-2510.1 10.1 本章学习要求本章学习要求重点掌握重点掌握一般掌握一般掌握了解了解11 1 与树相关基与树相关基本概念本概念2 2 树的性质树的性质3 3 树的基本算树的基本算法法 31 1 树的同构树的同构2 2 树的应用树的应用2树的算法树的算法 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82-82-5 52022-3-252022-3-2510.2 10.2 树树 10.2.

5、1 10.2.1 树的定义与性质树的定义与性质例例10.2.1 200610.2.1 2006年德国世界杯年德国世界杯8 8强的比赛结强的比赛结果图，最后胜利的队捧得大力神杯。果图，最后胜利的队捧得大力神杯。德德 国国阿根廷阿根廷意大利意大利乌克兰乌克兰英格兰英格兰葡萄牙葡萄牙巴巴 西西法法 国国德德 国国意大利意大利葡萄牙葡萄牙法法 国国意大利意大利法法 国国意大利意大利电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82-82-6 62022-3-252022-3-25定义定义10.2.110.2.1n连通而不含回路的无向图称为无向树连通而不含回路的无向图称为无

6、向树(Undirected (Undirected Tree)Tree)，简称树，简称树(Tree)(Tree)，常用，常用T T表示树。表示树。n树中度数为树中度数为1 1的结点称为叶的结点称为叶(Leaf)(Leaf)；度数大于；度数大于1 1的的结点称为分支点结点称为分支点(Branch Point)(Branch Point)或内部结点或内部结点(Interior Point)(Interior Point)。n每个连通分支都是树的无向图称为森林每个连通分支都是树的无向图称为森林(Forest)(Forest)。n平凡图称为平凡树平凡图称为平凡树(Trivial Tree)(Trivi

7、al Tree)。n树中没有环和平行边，因此一定是简单图树中没有环和平行边，因此一定是简单图n在任何非平凡树中，都无度数为在任何非平凡树中，都无度数为0 0的结点。的结点。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82-82-7 72022-3-252022-3-25例例10.2.210.2.2判断下图中的图哪些是树？为什么？判断下图中的图哪些是树？为什么？ (a)(a)(b)(b)(c)(c)(d)(d)分析分析 判断无向图是否是树，根据定义判断无向图是否是树，根据定义10.2.110.2.1，首，首先看它是否连通，然后看它是否有回路。先看它是否连通，然后看

8、它是否有回路。解解 图图(a)(a)、(b)(b)都是连通，并且不含回路，因此是都是连通，并且不含回路，因此是树；图树；图(c)(c)不连通，因此不是树，但由于它不含回不连通，因此不是树，但由于它不含回路，因此是森林；图路，因此是森林；图(d)(d)虽然连通，但存在回路，虽然连通，但存在回路，因此不是树。因此不是树。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82-82-8 82022-3-252022-3-25树的性质树的性质 定理定理10.2.1 10.2.1 设无向图设无向图G = G = ，|V| = n|V| = n，|E| = m|E| = m，下列

9、各命题是等价的：下列各命题是等价的：G G连通而不含回路连通而不含回路( (即即G G是树是树) )；G G中无回路，且中无回路，且m = n-1m = n-1；G G是连通的，且是连通的，且m = n-1m = n-1；G G中无回路，但在中无回路，但在G G中任二结点之间增加一条新边，就中任二结点之间增加一条新边，就得到惟一的一条基本回路；得到惟一的一条基本回路；G G是连通的，但删除是连通的，但删除G G中任一条边后，便不连通；中任一条边后，便不连通；(n2)(n2)G G中每一对结点之间有惟一一条基本通路。中每一对结点之间有惟一一条基本通路。(n2)(n2)电子科技大学离散数学课程组电

10、子科技大学离散数学课程组国家精品课程国家精品课程82-82-9 92022-3-252022-3-25定理定理10.2.1 10.2.1 分析分析 直接证明这直接证明这6 6个命题两两等价工作量太大，一个命题两两等价工作量太大，一般采用循环论证的方法，即证明般采用循环论证的方法，即证明(1) (2) (3) (4) (5) (6) (1)(1) (2) (3) (4) (5) (6) (1)然后利用传递行，得到结论。然后利用传递行，得到结论。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82-82-10102022-3-252022-3-25定理定理10.2.1

11、10.2.1 证明证明 (1) (2) (1) (2)： 对对n n作归纳。作归纳。n = 1n = 1时，时，m = 0m = 0，显然有，显然有m = n-m = n-1 1。假设。假设n = kn = k时命题成立，现证时命题成立，现证n = k+1n = k+1时也成立。时也成立。 由于由于G G连通而无回路，所以连通而无回路，所以G G中至少有一个度数中至少有一个度数为为1 1的结点的结点v0v0，在，在G G中删去中删去v0v0及其关联的边，便得到及其关联的边，便得到k k个结点的连通而无回路的图，由归纳假设知它有个结点的连通而无回路的图，由归纳假设知它有k-1k-1条边。再将结点

12、条边。再将结点v0v0及其关联的边加回得到原图及其关联的边加回得到原图G G，所以所以G G中含有中含有k+1k+1个结点和个结点和k k条边，符合公式条边，符合公式m = n-1m = n-1。 所以，所以，G G中无回路，且中无回路，且m = n-1m = n-1。 G G连通而不含回路连通而不含回路( (即即G G是树是树) ) G G中无回路，且中无回路，且m = n-1m = n-1；电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82-82-11112022-3-252022-3-25(2) (3)(2) (3)： 证明只有一个连通分支。证明只有一个连通

13、分支。 设设G G有有k k个连通分支个连通分支G1G1，G2G2，GkGk，其结点数，其结点数分别为分别为n1n1，n2n2，nknk，边数分别为，边数分别为m1m1，m2m2，mkmk，且，且 ， 。 由于由于G G中无回路，所以每个中无回路，所以每个Gi(i = 1, 2, , Gi(i = 1, 2, , k)k)均为树，因此均为树，因此mi = ni-1(i = 1, 2, , k)mi = ni-1(i = 1, 2, , k)，于是于是 故故k = 1k = 1，所以，所以G G是连通的，且是连通的，且m = n-1m = n-1。 k ki ii=1i=1n =nn =n k

14、ki ii=1i=1m =mm =mkkkkiiiii=1i=1i=1i=1m =m =(n -1)= n-k = n-1m =m =(n -1)= n-k = n-1 G G中无回路，且中无回路，且m = n-1m = n-1； G G是连通的，且是连通的，且m = n-1m = n-1；电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82-82-12122022-3-252022-3-25(3) (4)(3) (4)： 首先证明首先证明G G中无回路。对中无回路。对n n作归纳。作归纳。 n = 1 n = 1时，时，m = n-1 = 0m = n-1 = 0

15、，显然无回路。，显然无回路。 假设结点数假设结点数n = k-1n = k-1时无回路，下面考虑结点时无回路，下面考虑结点数数n = kn = k的情况。因的情况。因G G连通，故连通，故G G中每一个结点的度中每一个结点的度数均大于等于数均大于等于1 1。可以证明至少有一个结点。可以证明至少有一个结点v0v0，使，使得得deg(v0) = 1deg(v0) = 1，因若，因若k k个结点的度数都大于等于个结点的度数都大于等于2 2，则则 ，从而，从而mkmk，即至少有，即至少有k k条边，但这与条边，但这与m = n-1m = n-1矛盾。矛盾。 v vV V2 2m m = =d de e

16、g g( (v v) )2 2k k G G是连通的，且是连通的，且m = n-1m = n-1； G G中无回路，但在中无回路，但在G G中任二结点之间增加一中任二结点之间增加一条新边，就得到惟一的一条基本回路；条新边，就得到惟一的一条基本回路；电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82-82-13132022-3-252022-3-25 在在G G中删去中删去v0v0及其关联的边，得到新图及其关联的边，得到新图GG，根，根据归纳假设知据归纳假设知GG无回路，由于无回路，由于deg(v0) = 1deg(v0) = 1，所以，所以再将结点再将结点v0v0

17、及其关联的边加回得到原图及其关联的边加回得到原图G G，则，则G G也无也无回路。回路。 其次证明在其次证明在G G中任二结点中任二结点vivi，vjvj之间增加一条之间增加一条边边(vi, vj)(vi, vj)，得到一条且仅一条基本回路。，得到一条且仅一条基本回路。 由于由于G G是连通的，从是连通的，从vivi到到vjvj有一条通路有一条通路L L，再在，再在L L中增加一条边中增加一条边(vi, vj)(vi, vj)，就构成一条回路。若此，就构成一条回路。若此回路不是惟一和基本的，则删去此新边，回路不是惟一和基本的，则删去此新边，G G中必有中必有回路，得出矛盾。回路，得出矛盾。电子

18、科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82-82-14142022-3-252022-3-25(4) (5)(4) (5)： 若若G G不连通，则存在两结点不连通，则存在两结点vivi和和vjvj，在，在vivi和和vjvj之间无通路，此时增加边之间无通路，此时增加边(vi, vj)(vi, vj)，不会产生回路，不会产生回路，但这与题设矛盾。但这与题设矛盾。 由于由于G G无回路，所以删去任一边，图便不连通。无回路，所以删去任一边，图便不连通。 G G中无回路，但在中无回路，但在G G中任二结点之间增加一条新中任二结点之间增加一条新边，就得到惟一的一条基本回

19、路；边，就得到惟一的一条基本回路； G G是连通的，但删除是连通的，但删除G G中任一条边后，便不连通；中任一条边后，便不连通；(n2)(n2)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82-82-15152022-3-252022-3-25 G G是连通的，但删除是连通的，但删除G G中任一条边后，便不连通；中任一条边后，便不连通；(n2)(n2) G G中每一对结点之间有惟一一条基本通路。中每一对结点之间有惟一一条基本通路。(n2)(n2)(5) (6)(5) (6)： 由于由于G G是连通的，因此是连通的，因此G G中任二结点之间都有通中任二结点之间都有

20、通路，于是有一条基本通路。若此基本通路不惟一，路，于是有一条基本通路。若此基本通路不惟一，则则G G中含有回路，删去回路上的一条边，中含有回路，删去回路上的一条边，G G仍连通，仍连通，这与题设不符。所以此基本通路是惟一的。这与题设不符。所以此基本通路是惟一的。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82-82-16162022-3-252022-3-25(6) (1)(6) (1)： 显然显然G G是连通的。若是连通的。若G G中含回路，则回路上任二中含回路，则回路上任二结点之间有两条基本通路，这与题设矛盾。因此，结点之间有两条基本通路，这与题设矛盾。因此

21、，G G连通且不含回路。连通且不含回路。 G G中每一对结点之间有惟一一条基本通路。中每一对结点之间有惟一一条基本通路。(n2)(n2) G G连通而不含回路连通而不含回路( (即即G G是树是树) )；电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82-82-17172022-3-252022-3-25树的特点树的特点在结点给定的无向图中，在结点给定的无向图中， 树是边数最多的无回路图树是边数最多的无回路图 树是边数最少的连通图树是边数最少的连通图由此可知，在无向图由此可知，在无向图G = (n, m)G = (n, m)中，中， 若若m mn-1n-1，则，则

22、G G是不连通的是不连通的 若若m mn-1n-1，则，则G G必含回路必含回路由定理由定理10.2.1(4)10.2.1(4)由定理由定理10.2.1(5)10.2.1(5)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82-82-18182022-3-252022-3-25定理定理10.2.210.2.2任意非平凡树任意非平凡树T = (n, m) T = (n, m) 都至少有两片叶。都至少有两片叶。分析分析 利用握手定理和利用握手定理和m = n-1m = n-1即可。即可。证明证明 因树因树T T是连通的，从而是连通的，从而T T中各结点的度数均大中各结

23、点的度数均大于等于于等于1 1。设。设T T中有中有k k个度数为个度数为1 1的结点的结点( (即即k k片叶片叶) )，其余的结点度数均大于等于其余的结点度数均大于等于2 2。 由于树中有由于树中有m = n-1m = n-1，于是，于是2(n-1)2n-k2(n-1)2n-k，因，因此可得此可得k2k2，这说明，这说明T T中至少有两片叶。中至少有两片叶。 v Vv V2m =deg(v)k + 2(n - k) = 2n - k2m =deg(v)k + 2(n - k) = 2n - k于是由握手定理于是由握手定理电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精

24、品课程82-82-19192022-3-252022-3-2510.2.2 10.2.2 生成树生成树 定义定义10.2.2 10.2.2 给定图给定图G = G = ，若，若G G的某个生成的某个生成子图是树，则称之为子图是树，则称之为G G的生成树的生成树(Spanning Tree)(Spanning Tree)，记为记为TGTG。生成树。生成树TGTG中的边称为树枝中的边称为树枝(Branch)(Branch)；G G中中不在不在TGTG中的边称为弦中的边称为弦(Chord)(Chord)；TGTG的所有弦的集合的所有弦的集合称为生成树的补称为生成树的补(Complement)(Com

25、plement)。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82-82-20202022-3-252022-3-25例例10.2.310.2.3判断下图中的图判断下图中的图(b)(b)、(c)(c)、(d)(d)、(e)(e)是否是图是否是图(a)(a)的生成树。的生成树。a ab bc cd de ef f(a)(a)a ab bc cd de ef f(b)(b)a ab bc cd de ef f(c)(c)a ab bc cd de ef f(d)(d)b bc cd de ef f(e)(e)分析分析 判断是否是生成树，根据定义判断是否是生成树，根

26、据定义10.2.210.2.2，首先，首先看它是否是树，然后再看它是否是生成子图。由于看它是否是树，然后再看它是否是生成子图。由于图图(b)(b)和和(d)(d)不是树，图不是树，图(e)(e)不是生成子图，因此它不是生成子图，因此它们都不是图们都不是图(a)(a)的生成树，而图的生成树，而图(c)(c)既是树，又是生既是树，又是生成子图，因此是生成树。成子图，因此是生成树。解解 图图(b)(b)、(d)(d)和和(e)(e)不是图不是图(a)(a)的生成树，图的生成树，图(c)(c)是图是图(a)(a)的生成树，其中边的生成树，其中边(a, c)(a, c)、(a, d)(a, d)、(b,

27、 (b, f)f)、(c, f)(c, f)、(c, e)(c, e)是树枝，而是树枝，而(a, b)(a, b)、(b, c)(b, c)、(c, d)(c, d)、(d, e)(d, e)、(e, f)(e, f)是弦。是弦。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82-82-21212022-3-252022-3-25定理定理10.2.310.2.3一个图一个图G = G = 存在生成树存在生成树TG = TG = 的充的充分必要条件是分必要条件是G G是连通的。是连通的。分析分析 必要性由树的定义即得，充分性利用构造性必要性由树的定义即得，充分性利用

28、构造性方法，具体找出一颗生成树即可方法，具体找出一颗生成树即可证明证明 必要性：假设必要性：假设TG = TG = 是是G = G = 的的生成树，由定义生成树，由定义10.2.110.2.1，TGTG是连通的，于是是连通的，于是G G也是连通也是连通的。的。 充分性：假设充分性：假设G = G = 是连通的。如果是连通的。如果G G中无回中无回路，路，G G本身就是生成树。如果本身就是生成树。如果G G中存在回路中存在回路C1C1，可删除，可删除C1C1中一条边得到图中一条边得到图G1G1，它仍连通且与，它仍连通且与G G有相同的结点集。有相同的结点集。如果如果G1G1中无回路，中无回路，G

29、1G1就是生成树。如果就是生成树。如果G1G1仍存在回路仍存在回路C2C2，可删除，可删除C2C2中一条边，如此继续，直到得到一个无中一条边，如此继续，直到得到一个无回路的连通图回路的连通图H H为止。因此，为止。因此，H H是是G G的生成树。的生成树。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82-82-22222022-3-252022-3-25破圈法与避圈法破圈法与避圈法n 算法算法10.2.1 10.2.1 求连通图求连通图G = G = 的生成树的的生成树的破圈法：破圈法：n每次删除回路中的一条边，其删除的边的总每次删除回路中的一条边，其删除的边的

30、总数为数为m-n+1m-n+1。n 算法算法10.2.2 10.2.2 求连通图求连通图G = G = 的生成树的的生成树的避圈法：避圈法：n每次选取每次选取G G中一条与已选取的边不构成回路中一条与已选取的边不构成回路的边，选取的边的总数为的边，选取的边的总数为n-1n-1。n 由于删除回路上的边和选择不构成任何回路的由于删除回路上的边和选择不构成任何回路的边有多种选法，所以产生的生成树不是惟一的。边有多种选法，所以产生的生成树不是惟一的。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82-82-23232022-3-252022-3-25例例10.2.410

31、.2.4分别用破圈法和避圈法求下图的生成树。分别用破圈法和避圈法求下图的生成树。 1 12 23 34 45 56 6分析分析 分别用破圈法和避圈法依次进行即可。用破圈法时，分别用破圈法和避圈法依次进行即可。用破圈法时，由于由于n = 6n = 6，m = 9m = 9，所以，所以m-n+1 = 4m-n+1 = 4，故要删除的边数为，故要删除的边数为4 4，因此只需因此只需4 4步即可。用避圈法时，由于步即可。用避圈法时，由于n = 6n = 6，所以，所以n-1 = 5n-1 = 5，故要选取故要选取5 5条边，因此需条边，因此需5 5步即可。步即可。 破圈法破圈法电子科技大学离散数学课程

32、组电子科技大学离散数学课程组国家精品课程国家精品课程82-82-24242022-3-252022-3-25避圈法避圈法 由于生成树的形式不惟一，故上述两棵生成树由于生成树的形式不惟一，故上述两棵生成树都是所求的。都是所求的。 破圈法和避圈法的计算量较大，主要是需要找破圈法和避圈法的计算量较大，主要是需要找出回路或验证不存在回路。出回路或验证不存在回路。 1 12 23 34 45 56 61 12 23 34 45 56 6电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82-82-25252022-3-252022-3-25算法算法10.2.310.2.3求连通

33、图求连通图G = G = 的生成树的广度优先搜索算法：的生成树的广度优先搜索算法：（1 1）任选）任选sVsV，将，将v v标记为标记为0 0，令，令L = sL = s，V = V = V-sV-s，k = 0k = 0；（2 2）如果）如果V = V = ，则转，则转(4)(4)，否则令，否则令k = k+1k = k+1；（3 3）依次对）依次对L L中所有标记为中所有标记为k-1k-1的结点的结点v v，如果它与，如果它与V V中的结点中的结点w w相邻接，则将相邻接，则将w w标记为标记为k k，指定，指定v v为为w w的前驱，令的前驱，令L = LwL = Lw，V = V-wV

34、 = V-w，转，转(2)(2)；（4 4）EG = (v, w)|wL-sEG = (v, w)|wL-s，v v为为w w的前驱的前驱 ，结，结束。束。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82-82-26262022-3-252022-3-25例例10.2.510.2.5利用广度优先搜索算法求下图的生成树。利用广度优先搜索算法求下图的生成树。 0(-)0(-)1(a)1(a)1(a)1(a) 2(c)2(c)2(b)2(b)3(e)3(e)3(e)3(e)3(e)3(e)4(d)4(d)4(h)4(h)b ba ac cd dg gj ji if f

35、e eh h0(-)0(-)1(a)1(a)1(a)1(a) 2(c)2(c)2(b)2(b)3(e)3(e)3(f)3(f)3(e)3(e)4(h)4(h)4(h)4(h)b ba ac cd dg gj ji if fe eh h电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82-82-27272022-3-252022-3-2510.2.3 10.2.3 最小生成树最小生成树 定义定义10.2.3 10.2.3 设设G = G = 是连通的赋权图，是连通的赋权图，T T是是G G的一棵生成树，的一棵生成树，T T的每个树枝所赋权值之和称为的每个树枝所赋权值之

36、和称为T T的权的权(Weight)(Weight)，记为，记为w(T)w(T)。G G中具有最小权的生成中具有最小权的生成树称为树称为G G的最小生成树的最小生成树(Minimal Spanning Tree)(Minimal Spanning Tree)。 一个无向图的生成树不是惟一的，同样地，一个无向图的生成树不是惟一的，同样地，一个赋权图的最小生成树也不一定是惟一的。一个赋权图的最小生成树也不一定是惟一的。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82-82-28282022-3-252022-3-25算法算法10.2.3 Kruskal10.2.3

37、Kruskal算法算法 （1 1）在）在G G中选取最小权边中选取最小权边e1e1，置，置i = 1i = 1。（2 2）当）当i = n-1i = n-1时，结束，否则转时，结束，否则转(3)(3)。（3 3）设已选取的边为）设已选取的边为e1, e2, , eie1, e2, , ei，在，在G G中选取中选取不同于不同于e1, e2, , eie1, e2, , ei的边的边ei+1ei+1，使，使e1, e2, , e1, e2, , ei, ei+1ei, ei+1中无回路且中无回路且ei+1ei+1是满足此条件的最小权是满足此条件的最小权边。边。（4 4）置）置i = i+1i =

38、 i+1，转，转(2)(2)。要点：在与已选取的边不构成回路的边中要点：在与已选取的边不构成回路的边中选取最小者。选取最小者。 在在KruskalKruskal算法的步骤算法的步骤1 1和和3 3中，若满足条件中，若满足条件的最小权边不止一条，则可从中任选一条，这样的最小权边不止一条，则可从中任选一条，这样就会产生不同的最小生成树。就会产生不同的最小生成树。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82-82-29292022-3-252022-3-25例例10.2.610.2.6用用KruskalKruskal算法求图中赋权图的最小生成树。算法求图中赋权图的

39、最小生成树。4 46 65 55 57 76 61 1f f9 92 23 3a ad db bc ci im mj jk ke eh hg g3 34 43 34 44 46 65 58 87 75 58 82 23 34 45 5k k1 1f fe ec ch h3 34 4a a3 3i i5 5d dm m2 2g g2 2b bj j4 4解解 n=12 n=12，按算法要执行，按算法要执行n-1=11n-1=11次，次，w(T) = 36w(T) = 36。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82-82-30302022-3-252022

40、-3-25算法算法10.2.5 Prim10.2.5 Prim算法算法 （1 1）在）在G G中任意选取一个结点中任意选取一个结点v1v1，置，置VT = v1, VT = v1, ET = ET = ，k = 1k = 1；（2 2）在）在V-VTV-VT中选取与某个中选取与某个viVTviVT邻接的结点邻接的结点vjvj，使得边使得边(vi, vj)(vi, vj)的权最小，置的权最小，置VT = VTvj, ET VT = VTvj, ET = ET(vi, vj)= ET(vi, vj)，k = k+1k = k+1；（3 3）重复步骤）重复步骤2 2，直到，直到k = |V|k =

41、|V|。要点：从任意结点开始，每次增加一条最小权边要点：从任意结点开始，每次增加一条最小权边构成一棵新树。构成一棵新树。 在在PrimPrim算法的步骤算法的步骤2 2中，若满足条件的最小中，若满足条件的最小权边不止一条，则可从中任选一条，这样就会产权边不止一条，则可从中任选一条，这样就会产生不同的最小生成树。生不同的最小生成树。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82-82-31312022-3-252022-3-25例例10.2.710.2.7用用PrimPrim算法求图中赋权图的最小生成树。算法求图中赋权图的最小生成树。 5 5f f10102

42、2d db bc ce e7 7g g6 64 45 58 82 2a a7 7g ge e2 2f f5 5b b4 42 2c ca ad d5 5解解 n = 7 n = 7，按算法要执行，按算法要执行n-1 = 6n-1 = 6次，次，w(T) = 25w(T) = 25。 由由PrimPrim算法可以看出，每一步得到的图一定算法可以看出，每一步得到的图一定是树，故不需要验证是否有回路，因此它的计算是树，故不需要验证是否有回路，因此它的计算工作量较工作量较KruskalKruskal算法要小。算法要小。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82-

43、82-32322022-3-252022-3-2510.2.4 10.2.4 无向树的难点无向树的难点 1.1. 树是不含回路的连通图。注意把握树的性质，树是不含回路的连通图。注意把握树的性质，特别是树中叶结点的数目及边数与结点数的关特别是树中叶结点的数目及边数与结点数的关系：系：m = n-1m = n-1；2.2. 生成树是无向连通图是树的生成子图。注意把生成树是无向连通图是树的生成子图。注意把握所有连通图都有生成树，知道生成树的树枝握所有连通图都有生成树，知道生成树的树枝与弦及其数目，会使用避圈法、破圈法和广度与弦及其数目，会使用避圈法、破圈法和广度优先搜索算法求生成树；优先搜索算法求生

44、成树；3.3. 最小生成树是赋权连通图的权值之和最小的生最小生成树是赋权连通图的权值之和最小的生成树。会使用成树。会使用KruskalKruskal算法和算法和PrimPrim算法求最小生算法求最小生成树。成树。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82-82-33332022-3-252022-3-2510.2.5 10.2.5 无向树的应用无向树的应用 例例10.2.8 10.2.8 假设有假设有5 5个信息个信息中心中心A A、B B、C C、D D、E E，它们之间，它们之间的距离的距离( (以百公里为单位以百公里为单位) )如图所如图所示。要交

45、换数据，我们可以在任示。要交换数据，我们可以在任意两个信息中心之间通过光纤连接，但是费用的限意两个信息中心之间通过光纤连接，但是费用的限制要求铺设尽可能少的光纤线路。重要的是每个信制要求铺设尽可能少的光纤线路。重要的是每个信息中心能和其它中心通信，但并不需要在任意两个息中心能和其它中心通信，但并不需要在任意两个中心之间都铺设线路，可以通过其它中心转发。中心之间都铺设线路，可以通过其它中心转发。 A AB BC CD DE E3 35 54 47 79 96 62 28 87 79 9A AB BC CD DE E3 34 46 62 2分析分析 这实际上就是求赋权连通图的最小生成树问这实际上就

46、是求赋权连通图的最小生成树问题，可用题，可用PrimPrim算法或算法或KruskalKruskal算法求解。算法求解。解解 求得图的最小生成树如图所示，求得图的最小生成树如图所示，w(T) = 15w(T) = 15百百公里。即按图的图铺设，使得铺设的线路最短。公里。即按图的图铺设，使得铺设的线路最短。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82-82-34342022-3-252022-3-2510.3 10.3 根树根树 10.3.1 10.3.1 根树的定义与分类根树的定义与分类 定义定义10.3.1 10.3.1 一个有向图，若略去所有有向一个有

47、向图，若略去所有有向边的方向所得到的无向图是一棵树，则这个边的方向所得到的无向图是一棵树，则这个有向图称为有向树有向图称为有向树(Directed Tree)(Directed Tree)。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82-82-35352022-3-252022-3-25例例10.3.110.3.1判断下图中的图哪些是树？为什么？判断下图中的图哪些是树？为什么？(a)(a)(c)(c)(e)(e)(d)(d)(b)(b)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82-82-36362022-3-252022-

48、3-25定义定义10.3.210.3.2一棵非平凡的有向树，如果恰有一个结点的入度为一棵非平凡的有向树，如果恰有一个结点的入度为0 0，其余所有结点的入度均为，其余所有结点的入度均为1 1，则称之为根树，则称之为根树(Root Tree)(Root Tree)或外向树或外向树(Outward Tree)(Outward Tree)。入度为。入度为0 0的结点称为根的结点称为根(Root)(Root)；出度为；出度为0 0的结点称为叶的结点称为叶(Leaf)(Leaf)；入度为；入度为1 1，出度大于，出度大于0 0的结点称为内点的结点称为内点(Interior Point)(Interior

49、Point)；又将内点和根统称为分支点；又将内点和根统称为分支点(Branch Point)(Branch Point)。在根树中，从根到任一结点。在根树中，从根到任一结点v v的的通路长度，称为该结点的层数通路长度，称为该结点的层数(Layer Number)(Layer Number)；称；称层数相同的结点在同一层上；所有结点的层数中最层数相同的结点在同一层上；所有结点的层数中最大的称为根树的高大的称为根树的高(Height)(Height)。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82-82-37372022-3-252022-3-25例例10.3.

50、210.3.2判断下图所示的图是否是根树？若是根树，给出其判断下图所示的图是否是根树？若是根树，给出其根、叶和内点，计算所有结点所在的层数和高。根、叶和内点，计算所有结点所在的层数和高。v1v1v2v2v3v3v4v4v5v5v6v6 v7v7v8v8v9v9v1v10 0v1v11 1v1v12 2v1v13 3v1v1v2v2v3v3v4v4v5v5v6v6 v7v7v8v8v9v9v1v10 0v1v11 1v1v12 2v1v13 3解解 是一棵根树，其中是一棵根树，其中v1v1为根，为根，v5,v6,v8,v9,v10,v12,v13v5,v6,v8,v9,v10,v12,v13为叶

51、，为叶，v2,v3,v4,v7,v11v2,v3,v4,v7,v11为内点。为内点。v 1v 1 处 在 第 零 层 ， 层 数 为处 在 第 零 层 ， 层 数 为 0 0 ；v2,v3,v4v2,v3,v4同处在第一层，层数为同处在第一层，层数为1 1；v5,v6,v7,v8,v9v5,v6,v7,v8,v9同处在第二层，同处在第二层，层数为层数为2 2；v10,v11,v12v10,v11,v12同处在第同处在第三层，层数为三层，层数为3 3；v13v13处在第四层，处在第四层，层数为层数为4 4；这棵树的高为；这棵树的高为4 4。倒置法倒置法 电子科技大学离散数学课程组电子科技大学离散

52、数学课程组国家精品课程国家精品课程82-82-38382022-3-252022-3-25家族关系家族关系 定义定义10.3.3 10.3.3 在根树中，若从结点在根树中，若从结点vivi到到vjvj可达，则可达，则称称vivi是是vjvj的祖先的祖先(Ancestor)(Ancestor)，vjvj是是vivi的后代的后代(Descendant)(Descendant)；又若；又若是根树中的有向边，是根树中的有向边，则称则称vivi是是vjvj的父亲的父亲(Father)(Father)，vjvj是是vivi的儿子的儿子(Son)(Son)；如果两个结点是同一个结点的儿子，则称这两个结如果两

53、个结点是同一个结点的儿子，则称这两个结点是兄弟点是兄弟(Brother)(Brother)。定义定义10.3.4 10.3.4 如果在根树中规定了每一层上结点的如果在根树中规定了每一层上结点的次序，这样的根树称为有序树次序，这样的根树称为有序树(Ordered Tree)(Ordered Tree)。 一般地，在有序树中同一层中结点的次序为从一般地，在有序树中同一层中结点的次序为从左至右。有时也可以用边的次序来代替结点的次序。左至右。有时也可以用边的次序来代替结点的次序。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82-82-39392022-3-252022

54、-3-25定义定义10.3.510.3.5在根树在根树T T中，中，若每个分支点至多有若每个分支点至多有k k个儿子，则称个儿子，则称T T为为k k元树元树(k-(k-ary Tree)ary Tree)；若每个分支点都恰有若每个分支点都恰有k k个儿子，则称个儿子，则称T T为为k k元完全树元完全树(k-ary Complete Tree)(k-ary Complete Tree)；若若k k元树元树T T是有序的，则称是有序的，则称T T为为k k元有序树元有序树(k-ary (k-ary Ordered Tree)Ordered Tree)；若若k k元完全树元完全树T T是有序的，

55、则称是有序的，则称T T为为k k元有序完全树元有序完全树(k-ary Ordered Complete Tree)(k-ary Ordered Complete Tree)。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82-82-40402022-3-252022-3-25子树子树 在根树在根树T T中，任一结点中，任一结点v v及其所有后代导出的子及其所有后代导出的子图图TT称为称为T T的以的以v v为根的子树为根的子树(Subtree)(Subtree)。 当然，当然，TT也可以有自己的子树。也可以有自己的子树。 二元有序树的每个结点二元有序树的每个结点

56、v v至多有两个儿子，分至多有两个儿子，分别称为别称为v v的左儿子的左儿子(Left Son)(Left Son)和右儿子和右儿子(Right (Right Son)Son)。 二元有序树的每个结点二元有序树的每个结点v v至多有两棵子树，分至多有两棵子树，分别称为别称为v v的左子树的左子树(Left Subtree)(Left Subtree)和右子树和右子树(Right (Right Subtree)Subtree)。 注意区分以注意区分以v v为根的子树和为根的子树和v v的左的左( (右右) )子树，子树，v v为根的子树包含为根的子树包含v v，而，而v v的左的左( (右右)

57、)子树不包子树不包含含v v。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82-82-41412022-3-252022-3-25例例10.3.310.3.3判断下图所示的几棵根树是什么树？判断下图所示的几棵根树是什么树？(b)(b)(c)(c)(a)(a)2 2元元完全树完全树 3 3元树元树 3 3元元完全树完全树 3 3元有序元有序完全树完全树1 12 22 2(d)(d)1 13 33 32 21 13 3电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82-82-42422022-3-252022-3-25k k元完全树中

58、分支点与叶结点数目之间的关系元完全树中分支点与叶结点数目之间的关系 定理定理10.3.1 10.3.1 在在k k元完全树中，若叶数为元完全树中，若叶数为t t，分支点，分支点数为数为i i，则下式成立：，则下式成立：(k-1)(k-1)i = t-1i = t-1证明证明 由假设知，该树有由假设知，该树有i+ti+t个结点。由定理个结点。由定理10.2.110.2.1知，该树的边数为知，该树的边数为i+t-1i+t-1。由握手定理知，。由握手定理知，所有结点的出度之和等于边数。而根据所有结点的出度之和等于边数。而根据k k元完全树元完全树的定义知，所有分支点的出度为的定义知，所有分支点的出度

59、为k ki i。因此有。因此有k ki = i+t-1i = i+t-1即即 (k-1) (k-1)i = t-1i = t-1电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82-82-43432022-3-252022-3-25例例10.3.410.3.4假设有一台计算机，它有一条加法指令，可计算假设有一台计算机，它有一条加法指令，可计算3 3个数的和。如果要求个数的和。如果要求9 9个数个数x1, x2, x3, x4, x5, x1, x2, x3, x4, x5, x6, x7, x8, x9x6, x7, x8, x9之和，问至少要执行几次加法指令？之和

60、，问至少要执行几次加法指令？解解 用用3 3个结点表示个结点表示3 3个数，将表示个数，将表示3 3个数之和的结个数之和的结点作为它们的父结点。这样本问题可理解为求一个点作为它们的父结点。这样本问题可理解为求一个三元完全树的分支点问题。把三元完全树的分支点问题。把9 9个数看成叶。由定个数看成叶。由定理理10.910.9知，有知，有(3-1)i = 9-1(3-1)i = 9-1，得，得i = 4i = 4。所以至少。所以至少要执行要执行4 4次加法指令。次加法指令。 (a)(a)x1x1 x2x2 x3x3x4x43 3x5x5 x6x6x7x7 x8x8 x9x9x1x1 x2x2x3x3