离散数学PPT教学图论.ppt

《离散数学PPT教学图论.ppt》由会员分享，可在线阅读，更多相关《离散数学PPT教学图论.ppt（60页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、欢欢迎迎进进入入第第11章章图图论论本章重难点本章重难点:重点了解图的各种概念，理解并掌握握手定理的应用以及各种矩阵的表示。难点是图的最短路径和关键路径的求法。第第11章章 图图 论论第一节第一节图的基本概念图的基本概念第二节第二节图的矩阵表示图的矩阵表示第三节第三节生成树、最短路径和关键路径生成树、最短路径和关键路径第四节第四节特殊图（欧拉图和哈密顿图等）特殊图（欧拉图和哈密顿图等）第五节第五节树、二叉树和哈夫曼树树、二叉树和哈夫曼树一一、图的基本概念、图的基本概念图的定义：图的定义：图图（graph）G由三个部分所组成：由三个部分所组成：（1）非空集合）非空集合V(G)称为图称为图G的的结

2、点集结点集，其成员称为节点或顶点（，其成员称为节点或顶点（nodes or vertices）（2）集合）集合 E(G)，称为图，称为图G的的边集边集，其成员称为边，其成员称为边(edges)。（3）函数）函数G：E(G)(V(G)，V(G)，称为边称为边与顶点的与顶点的关联映射。关联映射。度的相关定义度的相关定义：在任何图中，结点在任何图中，结点v的的度度度度（degree）d(v)是是v所关联边的数目。所关联边的数目。而在有向图中，结点而在有向图中，结点v的的出度出度出度出度（out-degree）d+(v)是是v作为有向边起点的作为有向边起点的数目，数目，v的的入度入度入度入度（in-d

3、egree）d-(v)是是v作为有向边终点的数目，这时结点作为有向边终点的数目，这时结点v的度是它的出度与入度的和；结点的度是它的出度与入度的和；结点v的环使其度增加的环使其度增加2。一一、图的基本概念、图的基本概念连通图、强连通图、弱连通图连通图、强连通图、弱连通图 若无向图中的任意两个顶点都相互可达，则称无向图若无向图中的任意两个顶点都相互可达，则称无向图G是是连通连通连通连通的（的（connected）；）；若有向图若有向图G的任何两个顶点都是相互可达的，则称有向图的任何两个顶点都是相互可达的，则称有向图G是是强连通强连通强连通强连通的；的；如果如果G的任何两个顶点都是相互可达的，称有向

4、图的任何两个顶点都是相互可达的，称有向图G是是单单单单向连通向连通向连通向连通的；的；如果如果G的任何两个顶点中，至少从一个顶点到另一个顶点的任何两个顶点中，至少从一个顶点到另一个顶点是可达的，称有向图是可达的，称有向图G是是弱连通弱连通弱连通弱连通的。的。一一、图的基本概念、图的基本概念邻接和关联邻接和关联无向图和有向图无向图和有向图零图和平凡图零图和平凡图简单图简单图完全图（无向完全图和有向完全图）完全图（无向完全图和有向完全图）有环图有环图一一、图的基本概念、图的基本概念有限图和无限图有限图和无限图 设图设图G为为（l）当）当V和和E为有限集时，称为有限集时，称G为为有限图有限图有限图有

5、限图，否则称，否则称G为为无限图无限图无限图无限图。（2）当）当G为单射时，称为单射时，称G为为单图单图单图单图；当；当G为非单射时，称为非单射时，称G为为重图重图重图重图，又称满足又称满足(e1)=(e2)的不同边的不同边e1，e2，为，为重边重边重边重边,或或平行边。平行边。平行边。平行边。正则图正则图 各顶点的度均相同的图称为各顶点的度均相同的图称为正则图正则图正则图正则图（regular graph）。）。各顶点度均为各顶点度均为k的正则图称为的正则图称为k-k-正则图正则图正则图正则图。同构图同构图一一、图的基本概念、图的基本概念子图、真子图、生成子图子图、真子图、生成子图设图设图G

6、1，G2，称称G1为为G2的的子图子图子图子图（subgraph）；）；如果如果V1 V2，E1 E2，1 2，称，称G1为为G2的的真子图真子图真子图真子图；如果如果G1是是G2的子图，且的子图，且G1 G2，称，称G1为为G2的的生成子图生成子图生成子图生成子图（spanning subgraph）；如果）；如果G1是是G2的子图，且的子图，且V1=V2。握手定理的证明握手定理的证明每个图中，节点度数的总和等于边的每个图中，节点度数的总和等于边的2倍。倍。证明：因为每条边必关联两个节点，而一 条边给予关联的每个节点的度数为1，因此在一个图中，节点度数的总和等于边数的2倍。握手定理的运用握手

7、定理的运用定理定理1：在任何图中，度数为奇数的节点个在任何图中，度数为奇数的节点个数必定是偶数个。数必定是偶数个。证明：（自己思考！）定理定理2：在任何有向图中，所有节点入度之和在任何有向图中，所有节点入度之和等于所有节点的出度之和。等于所有节点的出度之和。证明：因为每一条有向边必对应一个入度及一个出度，所以有向图中各节点入度之和等于边数，各节点的出度之和也等于边数。例：设图例：设图G为下列情况：为下列情况：(1)16条边，每个顶点都是条边，每个顶点都是2度；度；(2)21条边，条边，3个个4度顶点，其余均为度顶点；度顶点，其余均为度顶点；(3)24条边，各节点的度数均相同；条边，各节点的度数

8、均相同；试求每个图有几个节点？试求每个图有几个节点？握手定理的应用握手定理的应用解答：利用握手定理，设图有x个节点，则x=16*2 x=1621*2=12+3*x x=10 故图中有个节点(3)x*m=24*2 二、图的矩阵表示二、图的矩阵表示1.关联矩阵关联矩阵2.邻接矩阵邻接矩阵3.可达矩阵可达矩阵4.布尔矩阵布尔矩阵5.代价矩阵代价矩阵 二、图的矩阵表示二、图的矩阵表示1.关联矩阵关联矩阵无向图的关联矩阵无向图的关联矩阵-以节点数为行,边数为列.若有环,则关联数为2,无关联则为0.每行之和为该顶点的度,列之和一定为2.有向图的关联矩阵有向图的关联矩阵-以节点数为行,边数为列.节点与边无关

9、系,为0,有关系,则起点为1,终点为-1;列之和一定为0,每行绝对值之和等于该节点的度数;其中1的个数为该节点的出度,-1的个数为对应节点的入度;所有元素的和为0,1的个数等于-1的个数,都等于边数m.二、图的矩阵表示二、图的矩阵表示2.邻接矩阵邻接矩阵无向图的邻接矩阵无向图的邻接矩阵-行和列均为节点的数目;是个对称距阵,行之和等于列之和,均等于该顶点的度;主对角线都为0,除非有环才为1;边的数目m为1的数目总和的一半.有向图的邻接矩阵有向图的邻接矩阵-行和列均为节点的数目;不是对称距阵,行之和等于该顶点的出度,列之和等于该顶点的入度;主对角线都为0,除非有环才为1;边的数目m为非0的数目的总

10、和.二、图的矩阵表示二、图的矩阵表示3.可达矩阵可达矩阵-行和列均为节点的数目;节点和节点之间若至少存在一条路则为1,不存在路则为0.4.布尔矩阵布尔矩阵-由可达距阵转变,把非0的数值均改为1即可.5.代价矩阵代价矩阵-若邻接距阵元素为1的以权值表示,距阵元素为0的则以表示.三、生成树、最短路径和关键路径三、生成树、最短路径和关键路径生成树定义生成树定义1、深度优先遍历2、广度优先遍历最小生成树最小生成树构造最小生成树的三种方法：1、Kruskal算法2、管梅谷算法3、Prim算法第四节 欧拉图和哈密顿图欧拉图的由来：哥尼斯堡七桥问题哥尼斯堡城市有一条横贯全城的普雷格尔河，河中有两个小岛，城的

11、各部分用七座桥连接，每逢假日，城中居民进行环城逛游，这样就产生了一个问题，能不能设计一次遍游，使得从某地出发对每座跨河桥只走一次，而在遍历了七桥之后却又能回到原地。第四节 欧拉图和哈密顿图通过图中所有边一次且仅一次行遍所有顶点的通路称为欧拉通路（欧拉路）。通过图中所有边一次且仅一次行遍所有顶点的回路称为欧拉回路。只有具有欧拉回路的图才能称为欧拉图。具有欧拉通路而无欧拉回路的图称为半欧拉图。第四节 欧拉图和哈密顿图 欧拉在1736年的论文中提出了一条简单准则，确定了哥尼斯堡七桥问题是不能解的。定理定理1：无向图是欧拉图当且仅当G是连通图且没有奇度顶点。定理定理2：无向图是半欧拉图当且仅当G是连通

12、的且恰有两个奇度顶点。第四节 欧拉图和哈密顿图定理定理3：有向图D是欧拉图当且仅当D是强连通的且每个顶点的 入度等于出度。定理定理4：有向图D是半欧拉图当且仅当D是单向连通的且恰有两个奇度顶点，其中一个顶点的入度比出度大1，另一个顶点出度比入度大1，而其余顶点的 入度等于出度。第四节 欧拉图和哈密顿图欧拉图的应用：一笔画问题：一个图能一笔画出是指从图某一点出发，不间断地画完整个图，最后回到起点。第四节 欧拉图和哈密顿图哈密顿图的由来周游世界问题：一个数学游戏，能不能在一个十二面体中找到一条回路，使它含有这个图的所有结点？把每个结点看成一个城市，连接两个结点的边看成是交通线，也即能否找到旅游线路

13、，沿着交通线经过每个城市恰好一次再回到原来的出发地？第四节 欧拉图和哈密顿图经过图中所有顶点一次且仅一次的通路称为哈密顿通路（哈密顿路）。通过图中所有顶点一次且仅一次的回路称为哈密顿回路。只有具有哈密顿回路的图才能称为哈密顿图。具有哈密顿通路而无哈密顿回路的图称为半哈密顿图。第四节 欧拉图和哈密顿图定理定理1（必要条件）：设无向图G=是哈密顿图，则对于任意V1 V且V1 空集，均有 P（G-V1）V1定理定理2（充分条件）：设G是n阶无向简单图，若对于G中任意不相邻的顶点u，v，均有 d（u）+d（v）n-1，则G中存在哈密顿通路。推论：推论：设G为n（n3）阶无向简单图，若对于G中任意两个不

14、相邻的顶点u，v均有 d（u）+d（v）n，则G中存在哈密顿回路。第四节 欧拉图和哈密顿图哈密顿图的应用在某次国际会议的预备会中，共有8人参加，他们来自不同的国家，已知他们中任何两个无共同语言的人，与其余有共同语言的人数之和大于或等于8，试证明能将这8个人排在圆桌旁，使其任何人都能与两边的人交谈。一、无向树一、无向树1.定义：定义：无回路的连通无向图称为无向树，简称树。无回路的连通无向图称为无向树，简称树。树中度数为树中度数为1的顶点称为树叶，度数大于的顶点称为树叶，度数大于1的顶点称为内部结点或分枝点。的顶点称为内部结点或分枝点。若图若图G的每个连通分图都是树的每个连通分图都是树,G称为森林

15、称为森林。第五节第五节 树、二叉树和哈夫曼树树、二叉树和哈夫曼树 2 2、树的五个等价定义、树的五个等价定义Th1.Th1.无向图无向图T T是树，当且仅当下列条件之一成立：是树，当且仅当下列条件之一成立：1.1.无回路且无回路且m=n-1m=n-1的图的图 2.2.连通且连通且m=n-1 m=n-1 的图的图 3.3.无无 回回 路路，但但 增增 加加 任任 一一 新新 边边，得得 到到 且且 仅仅 得得 到到 一个基本回路一个基本回路 4.4.连通但删去任一边，图便不连通。连通但删去任一边，图便不连通。(n=2)(n=2)5.5.每一对顶点间有唯一的一条通路。每一对顶点间有唯一的一条通路。

16、(n=2)(n=2)证明：证明思路证明：证明思路 (1)(1)树树=1=1 (2)1=2 (2)1=2 (3)2=3 (3)2=3 (4)3=4 (4)3=4 (5)4=5 (5)4=5 (6)5=6 (6)5=6 (1)(1)树树=1=1 即即无回路的连通无向图无回路的连通无向图=无回路且无回路且m=n-1m=n-1证明：对顶点数作归纳证明。证明：对顶点数作归纳证明。n=1n=1时，时，m=0m=0，m=n-1m=n-1成立成立 设设n=kn=k命命题题成成立立，当当n=k+1n=k+1时时，因因树树连连通通而而无无回回路路，所所以以至至少少有有一一个个度度数数为为1 1的的顶顶点点v v，

17、在在T T中中删删去去v v，及及其其关关联联边边，得得k k个个顶顶点点的的树树TT由由归归纳纳假假设设，它它有有k-1k-1条边。条边。原图原图T T边数为边数为k-1+1,k-1+1,顶点数为顶点数为k+1k+1m=n-1m=n-1成立。成立。树是无回路且树是无回路且m=n-1m=n-1的图。的图。(2)(2)无回路且无回路且m=n-1m=n-1的图的图=连通且连通且m=n-1 m=n-1 的图的图反证法反证法.证明：设证明：设T T不连通，有不连通，有k k个连通分图个连通分图 T T1 1.T.Tk k(k2)(k2)，顶点数及边数分别为，顶点数及边数分别为 n n1 1.n.nk

18、k,m,m1 1.m.mk,k,因每个连通分图是无回路连通图，因每个连通分图是无回路连通图，故符合树的定义，所以故符合树的定义，所以n ni i=m=mi-1i-1成立成立 n=m-k k1,n=m-k k1,这与这与m=n-1m=n-1前提矛盾前提矛盾 T T连通且具有连通且具有m=n-1m=n-1的图的图(3)2=3 3)2=3 即连通且m=n-1 的图=无无回回路路，但但增增加加任任一一新边，得到且仅得到一个基本回路。新边，得到且仅得到一个基本回路。证明：证明：(a)T(a)T无回路，因无回路，因T T是连通是连通,并且并且m=n-1m=n-1的图，的图，故当故当n=1n=1时，时，m=

