第8章+图论-8(树)--离散数学-图论课件.ppt

1返回 结束第八章 图论-28.1 Euler图与图与Hamilton图图8.2 树树8.2.1 树的概念和基本性质8.2.2 几类常用树根树 最优二叉树8.2.3 8.3 2返回 结束8.2 树树 树的术语起源于植物学和家谱学。早在1857年，英国数学Arthur Cayley(18211895)就发现了树，当时他正在试图列举形为CnH2n+2的化合物的同分异构体。树具有广泛的应用，特别在计算机科学与管理科学中。如用树构造存储和传输数据的有效编码，用树构造最便宜的电话线连接分布式计算机网络，用树模拟一系列决策完成的过程等。3返回 结束8.2.1 树的概念和基本性质树的概念和基本性质v在图论中：1、连通的无环图称为树树。2、除根之外，度1的顶点称为叶子叶子，度1的顶点称为分支分支点点或者内点内点。叶子叶子分支点分支点根根4返回 结束8.2.1 树的概念和基本性质树的概念和基本性质3、多个树称为森林森林；4、孤立顶点叫做平凡树平凡树。123456789101512131114平凡树平凡树5返回 结束6返回 结束1根树根树8.2.2 几类常用树几类常用树有向树有向树 一个弱连通有向图，若去掉方向后得到一一个弱连通有向图，若去掉方向后得到一棵树，则称此有向图为一棵有向树，记为棵树，则称此有向图为一棵有向树，记为T。根树根树 一棵有向树一棵有向树T，若其中有且仅有一个结点，若其中有且仅有一个结点v0的入度为的入度为0，其余结点的入度为，其余结点的入度为1，则称，则称T是一棵以是一棵以v0为根的根树或为根的根树或外向树外向树。其中出度为。其中出度为0的结点称为的结点称为有根树的叶子。有根树的叶子。把外向树之定向反过来，得到的有向树叫内向树内向树。v0v07返回 结束8.2.2 几类常用树几类常用树v根树通常画成倒长的；v一个 结点的子结点画在它的v下一层，边的方向省略；v“同辈兄弟”画在同一层。8返回 结束8.2.2 几类常用树几类常用树树的高度树的高度 设有根树设有根树 T=(V,A)，v0为树根。为树根。u V的深度是从的深度是从v0 开始到达开始到达u的有向路的长度，的有向路的长度，T的高度是从的高度是从v0到到T的叶子的最长路的长度。的叶子的最长路的长度。根结点深度为根结点深度为0，称为第，称为第0层；层；深度同为深度同为i 的结点构成树的第的结点构成树的第i 层；层；具有最大深度的结点的深度称为树的深度具有最大深度的结点的深度称为树的深度（高度）。（高度）。9返回 结束10返回 结束8.2.2 几类常用树几类常用树2有序树有序树定义定义 对有向树对有向树 T=(V,A)，若，若 u,v V且且 A，则称，则称 u为为v的父亲，的父亲，v为为u的儿子。若从的儿子。若从u到到v存在有向道路，存在有向道路，则称则称u是是v的祖先，的祖先，v是是u的后代（子孙）的后代（子孙）有序树有序树 将各树的每个结点的所有儿子按次序排列，将各树的每个结点的所有儿子按次序排列，称这样的根树为有序树。称这样的根树为有序树。有序树的每个结点的出度小于或等于有序树的每个结点的出度小于或等于m时，称为时，称为m叉叉有序树。有序树。有序树的每个结点的出度只为有序树的每个结点的出度只为 0或或 m 时，称为时，称为m叉叉正则有序树。正则有序树。11返回 结束8.2.2 几类常用树几类常用树v例 设有4个银币，已知其中3个一定是真的，真假的区别在于银币的重量，现用一天平设法找出假币。解：用a、b、c、d分别表示银币，a:b表示在天平上作比较。a:ba:cc重c轻a:dd重全真d轻a:ca轻b重a:cb轻a重12返回 结束13返回 结束8.2.2 几类常用树几类常用树三三、最优二叉树最优二叉树二叉树二叉树 除树叶外，每个结点的最多有两个子结点，分别称为除树叶外，每个结点的最多有两个子结点，分别称为左子结点和右子结点的根树称为二叉树左子结点和右子结点的根树称为二叉树二叉树的另外一个定义：二叉树或者是空树，或者有一个二叉树的另外一个定义：二叉树或者是空树，或者有一个根结点和两个分别称为左右子树的二叉树构成。根结点和两个分别称为左右子树的二叉树构成。二叉树的性质二叉树的性质1)第第i 层的结点数最多为层的结点数最多为2i；2)深度为深度为k的二叉树最多有的二叉树最多有2k+1-1个结点；个结点；3)记二叉树出度为记二叉树出度为2的结点数目为的结点数目为n2，叶子数目为，叶子数目为n0，则有：，则有：n0=n2+14)多元树与二叉树的对应关系：以结点的最左儿子为对应二叉树中多元树与二叉树的对应关系：以结点的最左儿子为对应二叉树中该结点的左儿子；以结点的右兄弟为对应二叉树中该结点的右儿该结点的左儿子；以结点的右兄弟为对应二叉树中该结点的右儿子。子。14返回 结束15返回 结束8.2.2 几类常用树几类常用树高度为高度为k的完全二叉树，其的完全二叉树，其k-1层以上结点构成一棵高度层以上结点构成一棵高度为为k-1 的完美二叉树。的完美二叉树。完全二叉树的叶结点或者在同一层或者完全二叉树的叶结点或者在同一层或者 在相邻的两层。在相邻的两层。满二叉树完美二叉树完全二叉树16返回 结束8.2.2 几类常用树几类常用树三三、最优二叉树最优二叉树定义定义设设T是有是有t片叶子的二叉树，其中片叶子的二叉树，其中t片叶子分别带有片叶子分别带有非负实权非负实权 ，则称，则称T为为加权二叉树加权二叉树。称。称W(T)为二叉树为二叉树T的权，其中的权，其中hi为带权为带权wi的树的树叶叶vi的层数。在所有的带权的层数。在所有的带权 的二叉树的二叉树中，带权最小的二叉树称为中，带权最小的二叉树称为最优二叉树最优二叉树(哈夫曼树哈夫曼树)17返回 结束18返回 结束8.2.2 几类常用树几类常用树vHuffmanHuffman树树Huffman 算法算法 给定给定t个非负实数，构造以它们为叶子带权且具有最小个非负实数，构造以它们为叶子带权且具有最小M(T)的最优二叉树。的最优二叉树。(1)i t；(2)若若 i=1 结束；结束；(3)将将 i 个非负实数权由小到大排列成序，以最小的两个个非负实数权由小到大排列成序，以最小的两个数作为左右儿子，构造其父亲结点，并以此左右儿子数作为左右儿子，构造其父亲结点，并以此左右儿子的权值之和作为新构造的父亲结点的权值。在权序列的权值之和作为新构造的父亲结点的权值。在权序列中删去此左右儿子对应的权值，增加新构造的父亲结中删去此左右儿子对应的权值，增加新构造的父亲结点的权值。点的权值。(4)i i-1，转转(2)。19返回 结束8.2.2 几类常用树几类常用树v例：有例：有4个权值个权值7,5,2,4，试构造一棵有，试构造一棵有4个个叶子结点的哈夫曼树。叶子结点的哈夫曼树。20返回 结束8.2.2 几类常用树几类常用树Huffman树树 由由Huffman算法构造的二叉树称算法构造的二叉树称为相对于非负实数权为相对于非负实数权 wi(i=1,2,t)的的Huffman树。树。定理定理 Huffman树是一棵相对于非负实数权树是一棵相对于非负实数权 wi(i=1,2,t)的最优二叉树。的最优二叉树。21返回 结束8.2.2 几类常用树几类常用树定义定义：有一个序列的集合，如果在这个集合中。任何序列都不是另一个序列的前缀，则称这个集合为前缀码前缀码。v例如，001是001011的前缀，集合000,001,01,10,11是前缀码，而1,00,01,000,0001不是前缀码。二元前缀码二元前缀码前缀码前缀码A=1,2,m 中的中的 i 只由两种符号（如只由两种符号（如0、1）组成时，称）组成时，称A为一个为一个二元二元前缀码。前缀码。22返回 结束8.2.2 几类常用树几类常用树v对有序二叉树的顶点编码如下：(1)根不标码；(2)兄弟有序，左为兄，标0，右为弟，标1；(3)从根始到叶上的道路依次抄出各点之码，写在叶下方，称该叶的前缀该叶的前缀；(4)全树的叶从左到有把它们的前缀依次抄出，叫做该树的前缀码该树的前缀码，每个叶子的前缀后加逗号，最后一个叶子前缀后加句号。显然有序二叉树与前缀码一一对应。23返回 结束24返回 结束8.2.2 几类常用树几类常用树Huffman编码编码 以各个源码符号在源码电文中以各个源码符号在源码电文中出现的频率为权值，构造以源码符号为叶子出现的频率为权值，构造以源码符号为叶子的的Huffman树，得到关于源码符号集的一个树，得到关于源码符号集的一个二叉前缀码，称为其二叉前缀码，称为其Huffman编码。编码。定理定理 Huffman编码是关于该源码符号集的最编码是关于该源码符号集的最短二叉前缀码。短二叉前缀码。证明证明 略略25返回 结束8.2.2 几类常用树几类常用树实现译文长度最短的二叉前缀码设计过程：实现译文长度最短的二叉前缀码设计过程：1.字频统计字频统计2.等概率假设等概率假设3.Huffman树构造树构造4.Huffman编码方案确定编码方案确定例例 设一段电文含有设一段电文含有x1,x2,x3,x4,x5,x6,x7共共7个符号，个符号，它们出现的频率分别是：它们出现的频率分别是：x1:35%x2:20%x3:15%x4:10 x5:10%x6:5%x7:5%。试为这。试为这7个符个符号设计一套最短二叉前缀编码方案。号设计一套最短二叉前缀编码方案。26返回 结束8.2.2 几类常用树几类常用树例例27返回 结束28返回 结束8.2.3 生成树生成树生成树生成树如果一棵树T是图G的子图，则树T称为图G的生成树生成树或支撑树支撑树；GE(T)称为树T的余树余树，记作：T；T中的边称为图G的弦弦，也是树T的弦。1234567812345678余树余树弦弦29返回 结束8.2.3 生成树生成树定理定理 任何连通图至少有一棵生成树。任何连通图至少有一棵生成树。证明略证明略定理定理 若连通图G=(V,E)，n=|V|，则图的生成生成树树有n1条边。用归纳法易证明。30返回 结束31返回 结束8.3.1 平面图的定义平面图的定义 可平面性可平面性 一个图一个图 G=(V,E)，若能将其画在平面上，若能将其画在平面上，且任意两条边的交点只能是且任意两条边的交点只能是G的顶点，则称的顶点，则称G可嵌入可嵌入平面，或称平面，或称G是可平面的。可平面图在平面上的一个是可平面的。可平面图在平面上的一个嵌入称为一个平面图。嵌入称为一个平面图。树是一类重要的平面图。树是一类重要的平面图。应用举例：印刷电路版、集成电路设计。应用举例：印刷电路版、集成电路设计。(a)(b)(c)(a)是可平面图，(b),(c)是(a)的平面嵌入，是平面图。32返回 结束8.3.1 平面图的定义平面图的定义 例例 K5 和和K3,3 是不可平面的。是不可平面的。K5K3,3K5K3,333返回 结束8.3.1 平面图的定义平面图的定义 区域区域 由平面图的边包围而成，其中不含图的由平面图的边包围而成，其中不含图的顶点。也称为顶点。也称为面面。包围域。包围域R的所有边组成的回的所有边组成的回路称为该域的边界，回路长度称为该域的度，路称为该域的边界，回路长度称为该域的度，记为记为deg(R)。v2R1R2R0v1v3v4v5v6v7各域的边界：各域的边界：R0:v1 v2 v4 v5 v7 v7 v4 v3 v1R1:v1 v2 v4 v3 v1R2:v4 v5 v7 v4 v6 v4R3:v7 v7 例例deg(R0)=8,deg(R1)=4,deg(R2)=5,deg(R3)=1R334返回 结束8.3.1 平面图的定义平面图的定义 内部面和外部面内部面和外部面 由平面图的边包围且无穷大的域称为由平面图的边包围且无穷大的域称为外部面。（如上例的域外部面。（如上例的域R0为外部面）为外部面）一个平面图有且只有一个外部面。一个平面图有且只有一个外部面。曲面嵌入曲面嵌入 一个图可嵌入平面当且仅当它可嵌入曲一个图可嵌入平面当且仅当它可嵌入曲面。面。定理定理5-1-1 平面图平面图G的所有域的度之和等于其边的所有域的度之和等于其边数数m的的2倍，即：倍，即：35返回 结束8.3.1 平面图的定义平面图的定义v显然：可平面图的子图仍然是可平面图；包含不可平面图的图是不可平面图；v容易发现，平面图G每增加1条边，图G总的边数和面数都增加1。边界面36返回 结束8.3.2 欧拉公式欧拉公式 定理定理 欧拉公式欧拉公式 （必要条件必要条件）设平面连通图设平面连通图G有有n个顶点，个顶点，m条边，条边，d个域，则有个域，则有 n-m+d=2。证明证明 对对m作归纳。作归纳。m=0,m=1时成立。假定对于时成立。假定对于m=k成立成立:nk-mk+dk=2。当。当m=k+1时，考虑删除一条边后仍然连通的情时，考虑删除一条边后仍然连通的情况。况。(1)如果如果G有回路，则删除回路上一条边后的图边数减少一，面有回路，则删除回路上一条边后的图边数减少一，面数减少一，故公式对数减少一，故公式对G成立：成立：nk-(mk+1)+(dk+1)=2.(2)G没有回路，只有割边，必有度数为一的结点，删除相应割没有回路，只有割边，必有度数为一的结点，删除相应割边的一度顶点后，结点数和边数分别减少一，面数不变，故边的一度顶点后，结点数和边数分别减少一，面数不变，故仍然有仍然有(nk+1)-(mk+1)+dk=2.欧拉公式对非简单图仍然成立。欧拉公式对非简单图仍然成立。37返回 结束8.3.2 欧拉公式欧拉公式对于对于n个顶点，个顶点，m条棱，条棱，d个面的凸多面体，个面的凸多面体，n-m+d=2.推论推论 设平面图设平面图G的连通分支数为的连通分支数为k，并有，并有n个个顶点，顶点，m条边，条边，d个域，则有个域，则有 n-m+d=k+1。证明证明 对每个连通分支使用欧拉公式，注意它对每个连通分支使用欧拉公式，注意它们共同拥有一个无穷面。们共同拥有一个无穷面。定理 若图G是简单的平面图，则图G至少有一个顶点的度小于小于6。38返回 结束8.3.3 极大平面图极大平面图 极大平面图极大平面图 设设G=(V,E)为简单平面图，为简单平面图，|V|3，若对任意，若对任意vi,vj V，且，且(vi,vj)E，有，有G=(V,E(vi,vj)为非平面图，则称为非平面图，则称G为为一个极大平面图。一个极大平面图。“极大性极大性”乃针对固定顶点数的图的边的数乃针对固定顶点数的图的边的数目而言。目而言。39返回 结束8.3.3 极大平面图极大平面图v极大平面图的性质极大平面图的性质极大平面图是连通图。极大平面图是连通图。极大平面图的每个面都由极大平面图的每个面都由3条边组成。条边组成。极大平面图有极大平面图有3d=2m（d为面数目，为面数目，m 为边数目）。为边数目）。定理定理 设极大平面图设极大平面图G有有n个顶点，个顶点，m条边，条边，d个域，个域，则有则有m=3n-6，d=2n-4。证明证明 将将3d=2m代入欧拉公式。代入欧拉公式。推论推论 简单平面图简单平面图G有有 m 3n-6，d 2n-4。定理定理 简单平面图至少有一个顶点的度小于简单平面图至少有一个顶点的度小于6。证明证明 设任一点的度设任一点的度 6，得，得 m 3n，矛盾。，矛盾。40返回 结束8.3.4 非平面图非平面图 例例 K3,3K5K3,3K5 是不可平面的。是不可平面的。证明证明 如果如果G是平面图，是平面图，则有则有 m 3n-6,将将n=5,m=10代入得到代入得到10 9,矛盾！矛盾！K3,3 是不可平面的。是不可平面的。证明证明 注意注意 K3,3中的回路中的回路长度是偶数，至少是长度是偶数，至少是4，即每个面的度数至少是即每个面的度数至少是4。所以，所以，4|R|2|E|.如果如果K3,3 是可平面的，则面数是可平面的，则面数=5，由此的由此的20 18。矛。矛盾！盾！41返回 结束8.3.4 非平面图非平面图K5 和和K3,3 称为基本的不可平面图，或称为基本的不可平面图，或 Kuratowski(库拉图斯基)图。图。同胚同胚 设设G是一个平面图，通过删除是一个平面图，通过删除G的一条边的一条边(x,y)，并且，并且添加一个新结点添加一个新结点a和两条边和两条边(x,a)与与(a,y)(所获得的任何所获得的任何图也是平面图图也是平面图)，这样的操作成为初等细分。若可以从，这样的操作成为初等细分。若可以从相同的图相同的图G通过一系列初等细分来获得图通过一系列初等细分来获得图G1和和G2，称，称G1和和G2是同胚的是同胚的(homeomorphism)。例：两个同胚图42返回 结束8.3.4 非平面图非平面图与与K5同胚的图，称为同胚的图，称为K(1)型图；与型图；与K3,3同胚的图，称为同胚的图，称为K(2)型图；型图；K(1)型图和型图和K(2)型图统称型图统称K型图。型图。vKuratowski 定理定理 图图 G=(V,E)可平面当且仅当可平面当且仅当G中不存在任何中不存在任何K型子图。型子图。库拉图斯基定理给出了平面图的充要条件，但库拉图斯基定理给出了平面图的充要条件，但用它并不能得出判别一个图是否为平面图的有效用它并不能得出判别一个图是否为平面图的有效算法。算法。v根据Kuratowski定理，可以断定：所有树树都是平面图。43返回 结束8.3.4 非平面图非平面图v例例彼得森彼得森(petersen)图不是平面图图不是平面图