图论课件---04-2015

1、第九章树树是图论中的一个非常重要的概念，而 在计算机科学中有着非常广泛的应用，例如 现代计算机操作系统均采用树形结构来组织 文件和文件夹，本章介绍树的基本知识和应 用。定义1§9.1 树无向树：连通而不含回路的无向图称为无向树，简称树，常用T表示树。叶：树中度数为1的结点； 分支点或内部结点：度数大于1的结点；森林：每个连通分支都是树的无向图。注：树中没有环和平行边，因此一定是简单图例1判断下图中的图哪些是树？为什么？(a)(b)(c)(d) 分析判断无向图是否是树，根据定义1，首先看它 是否连通，然后看它是否有回路。定理1 设无向图G = <V,E>，|V| = n，|

2、E| = m，下列各命题是等价的： G连通而不含回路(即G是树)； G中无回路，且m=n-1； G是连通的，且m=n-1； G中无回路，但在G中任二结点之间增加一条 新边，就得到惟一的一条基本回路； G是连通的，但删除G中任一条边后，便不连 通；(n2) G中每对结点间有惟一一条基本通路。(n2)例2：无向树G有5片树叶，3个2度分支点，其余分支点均为3度，问G有多少个结点？解：由握手定理2m=d(vi) 及定理1n= m+1 设G有n个顶点,则有下列关系式5 ×1+3 ×2+(n-5-3) ×3=2 ×(n-1)解得：n=11例3：无向树G有2个2度结

3、点，1个3度结点，3个4度结点，则其1度结点数为多少？解：由握手定理2m=d(vi)及定理1n=m+1设G有t个1顶点, 则有下列关系式2×2+3+4×3+t =2m=2×(n-1)=2×(2+1+3+t-1)解得：t = 9定理2任意非平凡树T = (n, m) 都至少有两片叶。分证析明利因用树握T手是定连理通和的m，=从n而-1T即中可各。结点的度数均大于等于1。设T中有k个度数为1的结点(即k片叶)， 其余的结点度数均大于等于2。于是由握手定理2m=åvVdeg(v) k + 2(n - k) = 2n - k由于树中有m=n-1，于是2

4、(n-1)2n-k，因此可得k2，这说明T中至少有两片叶。§9.2 有向树定义1 一个有向图，若略去所有有向边的方 向所得到的无向图是一棵树，则这个有向图 称为有向树。例1判断下图中的图哪些是树？为什么？(a)(b)(c)(d)(e)外向树的定义与分类定义2外向树:一棵非平凡的有向树，如果恰有一个结点 的入度为0，其余所有结点的入度均为1。根:入度为0的结点； 叶:出度为0的结点；分支点:非根非叶结点称为分支点。 层数：从根到任一结点v的通路长度，称为该结点的层数；高：所有结点中的最大层数。例2判断下图所示的图是否是外向树？若是外向树，给出其根、叶和分支点，计算所有结点所在的层数和

5、高。解是 一 棵 外 向 树 ， 其 中 v1 为v1根，v ,v,v ,v ,v,v,v为叶，5689101213v2v3v4v5v6v7v8v9 v10v11v12v2,v3,v4,v7,v11 为 内点 。 v1 处在第零层，层数为0； v2,v3,v4 同处在第 一 层 ， 层 数 为 1 ； v5,v6,v7,v8,v9 同处在第二层，层数为2；v10,v11,v12同处在第三层，层数为3；处在第四层，层数为4；这棵树v13v13的高为4。家族关系定义3 在外向树中，若从 结点vi 到 vj 可达，则 称vi是vj的祖先，vj是vi 的后代；又若<vi, vj>是 根树中

6、的有向边，则称v1v2v3v4v5v6v7v8v9vi是vj的父亲，vj是vi的儿子；如果两个结点是同一个结点的儿子，则 称这两个结点是兄弟。v10v11v13v12内向树:一棵非平凡的有向树，如果恰有一个结点的出度为0，其余所有结点的出度均为1。根:出度为0的结点；叶:入度为0的结点；分支点:非根非叶结点称为分支点。层数：从根到任一结点v的通路长度，称为该结点的层数；高：所有结点中的最大层数。v1v2v3v4v5v6v7v8v9 v10v11v12v13定义4在外向树T中， m元树：若每个结点的出度不超过正数m； m元完全树：若每个结点（不含叶）的出度都等于正数m 。例3判断下图所示的几棵外