19、n-1=0,m=n-1=0,无回路无回路 设顶点数为设顶点数为n-1n-1时无回路。时无回路。当顶点数为当顶点数为n n时，时，m=n-1m=n-1，故至少有一个顶点，故至少有一个顶点v v，使使d(v)=1d(v)=1，删去，删去v v及其关连边得图及其关连边得图TT 则由归纳假设则由归纳假设TT无回路，再加回无回路，再加回v v及关联边得及关联边得 图图T T，则，则T T也无回路。也无回路。(b)在连通图在连通图T中中,任意取两点任意取两点vi，vj,因为因为T连通所以连通所以vi，vj存在一路经，存在一路经，若增加新边若增加新边(vi,vj)，则得一回路，则得一回路，且该回路是唯一的。

20、且该回路是唯一的。(否则，删去新边，路经中必有回路。否则，删去新边，路经中必有回路。)(4)3=4.即即无无回回路路，但但增增加加任任一一新新边边，得得到到且且仅仅得得到到一一个个基基本本回回路路=连连通通，但但删去任一边，图便不连通。删去任一边，图便不连通。(n=2)(n=2)证证明明：若若图图不不连连通通，则则存存在在vi,vj,，使使vi,vj之之间间没没有有路路，增增加加边边不不产产生生回路，与前提矛盾。回路，与前提矛盾。因因T无无回回路路，故故删删去去任任一一边边，图图便便不不连通。连通。(5)4=5.即即连连通通，但但删删去去任任一一边边，图图便便不不连连通通。(n=2)(n=2)

21、=每一对顶点间有唯一的一条通路。每一对顶点间有唯一的一条通路。证证明明：因因图图连连通通，故故任任二二顶顶点点间间有有一一条条通通路路，若若二二顶顶点点间间路路径径不不唯唯一一，则则T中中有有回回路路，删删去去回回路路上上任任一一条条边边，图图仍仍连连通通，与与假假设设矛矛盾盾，所所以以，每每一一对对顶顶点点间间必必有唯一的一条通路有唯一的一条通路(6)5=树定义树定义（无回路的连通无向图）（无回路的连通无向图）因每一对顶点有唯一的一条通路，故图连通，若图因每一对顶点有唯一的一条通路，故图连通，若图有回路，则任二顶点有两条不同通路，与题设矛盾。有回路，则任二顶点有两条不同通路，与题设矛盾。证：

22、若证：若T中只有一片树叶，中只有一片树叶，则则 d（vi）2（n-1）+1=2n-1若若T中没有树叶，则中没有树叶，则 d（vi）2n均与均与 d（vi）=2m=2（n-1）矛盾。）矛盾。3、Th2：结结点点数数大大于于等等于于2的的任任意意树树，至至少少有有两两片树叶。片树叶。二、生成树二、生成树1、生成树定义：、生成树定义：若若无无向向图图的的一一个个生生成成子子图图T是是树树，则则称称T为为G的的 生生 成成 树树，T中中 的的 边边 称称 为为 树树 枝枝，E（G）-E（T）称称为为树树T的的补补，其其中中的的每每一一边边称称为为树树T的弦。的弦。注：注：(1)由定义知，只有连通图才有