7、向树是什么树？(a)(b)(c)2元 完全树3元树3元完全树二元树比较重要，许多实际问题都可用二元树表示生成树§9.3生成树定义1 给定图G = <V, E>，若G的某个生成子图是树，则称之为G的生成树，记为TG。 生成树TG中的边称为树枝；G中不在TG中的 边称为弦；TG的所有弦的集合称为生成树的 补。例1判断下图中的图(b)、(c)、(d)、(e)是否是图(a)的生成树。afeafeafeafefebcd (a)bcd (b)bcd (c)bcd (d)bcd (e)(b)解分析图判(b断)、是(d否)和是(生e)不成是树图，(根a)据的定生义成1树，首图先(看c)是

8、它图是 否是树，然后再看它是否是生成子图。由于图(a)的生成树，其中边(a,c)、(a,d)、(b,f)、(c,f)、和(d)不是树，图(e)不是生成子图，因此它们都不 (c, e)是树枝，而(a, b)、(b, c)、(c, d)、(d, e)、(e, f) 是 图 (a) 的 生 成 树 ， 而 图 (c) 既 是 树 ， 又 是 生 成 子是图弦，。因此是生成树。破圈法与避圈法算法1求连通图G = <V, E>的生成树的破圈法： 每次删除回路中的一条边，其删除的边的总数 为m-n+1。算法2求连通图G = <V, E>的生成树的避圈法： 每次选取G中一条与已选取的

9、边不构成回路的 边，选取的边的总数为n-1。由于删除回路上的边和选择不构成任何回路的边有 多种选法，所以产生的生成树不是惟一的。例2分别用破圈法和避圈法求下图的生成树。1破圈法26534分析 分别用破圈法和避圈法依次进行即可。用破圈法时， 由于n = 6，m = 9，所以m-n+1 = 4，故要删除的边数为4， 因此只需4步即可。用避圈法时，由于n = 6，所以n-1 = 5， 故要选取5条边，因此需5步即可。避圈法112652653434Ø由于生成树的形式不惟一，故上述两棵生成树都是所求的。Ø破圈法和避圈法的计算量较大，主要是需要找 出回路或验证不存在回路。思考：现要铺设

10、一个连接各个城市的输油管道，边上的 权代表费用，问如铺设才能使总费用最小？27123518732443466上图即为最小生成树问题最小生成树定义3 设G = <V, E>是连通的带权图，T是G的一 棵 生 成树 ， T的 每个 树 枝所赋权值之和称为 T的 权，记为w(T)。G中具有最小权的生成树称为G的 最小生成树。一个无向图的生成树不是惟一的，同样地， 一个带权图的最小生成树也不一定是惟一的。算法3Kruskal算法(避圈法)（1）在G中选取最小权边e1，置i=1。（2）当i=n-1时，结束，否则转(3)。（3）设已选取的边为e1, e2, , ei，在G中选取不同 于e1,

11、e2, , ei的边ei+1，使e1, e2, , ei, ei+1中无回 路且ei+1是满足此条件的最小权边。要点：在与已选取的边不构成回路的边中 选取最小者。（4）置i=i+1，转(2)。在Kruskal算法的步骤1和3中，若满足条件 的最小权边不止一条，则可从中任选一条，这样 就会产生不同的最小生成树。例3用Kruskal算法求图的最小生成树。a5b4c3dab4c3d43234e1gh54233e1fgf792h278545468i6j5k6mij5km解 n=12，按算法要执行n-1=11次， w(T)=36。例4用避圈法求下图所示的最小生成树解: W(T)=1+2+3+4+5=15a551b5f5e注意：最小生成树的结点数与原图相等，边的数3642目比原图少。cd6例5：铺设一