23、生成树。由定义知，只有连通图才有生成树。(2)连通图的生成树不唯一，至少有一棵，连通图的生成树不唯一，至少有一棵，因通过不断地删去图因通过不断地删去图G中的回路中的边，中的回路中的边，总能得到一棵生成树。总能得到一棵生成树。e1e2e6e7e3e5e4e8基本回路：基本回路：生成树生成树e1,e7,e5,e6，e1，e7，e5，e2，e4e7,e2,e3,e4，e1，e6，e5，e2，e4e5,e4,e8，e7，e6，e5，e2，e4(3)设设连连通通图图G有有n个个顶顶点点，m条条边边，则则G的的任任一一生生成成树树有有n-1条边，条边，m-(n-1)条弦，条弦，m-n+1称为连通图的秩。称

24、为连通图的秩。2.图图G中中任任一一条条回回路路和和任任何何一一棵棵生生成成树树的的补补至至少少有有一一条条公共边。公共边。证证明明：若若G中中一一条条回回路路和和一一生生成成树树的的补补无无公公共共边边，则则表示该回路在该生成树中。这与生成树定义矛盾。表示该回路在该生成树中。这与生成树定义矛盾。3.图图G中中任任何何一一个个边边割割集集和和任任何何一一棵棵生生成成树树至至少少有有一一条条公共边。公共边。证明：若证明：若G中一个边割集和一生成中一个边割集和一生成树无公共边，则表树无公共边，则表示该边割集所分离的结点不在生成树中，这导致与生成示该边割集所分离的结点不在生成树中，这导致与生成树的定

25、义矛盾。树的定义矛盾。三、最小生成树三、最小生成树1、最小生成树定义：、最小生成树定义：设设图图G=是是赋赋权权连连通通简简单单图图，其其中中每每一一边边的的权权W(i，j)是是非非负负实实数数。生生成成树树T的的权权定定义义为为W(T)=W（i，j），（i，j）T T，使使W(T）具具有有最最小小值值的的生生成成树树称称为为G的的最最小小生生成树。成树。2、最小生成树求法、最小生成树求法-kruskal算法算法。设图设图G有有n个顶点，个顶点，m条边，条边，w(e1)w(em)k1，A若若A ek导出子图不包导出子图不包含回路，则含回路，则AAekkk+1N0 A=n-1Yes结束结束证明：

26、因证明：因T是有是有n-1条边，且无回路的图。条边，且无回路的图。由树的等价定义可知，它是树。由树的等价定义可知，它是树。又又T包含了包含了n个顶点，个顶点，故包含了故包含了G的全部顶点。的全部顶点。T是是G的生成树。的生成树。算法的正确性证明算法的正确性证明证明边集证明边集A最后所得子图最后所得子图T是是G的生成树。的生成树。、T是最小生成树是最小生成树注注：当当G中中的的权权相相等等时时，仍仍可可用用本本算算法法，只只是是所得之最小生成树不唯一。所得之最小生成树不唯一。证明证明T是最小生成树是最小生成树（证明方法：（证明方法：T逐步转化逐步转化T证明：设证明：设T是最小生成树，是最小生成树

27、，T是由是由krusal算法生成的树算法生成的树，若，若T与与T不同，但有公共边不同，但有公共边e1.ei(i=0),则则 ei+1 T ei+1 T,则在则在T ei+1中有一回路中有一回路r,而而T是树，是树，因任一回路与生成树的补必有一公共边，所以在因任一回路与生成树的补必有一公共边，所以在r中中必存在一条边必存在一条边f T对于树对于树T(边集至少为边集至少为e1.ei,f)，若用，若用ei+1代换代换f，得，得一棵新树一棵新树T1(边集至少为边集至少为e1.eiei+1)则则T1的权的权W(T1)=W(T1)+W(ei+1)-W(f)因为因为T为最小生成树为最小生成树W(T)W(T1

28、)W(ei+1)W(f)又根据又根据T生成法生成法自自e1.ei之后将取之后将取f而不是而不是ei+1而现在而现在T取取ei+1W(ei+1)W(f)W(ei+1)=W(f)T1也是也是G的最小生成树。而的最小生成树。而T1与与T的公共边比的公共边比T与与T的公共边多的公共边多1，用，用T1置换置换T，重复上面论证直至，重复上面论证直至T与与T有有n-1条公共边，从而证得条公共边，从而证得T也是也是G的最小生成树。的最小生成树。一、有向树一、有向树定义定义:1.若若一一个个有有向向图图T的的底底图图是是无无向向树树，且且恰恰有有一一个个结结点点的的入入度度为为0，其其余余所所有有结结点点入入度

29、度为为1，称称T为为有有向向树树。入入度度为为0的的结结点点称称为为根根，出出度度不不为为0的的结结点点称称为为分分枝枝点点或或内内部部结结点点，出出度度为为0的的结结点称为数叶或外部结点。点称为数叶或外部结点。注意：有向树通常采用根在顶点上，所有边方注意：有向树通常采用根在顶点上，所有边方向向下的图表示向向下的图表示.(箭头也可省略箭头也可省略)有有向向树树及及应应用用2.基本概念基本概念:设设a和和b是树是树T的结点，若从的结点，若从a到到b有一条边称有一条边称a是是b的的父亲父亲，b是是a的的儿子儿子，同一个分枝点的儿子，称为，同一个分枝点的儿子，称为“兄弟兄弟”。若从若从a到到c有一有

30、向路径，称有一有向路径，称a是是c的的祖先祖先，c是是a的的子孙子孙.由结点由结点a和它所有的后代导的子图，称为和它所有的后代导的子图，称为T的的子树子树.从树根从树根r到一结点到一结点a的路径所含的边数称为的路径所含的边数称为a的的路径长度路径长度。树树T中最长的路径称为树中最长的路径称为树T的的高度高度。例题:abc由有向树的结构可知，它还可以递归定义如下由有向树的结构可知，它还可以递归定义如下:3.有有向向树树有有一一个个根根，其其余余的的结结点点划划分分为为m0个个不不相交的集合相交的集合T1.Tm，且每个集合是子有向树。，且每个集合是子有向树。4.有向树的括号表示有向树的括号表示若若

31、T中只有一个结点，则此结点就是它的括号表示。中只有一个结点，则此结点就是它的括号表示。若若T由根由根v和子树和子树T1T2.Tn组成，则组成，则T的括号表示为的括号表示为v(T1T2.Tn）.5.m元完全树，正则树的定义元完全树，正则树的定义定定义义:在在树树T中中若若每每一一结结点点的的儿儿子子个个数数小小于于或或等等于于m,称称T为为m元元树树;在在树树T中中若若每每一一结结点点的的儿儿子子个个数数等等于于m或或者者等等于于0，称称T为为完完全全m元元树树。若若完完全全m元元树树所所有有树树叶叶层层次相同，称为正则次相同，称为正则m元树。元树。5.有向森林定义有向森林定义一个有向图一个有向

32、图G，若它的每个连通分量是有向树，若它的每个连通分量是有向树，称称G为为(有向有向)森林，在森林中，若所有树是有序树，且森林，在森林中，若所有树是有序树，且给每棵树指定次序，称此森林为有序森林给每棵树指定次序，称此森林为有序森林.bcbcabc完全完全3元树元树完全完全2元树元树正则正则2元树元树6、有序树，有序森林与二元树相互转换、有序树，有序森林与二元树相互转换有序树转换为二元树，转换过程为：有序树转换为二元树，转换过程为：a)在各兄弟结点之间加一连线。在各兄弟结点之间加一连线。b)对对任任何何结结点点，除除最最左左的的儿儿子子之之外外，擦擦掉掉该该结结点点与与其余儿子的联线。其余儿子的联

33、线。c)对新图向下旋转对新图向下旋转45度。度。bcbc-2.有序森林转换为二元树转换过程有序森林转换为二元树转换过程a)设置一个总根，联结各树的根，得设置一个总根，联结各树的根，得Tb)把把T转换为二元树转换为二元树c)删除总根删除总根二二.完全完全m元树性质元树性质1.设完全设完全m元树，叶数为元树，叶数为t，分枝数为，分枝数为i，则，则t=(m-1)i+1解解:i=(t-1)/(m-1)=(10-1)/(3-1)=5答答:至少执行至少执行5次加法指令次加法指令.例：若例：若t=i(m-1)+1计算机有一计算三数之和的加计算机有一计算三数之和的加法器法器,现求十个数之和现求十个数之和,问至

34、少执行多少次加法指令问至少执行多少次加法指令?证明证明:若把完全若把完全m元树视为元树视为m个选手参加淘汰赛个选手参加淘汰赛,则则t表示选手总数表示选手总数,i表示比赛场数表示比赛场数,每场比赛淘汰每场比赛淘汰m-1人人,共淘汰共淘汰i(m-1)人人,剩下一个冠军剩下一个冠军,所以所以t=(m-1)i+12、内部通数长度、内部通数长度I定义：各分枝点路径长度之和。定义：各分枝点路径长度之和。内部通数长度内部通数长度E定义：各定义：各叶子路径长度之和叶子路径长度之和.性质：完全二叉树性质：完全二叉树T有有E=I+2n其中其中:n为分枝点数为分枝点数证：对证：对n n用数学归纳法用数学归纳法:当当

35、n=1,n=1,则叶数为则叶数为2 2，I=0I=0，E=2E=2，E=I+2nE=I+2n成立成立;当当n=2,n=2,则叶数为则叶数为3 3，I=1I=1，E=5E=5，E=I+2nE=I+2n成立成立;设设n=k-1n=k-1时，结论成立时，结论成立;则则n=kn=k时时，若若删删去去长长度度为为e+le+l其其关关系系为为兄兄弟弟的的叶叶子子，得得TT，TT与与原原树树比比较较，减减少少一一个个长长度度为为e e的的分分枝枝点点、二二个个长长度度为为e+1e+1的的叶叶子子，增增加加一一长长度度为为e e的的叶叶子子，E=I+2E=I+2（k-1k-1）而而I=I-e.I=I-e.所以

36、所以E=E-2E=E-2（e+1)+e,e+1)+e,即即E-2(e+1)+e=E-2(e+1)+e=I-eI-e+2(k-1)+2(k-1)所以所以 E=I+2k.E=I+2k.三、三、前缀码和最优树前缀码和最优树1、问题的引出：问题的引出：传传递递信信息息中中，可可用用5位位01序序列列表表示示一一个个英英文文字字母母，因因每每个个字字母母的的使使用用频频率率不不一一样样，人人们们希希望望用用较较短短的的序序列列表示常用字母，但产生问题：表示常用字母，但产生问题：e：00，t：01，q：0001，则，则0001为为q还是为还是为et。2、前缀码定义：前缀码定义：若若01序序列列集集合合中中

37、，任任何何序序列列都都不不是是另另一一个个序序列列的的前前缀，则这个序列集合称为前缀码。缀，则这个序列集合称为前缀码。注注1：任意前缀码均可用完全二元树的叶子表示。：任意前缀码均可用完全二元树的叶子表示。注：注：1、任意前缀码均可用完全二元树的叶子表示。、任意前缀码均可用完全二元树的叶子表示。2、由任一棵完全二元树可得前缀码。、由任一棵完全二元树可得前缀码。3、使用前缀码可分辨出长短不一的序列。、使用前缀码可分辨出长短不一的序列。方法：从根出发，接收到方法：从根出发，接收到0朝左走，接收到朝左走，接收到1右走，右走，直到树叶。直到树叶。4、如何设计，使字母编码根据使用频率平均最短。、如何设计，

38、使字母编码根据使用频率平均最短。0001110001 1011例如：例如：5个字母个字母a，b，c，d，e，f的使用频率分别的使用频率分别为为3，4，5，6，12，试求出最优树及对应的前缀，试求出最优树及对应的前缀码码。3456125，6，7，127，11，1212，183000111354612前缀码为前缀码为a：000，b：001，c：010，d：011最优树的权为最优树的权为W（T）=3（3+4+5+6）+12=40所以，一篇所以，一篇30个字母的电文，若用前缀码，平均只需发个字母的电文，若用前缀码，平均只需发送送40位，若每个字母用位，若每个字母用3位表示，须发送位表示，须发送90位。位。本 章 小 结 课后练习和作业课后练习：P304：1，2，3P307：17，18，19P308：26，29课后作业：P305：7P306：12P307：20，22