《运筹学 第一节 图与网络的基本知识幻灯片.ppt》由会员分享，可在线阅读，更多相关《运筹学 第一节 图与网络的基本知识幻灯片.ppt（56页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、运筹学课件 第一节 图与网络的基本知识1第1页，共56页，编辑于2022年，星期三图的基本概念图的基本概念G=G=（V，E）子图子图矩阵表示矩阵表示含元素的个数含元素的个数点的次点的次边边 图图点边关系点边关系简简单单图图多多重重图图连通图连通图树树生成子图生成子图2第2页，共56页，编辑于2022年，星期三第二节第二节 树树 主要内容主要内容 一、树的概念以及性质一、树的概念以及性质 二、图的生成树：深探法、广探法和破圈法二、图的生成树：深探法、广探法和破圈法 三、最小生成树：避圈法和破圈法三、最小生成树：避圈法和破圈法 四、根树及其应用四、根树及其应用3第3页，共56页，编辑于2022年，
2、星期三树是一类极其简单而很有用的图。树是一类极其简单而很有用的图。树是一类极其简单而很有用的图。树是一类极其简单而很有用的图。多级辐射制的电信网络、家谱、分类学、管理组织多级辐射制的电信网络、家谱、分类学、管理组织多级辐射制的电信网络、家谱、分类学、管理组织多级辐射制的电信网络、家谱、分类学、管理组织结构等都是典型的树图。结构等都是典型的树图。结构等都是典型的树图。结构等都是典型的树图。某企业的组织结构某企业的组织结构图图总经理生产经理人力经理销售经理车间主任销售代表招聘人员一、树的概念以及性质一、树的概念以及性质A B C D E FN乒乓球单打比赛抽签后，用图乒乓球单打比赛抽签后，用图表示
3、相遇情况表示相遇情况v1v2w1v3w2V4第4页，共56页，编辑于2022年，星期三树实际上是树实际上是连通图连通图，但没，但没有有圈圈。由所有节点。由所有节点(n)(n)和和相应的边相应的边(n-1)(n-1)组成。组成。定义定义14141414（树）（树）（树）（树）:一个无圈的一个无圈的一个无圈的一个无圈的连通连通连通连通无无向图称为向图称为树树。树中次为树中次为1 1 1 1的点为的点为的点为的点为树叶树叶树叶树叶；次大于；次大于；次大于；次大于1 1 1 1的的的的点为点为点为点为分枝点分枝点分枝点分枝点。b bf fe ed dv1v2v3v4v5d(v1)=1;v1树叶d(v2
4、)=1;v2树叶d(v5)=1;v5树叶d(v4)=4;v4分枝点d(v3)=1;v3树叶5第5页，共56页，编辑于2022年，星期三例：判断下列图形是否为树例：判断下列图形是否为树图1v1v2e1树树图2v1v2v3e1e2e36第6页，共56页，编辑于2022年，星期三v2a ab bc cf fe ed dh hg g图3v1v3v4v5图4b bf fd dg gv1v2v3v5v4树树7第7页，共56页，编辑于2022年，星期三a ab bc ch h图5v1v2v3v4v5b bc ce ed d图6v1v2v3v4v5树树树树8第8页，共56页，编辑于2022年，星期三v4v3a
5、 af fd dg g图7v1v2v5v3b bf fe ed d图8v1v2v4v5树树树树9第9页，共56页，编辑于2022年，星期三树的性质：树的性质：1 1、在图中任意两点之间必有一条而且只有一在图中任意两点之间必有一条而且只有一条链。条链。2 2、在图中划去一条边，则图不连通。在图中划去一条边，则图不连通。3 3、在图中不相邻的两个顶点之间加一条边，在图中不相邻的两个顶点之间加一条边，可得一个且仅得一个圈。可得一个且仅得一个圈。4 4、图中边数有图中边数有m=n-1m=n-1（n n为顶点数）为顶点数）10第10页，共56页，编辑于2022年，星期三定理定理定理定理6:图图T=(V,
6、E),T=(V,E),点数点数=n;=n;=n;=n;边数边数=m=m=m=m；下列关于树的说法等价。；下列关于树的说法等价。；下列关于树的说法等价。；下列关于树的说法等价。（1 1 1 1）T T是一棵树；是一棵树；（2 2 2 2）T T T T无圈，且无圈，且无圈，且无圈，且m=n-1m=n-1；（3 3）T T连通，且连通，且m=n-1m=n-1；（4 4）T T无圈，但任加一新边得到唯一一个圈；无圈，但任加一新边得到唯一一个圈；无圈，但任加一新边得到唯一一个圈；无圈，但任加一新边得到唯一一个圈；（5 5 5 5）T T连通，但任舍去一边就不连通；连通，但任舍去一边就不连通；连通，但任
7、舍去一边就不连通；连通，但任舍去一边就不连通；（6 6 6 6）T T任意两点，有唯一链相连。任意两点，有唯一链相连。任意两点，有唯一链相连。任意两点，有唯一链相连。11第11页，共56页，编辑于2022年，星期三b bc cf fe ed dh hg gb bf fe ed db bf fd dg gb bc ce ed da ab bc ch ha af fd dg g图3图4图5图6图7图8a a12第12页，共56页，编辑于2022年，星期三二、图的生成树二、图的生成树定义定义15如果图如果图如果图如果图T是是G的一个生成子图，而且的一个生成子图，而且T T又是一棵树，又是一棵树，则称
8、图则称图T T为一棵为一棵生成树（支撑树）生成树（支撑树）生成树（支撑树）生成树（支撑树）。子图定义子图定义：设设设设G=G=（V V，E）和）和）和）和G1=（V1，E E1）。）。）。）。如果如果如果如果V V1 V，E1 E E，且，且E1边仅与边仅与V1中的顶点相关联，中的顶点相关联，则称则称GG1为为为为G的的子图子图；生成子图定义生成子图定义：如果如果GG1=（V1，E E1）是）是）是）是G=G=（V，E）子子子子图，并且图，并且图，并且图，并且V V1=V V，则称，则称G1为为为为G的的的的生成子图生成子图。13第13页，共56页，编辑于2022年，星期三生成树与子图、生成子
9、图的关系生成树与子图、生成子图的关系一个一个子图子图与与生成树生成树的区别是：的区别是：子图子图子图子图与原图相比少边与原图相比少边又少点，又少点，生成树生成树生成树生成树与原图相比少边不少点。与原图相比少边不少点。一个一个生成子图生成子图与与生成树生成树生成树生成树的区别是：的区别是：的区别是：的区别是：生成子图生成子图可能含有可能含有可能含有可能含有圈，圈，圈，圈，生成树生成树无圈。无圈。图中属于生成树的边为图中属于生成树的边为树枝，树枝，不在生成树中的边为不在生成树中的边为不在生成树中的边为不在生成树中的边为弦。弦。弦。弦。14第14页，共56页，编辑于2022年，星期三子图子图练习练习
10、1：找出图：找出图G的子图，生成子图，生成树的子图，生成子图，生成树图图1 1e e1 1e e8 8e e7 7e e6 6e e5 5e e4 4e e3 3e e2 2v5v3v4v2v1e e8 8e e1 1e e7 7e e6 6e e5 5e e4 4e e3 3v5v4v2v1图图G G15第15页，共56页，编辑于2022年，星期三生成子图生成子图e e1 1e e8 8e e7 7e e6 6e e5 5e e4 4e e3 3e e2 2v5v3v4v2v1e e1 1e e8 8e e6 6e e4 4e e3 3e e2 2v5v3v4v2v1图图2 2图图G G16
11、第16页，共56页，编辑于2022年，星期三生成子图；生成子图；生成树；生成树；树枝树枝e e2 2,e,e3 3,e,e5 5,e,e6 6;弦弦e e1 1,e,e4 4,e,e7 7,e,e8 8e e5 5e e2 2e e6 6图图3 3图图G Ge e3 3e e1 1e e8 8e e7 7e e6 6e e5 5e e4 4e e3 3e e2 2v5v3v4v2v1v3v2v1v4v517第17页，共56页，编辑于2022年，星期三定理定理7 7图图G G有生成树的充分必要条件为图有生成树的充分必要条件为图G G是连通图是连通图。生成树生成树的求解方法：的求解方法：（1 1）
12、深探法）深探法步骤：步骤：a.a.在点集在点集V V中任取一点中任取一点v,v,给给v v标号标号0 0；b.b.如果某点如果某点u u已经得到标号已经得到标号i,i,检查一端点为检查一端点为u u的各边，另的各边，另一端是否已经标号。如果有（一端是否已经标号。如果有（u,wu,w）边的）边的w w点未标号，点未标号，则则给给w w以标号以标号i+1,i+1,记下边（记下边（u,wu,w）。令）。令w w代替代替u,u,继续重复。继续重复。如果有（如果有（u,wu,w）边的）边的w w已经标号已经标号，则退到标号，则退到标号i-1i-1的的r r点点,令令r r代替代替u,u,继续重复。继续重
13、复。18第18页，共56页，编辑于2022年，星期三012345678910111213u u已经得到标号已经得到标号,检查一端点为检查一端点为u u的各边，另一端的各边，另一端w w是否已经标是否已经标号，有（号，有（u,wu,w）边的）边的w w已经标号，则退到标号已经标号，则退到标号i-1i-1的的r r点点,令令r r代替代替u,u,继续重复。继续重复。r=5-1;r代替u19第19页，共56页，编辑于2022年，星期三原则：不能成圈原则：不能成圈原则：不能成圈.0.1.3.4.5.2.6.7.8.9.10.11.12.1301234567891011121320第20页，共56页，编
14、辑于2022年，星期三（2 2）广探法）广探法步骤：步骤：a.a.在点集在点集V V中任取一点中任取一点v,v,给给v v标号标号0 0；b.b.令所有标号令所有标号i i的点集为的点集为V Vi i,检查检查VVi i,VV,VVi i 中的边端点是否已中的边端点是否已经标号，对所有的未标号的点均标号经标号，对所有的未标号的点均标号i+1,i+1,记下这记下这 些边。些边。c.c.对标号对标号i+1i+1的点继续重复步骤的点继续重复步骤b b，直至全部点得到标号，直至全部点得到标号21第21页，共56页，编辑于2022年，星期三01112222333412AB22第22页，共56页，编辑于2
15、022年，星期三14203331112222图的生成树不唯一图的生成树不唯一1111022222333423第23页，共56页，编辑于2022年，星期三（3）破圈法破圈法(深探法和广探法核心是避免成圈深探法和广探法核心是避免成圈)步骤：从图步骤：从图G G任取一个圈任取一个圈,从圈中任舍弃一条边从圈中任舍弃一条边,将将此圈破掉。重复以上步骤直至无圈为止。此圈破掉。重复以上步骤直至无圈为止。圈1圈2圈3圈4圈5圈6v1v2v3v4v5v6v724第24页，共56页，编辑于2022年，星期三练习练习2 2：分别使用深探法、广探法、破圈法：分别使用深探法、广探法、破圈法找出下图的一个生成树找出下图的
16、一个生成树25第25页，共56页，编辑于2022年，星期三01234使用深探法找出下图的一个生成树使用深探法找出下图的一个生成树26第26页，共56页，编辑于2022年，星期三使用广探法找出下图的一个生成树使用广探法找出下图的一个生成树27第27页，共56页，编辑于2022年，星期三使用破圈法找出下图的一个生成树使用破圈法找出下图的一个生成树圈圈1圈圈圈圈圈圈28第28页，共56页，编辑于2022年，星期三求最小树的方法有求最小树的方法有求最小树的方法有求最小树的方法有避圈法避圈法和和破圈法破圈法。三、最小生成树三、最小生成树三、最小生成树三、最小生成树定义定义1616：在在赋权图赋权图G G
17、中，一棵生成树所有树枝上权的和，称为中，一棵生成树所有树枝上权的和，称为中，一棵生成树所有树枝上权的和，称为中，一棵生成树所有树枝上权的和，称为生成树的权生成树的权生成树的权生成树的权。具有具有最小权的生成树最小权的生成树，称为，称为，称为，称为最小生成树或最小树或最小生成树或最小树或最小支撑树最小支撑树。最小树的应用：设计长度最小的公路网把若干城最小树的应用：设计长度最小的公路网把若干城市联系起来；设计用料最省的电话线网把有关单市联系起来；设计用料最省的电话线网把有关单位联系起来。位联系起来。29第29页，共56页，编辑于2022年，星期三例例例例 一个乡有一个乡有一个乡有一个乡有9 9 9
18、 9个村，道路及其个村，道路及其个村，道路及其个村，道路及其道路长度如图，如何拉电线才道路长度如图，如何拉电线才道路长度如图，如何拉电线才道路长度如图，如何拉电线才能使电线总长度最短能使电线总长度最短能使电线总长度最短能使电线总长度最短?1 1 1 1、避圈法（避圈法（krusakalkrusakal）步骤：每步从未选的边中选取边步骤：每步从未选的边中选取边e,e,使它与已经选的边不构成圈，使它与已经选的边不构成圈，且且e e是未选边中的最小权边，直到选够是未选边中的最小权边，直到选够n-1n-1条边条边。解解解解 （1 1）先将图中边按照大小顺序）先将图中边按照大小顺序）先将图中边按照大小顺
19、序）先将图中边按照大小顺序由小到大排列由小到大排列由小到大排列由小到大排列(v v0 0,v,v2 2)=1,()=1,(v v3 3,v,v2 2)=1,()=1,(v v3 3,v,v4 4)=1,)=1,(v v1 1,v,v8 8)=1)=1；(v v0 0,v,v1 1)=2,()=2,(v v0 0,v,v6 6)=2,()=2,(v v5 5,v,v6 6)=2)=2(v v0 0,v,v3 3)=3,()=3,(v v6 6,v,v7 7)=3;)=3;(v v0 0,v,v4 4)=4,()=4,(v v0 0,v,v5 5)=4,)=4,(v v0 0,v,v8 8)=4,
20、()=4,(v v1 1,v,v2 2)=4,)=4,(v v0 0,v,v7 7)=5,()=5,(v v7 7,v,v8 8)=5,()=5,(v v4 4,v,v5 5)=5)=5V1 1V0 0V8 8V2 2V3 3V4 4V5 5V6 6V7 7145325114421235430第30页，共56页，编辑于2022年，星期三V1 1V0 0V8 8V2 2V3 3V4 4V5 5V6 6V7 7145325114421235431第31页，共56页，编辑于2022年，星期三定理定理定理定理8:8:8:8:用避圈法用避圈法用避圈法用避圈法(kruskal)(kruskal)(krus
21、kal)(kruskal)算法得到的子图为一棵最小树算法得到的子图为一棵最小树算法得到的子图为一棵最小树算法得到的子图为一棵最小树V1 1V0 0V8 8V2 2V3 3V4 4V5 5V6 6V7 713211212使用电话线最小长度使用电话线最小长度L=1+1+1+1+2+2+2+3=1332第32页，共56页，编辑于2022年，星期三2 2 2 2、破圈法、破圈法步骤：步骤：步骤：步骤：(1)(1)从图从图G G G G中任选一棵树中任选一棵树中任选一棵树中任选一棵树T T1 1 1 1;(2)(2)(2)(2)加上一条加上一条加上一条加上一条弦弦弦弦e e e e1 1 1 1,T,T
22、,T,T1 1 1 1+e+e+e+e1 1 1 1中立即生成一个圈。去掉此圈中的中立即生成一个圈。去掉此圈中的中立即生成一个圈。去掉此圈中的中立即生成一个圈。去掉此圈中的最大权边，得到新树最大权边，得到新树最大权边，得到新树最大权边，得到新树T T2 2,以以T T T T2 2代替代替代替代替T T T T1 1 1 1，继续重复检查剩余的，继续重复检查剩余的，继续重复检查剩余的，继续重复检查剩余的弦，直到全部弦检查完毕。弦，直到全部弦检查完毕。弦，直到全部弦检查完毕。弦，直到全部弦检查完毕。定理定理9 9：图图G G的生成树的生成树T T T T为最小树，当且仅当对任一弦为最小树，当且仅
23、当对任一弦e e e e来来来来讲，讲，讲，讲，e e是是T+eT+eT+eT+e中与之对应的圈中与之对应的圈u u u ue e中的最大权边。中的最大权边。33第33页，共56页，编辑于2022年，星期三V1 1V0 0V8 8V2 2V3 3V4 4V5 5V6 6V7 7145325114421235434第34页，共56页，编辑于2022年，星期三例：先求出一棵树例：先求出一棵树例：先求出一棵树例：先求出一棵树T T T T1 1 1 1，加以弦（，加以弦（，加以弦（，加以弦（v v v v1 1 1 1,v,v,v,v2 2 2 2），得到圈），得到圈），得到圈），得到圈vvvv1
24、1 1 1v v v v2 2 2 2v v v v0 0 0 0v v v v1 1 1 1,去掉最大权边（去掉最大权边（去掉最大权边（去掉最大权边（v v v v1 1 1 1,v,v,v,v2 2 2 2 ）;再加上弦（再加上弦（再加上弦（再加上弦（v v v v2 2 2 2,v,v,v,v3 3 3 3 ），得到圈），得到圈），得到圈），得到圈vvvv2 2 2 2v v v v3 3 3 3v v v v0 0 0 0v v v v2 2 2 2,去掉最大权边（去掉最大权边（去掉最大权边（去掉最大权边（v v v v0 0 0 0,v,v,v,v3 3 3 3 ）,全部弦。全部弦。
25、全部弦。全部弦。2134142544152351V1 1V0V7 7V6 6V8 8V2 2V3 3V4 4V5 5使用电话线最小长度使用电话线最小长度L=1+1+1+1+2+2+2+3=1335第35页，共56页，编辑于2022年，星期三另一种破圈法：找圈，擦除最大边以破圈。另一种破圈法：找圈，擦除最大边以破圈。赋权赋权图图G1542453134421512生成最小树生成最小树T T12312112圈1圈2圈3圈4圈5圈6圈7圈8使用电话线最小长度使用电话线最小长度L=1+1+1+1+2+2+2+3=1336第36页，共56页，编辑于2022年，星期三V V1 1V V6 6V V3 3V
26、V4 4V V5 5V V2 2V V7 74323245172674练习练习3 3：破圈法求下图的最小树破圈法求下图的最小树最小树的权最小树的权=3+3+2+2+1+2=13=3+3+2+2+1+2=1337第37页，共56页，编辑于2022年，星期三9 93 317174 41 12323202015151616252528283636练习练习4 4：避圈法求下图的最小树避圈法求下图的最小树最小树的权最小树的权=1+4+9+3+17+23=57=1+4+9+3+17+23=57v2v3v4v5v6v7v138第38页，共56页，编辑于2022年，星期三根根根根：根树入次：根树入次：根树入次
27、：根树入次=0=0=0=0的点；的点；的点；的点；叶叶叶叶:根树出次根树出次根树出次根树出次=0=0=0=0的点；其他的顶点为的点；其他的顶点为的点；其他的顶点为的点；其他的顶点为分枝点分枝点分枝点分枝点。层次层次层次层次：由根到某一顶点的道路长度（假设每边的长度为：由根到某一顶点的道路长度（假设每边的长度为：由根到某一顶点的道路长度（假设每边的长度为：由根到某一顶点的道路长度（假设每边的长度为1 1 1 1），称为点），称为点），称为点），称为点的层次。的层次。的层次。的层次。四、根树及其应用四、根树及其应用四、根树及其应用四、根树及其应用1 1 1 1、根树根树根树根树对有向图而言对有向图
28、而言对有向图而言对有向图而言,根树在计算机科学、决策论有重要应用根树在计算机科学、决策论有重要应用根树在计算机科学、决策论有重要应用根树在计算机科学、决策论有重要应用定义定义定义定义17171717：如果一个有向图在不考虑边的方向时是一棵树，如果一个有向图在不考虑边的方向时是一棵树，如果一个有向图在不考虑边的方向时是一棵树，如果一个有向图在不考虑边的方向时是一棵树，此有向图为此有向图为此有向图为此有向图为有向树有向树有向树有向树。定义定义定义定义18181818：有向树：有向树：有向树：有向树T,T,T,T,恰好有一个结点入次恰好有一个结点入次恰好有一个结点入次恰好有一个结点入次=0=0=0=
29、0，其余各点入次，其余各点入次，其余各点入次，其余各点入次=1=1=1=1，树树树树T T T T为为为为根树（外向树）根树（外向树）根树（外向树）根树（外向树）。39第39页，共56页，编辑于2022年，星期三V V1 1:根根根根V1V4V9V8V7V6V5V2V10V3例例V V5 5,V,V6 6,V,V4 4,V,V7 7,V,V9 9,V,V1010：叶叶叶叶V V1 1,V,V2 2.V.V3 3,V,V8 8：分枝点分枝点分枝点分枝点V V2 2,V,V3 3,V,V4 4的的的的层次层次层次层次：1 1V V5 5,V,V6 6,V,V7 7,V,V8 8,V,V9 9的的层
30、次层次层次层次：2 2V V1010层次层次层次层次：3 3v1入次入次=0其它点入次其它点入次=1T根树根树v5,v6出次出次=0v4出次出次=0v7,v9出次出次=0v10出次出次=0根树应用根树应用:系统的传递关系系统的传递关系;指挥系统的上下级关系指挥系统的上下级关系;计算机科学的应用计算机科学的应用有向树有向树40第40页，共56页，编辑于2022年，星期三定义定义19191919：在根树中，如果每个顶点的出次等于在根树中，如果每个顶点的出次等于在根树中，如果每个顶点的出次等于在根树中，如果每个顶点的出次等于m m m m或零，称此或零，称此树为树为完全完全m m叉树叉树叉树叉树。如
31、每个顶点的出次小于或等于。如每个顶点的出次小于或等于。如每个顶点的出次小于或等于。如每个顶点的出次小于或等于m m称此树为称此树为称此树为称此树为m m叉叉树树。当当当当m=2m=2时，为时，为时，为时，为完全二叉树、二叉树完全二叉树、二叉树完全二叉树、二叉树完全二叉树、二叉树。完全三叉树完全三叉树完全三叉树完全三叉树四叉树四叉树四叉树四叉树出次出次=3出次出次=3出次出次=0出次出次=3出次出次=2出次出次=4出次出次=1出次出次=041第41页，共56页，编辑于2022年，星期三算法步骤：算法步骤：（1 1 1 1）将）将）将）将s s s s个叶子按照权大小排序。个叶子按照权大小排序。个
32、叶子按照权大小排序。个叶子按照权大小排序。（2 2 2 2）将二个具有最小权的叶子合并成一个分枝点，其权）将二个具有最小权的叶子合并成一个分枝点，其权）将二个具有最小权的叶子合并成一个分枝点，其权）将二个具有最小权的叶子合并成一个分枝点，其权p p p p1 1 1 1+p+p+p+p2 2 2 2;将新得将新得将新得将新得到的分枝点作为一个叶子。令到的分枝点作为一个叶子。令到的分枝点作为一个叶子。令到的分枝点作为一个叶子。令s=s-1,s=s-1,s=s-1,s=s-1,如果如果如果如果s=1s=1s=1s=1，停止，否则转（，停止，否则转（，停止，否则转（，停止，否则转（1 1 1 1）。
33、）。）。）。实际问题中经常讨论叶子上带权的二叉树。有实际问题中经常讨论叶子上带权的二叉树。有实际问题中经常讨论叶子上带权的二叉树。有实际问题中经常讨论叶子上带权的二叉树。有s s s s个叶子的二叉个叶子的二叉个叶子的二叉个叶子的二叉树树树树T T各个叶子的权分别为各个叶子的权分别为p p p pi i,根到叶子的层次为根到叶子的层次为根到叶子的层次为根到叶子的层次为L L L Li i(i=1,2,s),(i=1,2,s),这样叶子的二叉树的总权数这样叶子的二叉树的总权数m(T)=m(T)=满足总权最小的二叉树为满足总权最小的二叉树为最优二叉树或霍夫曼树最优二叉树或霍夫曼树。42第42页，共
34、56页，编辑于2022年，星期三例：例：S=6,S=6,其权分别为其权分别为4 4，3 3，3 3，2 2，2 2，1 1，求最优二叉树，求最优二叉树12234312234335643第43页，共56页，编辑于2022年，星期三122343356915总权为总权为m（T）=42+1 4+24+2 3+3 2+3 2=38绿绿色色为为叶子叶子;黑色黑色为层为层次。次。44第44页，共56页，编辑于2022年，星期三例例:使用计算机进行图书分类。使用计算机进行图书分类。现有现有5 5类图书共类图书共100100万册，其中有万册，其中有A A类类5050万册，有万册，有B B类类2020万册，有万册
35、，有C C类类5 5万册，有万册，有D D类类1010万册，有万册，有E E类类1515万册。万册。问如何安排分拣过程，可使总的运算（比较）次数问如何安排分拣过程，可使总的运算（比较）次数最小？最小？2 2、最优二叉树的应用、最优二叉树的应用解：解：先构造一棵具有先构造一棵具有5 5个叶子的最优二叉树，令其叶子的权个叶子的最优二叉树，令其叶子的权分别为分别为5050，2020，5 5，1010，1515，然后构造最优二叉树。，然后构造最优二叉树。45第45页，共56页，编辑于2022年，星期三510152050153050C D E B A100A？B？ANYE？BNYD？ENYDNYCm（T
36、）=54+10 4+15 3+20 2+50 1=19546第46页，共56页，编辑于2022年，星期三思考题:如何将实际应用与最小生成树的算法联系如何将实际应用与最小生成树的算法联系起来？起来？47第47页，共56页，编辑于2022年，星期三小结：小结：1 1、树的概念以及性质。、树的概念以及性质。2 2、图的生成树：深探法、广探法和破圈法。、图的生成树：深探法、广探法和破圈法。3 3、最小生成树：避圈法和破圈法。、最小生成树：避圈法和破圈法。4 4、根树及其应用。、根树及其应用。48第48页，共56页，编辑于2022年，星期三49第49页，共56页，编辑于2022年，星期三50第50页，共
37、56页，编辑于2022年，星期三证明：证明：(1)T T是一棵树是一棵树是一棵树是一棵树由于由于T是一棵树，根据定义，是一棵树，根据定义，T是连通且无圈。是连通且无圈。现在需要证明边数现在需要证明边数m=n-1m=n-1。用归纳法：。用归纳法：。用归纳法：。用归纳法：当当当当n=2n=2，由于由于T是一棵树，所以两点之间只有是一棵树，所以两点之间只有1条边，满足条边，满足m=n-1m=n-1；假设当假设当假设当假设当n=k-1n=k-1时命题成立，有时命题成立，有时命题成立，有时命题成立，有k-1k-1个顶点，有个顶点，有个顶点，有个顶点，有k-2k-2条边。条边。条边。条边。b bf fe
38、ed duvT(2)T无圈，且无圈，且无圈，且无圈，且m=n-1m=n-1T1eu51第51页，共56页，编辑于2022年，星期三证明：证明：(1)T T是一棵树是一棵树是一棵树是一棵树当当当当n=kn=k时，时，时，时，T是连通且无圈，是连通且无圈，k个顶点至少有个顶点至少有1个点次为个点次为1.设点设点u，为悬挂点，边，为悬挂点，边e=(u,v);从从T中去掉边中去掉边e和点和点u不会影响不会影响T的连通，得到的连通，得到T1:T1为树只有为树只有k-1个顶点，有个顶点，有k-2条边，再把条边，再把e=(u,v)点点u加上去，可知当加上去，可知当T有有k 个顶点时有个顶点时有k-1条边。条
39、边。b bf fe ed duvT(2)T无圈，且无圈，且m=n-1T1eu52第52页，共56页，编辑于2022年，星期三证明：（证明：（证明：（证明：（2 2 2 2）T T T T无圈，且无圈，且无圈，且无圈，且m=n-1m=n-1m=n-1m=n-1（3 3 3 3）T T T T连通，且连通，且连通，且连通，且m=n-1m=n-1m=n-1m=n-1只需要只需要T证明是连通的。证明是连通的。反证法：反证法：假设假设T不是连通的，可以分为不是连通的，可以分为L个连通子图个连通子图(L2)，设第，设第i个子图有个子图有ni个顶点，个顶点，因为第因为第i个连通子图是树，所以有个连通子图是树
40、，所以有ni-1条边，条边，L个子图共有边数为：个子图共有边数为：与已知矛盾。所以与已知矛盾。所以T是连通图。是连通图。53第53页，共56页，编辑于2022年，星期三先证明先证明T无圈。无圈。假设假设T T中有圈，设为中有圈，设为C,C,可以去掉可以去掉C C中的一条边，并不影响中的一条边，并不影响T T的连通性。如果剩的连通性。如果剩余图中仍有圈，可继续去掉一条边余图中仍有圈，可继续去掉一条边，像这，像这样去掉样去掉p p条边条边(p1)(p1)后得到一个没有圈的连后得到一个没有圈的连通图通图T T1 1，T T1 1显然有显然有n-1-pn-1-p（5-1-2=25-1-2=2）条边。）
41、条边。但但T T1 1为树，顶点个数又与为树，顶点个数又与T T相同为相同为n n个，个，所以所以T T1 1应应该有该有n-1n-1（5-1=45-1=4）条边，矛盾，所以）条边，矛盾，所以T T中无圈。中无圈。由于由于T T连通且无圈连通且无圈,两点之间必有一条唯一的两点之间必有一条唯一的链，否则会出现圈，所以，链，否则会出现圈，所以，T+(u,v)T+(u,v)出现唯一出现唯一的一个圈。的一个圈。证明证明证明证明:（3 3 3 3）T T T T连通，且连通，且连通，且连通，且m=n-1m=n-1m=n-1m=n-1（4 4 4 4）T T T T无圈，但任加一新边得到唯一一个圈无圈，但
42、任加一新边得到唯一一个圈无圈，但任加一新边得到唯一一个圈无圈，但任加一新边得到唯一一个圈b bf fe ed dT圈圈cT154第54页，共56页，编辑于2022年，星期三证明：（证明：（证明：（证明：（4 4 4 4）T T T T无圈，但任加一新边得到唯一一个圈无圈，但任加一新边得到唯一一个圈无圈，但任加一新边得到唯一一个圈无圈，但任加一新边得到唯一一个圈（5 5 5 5）T T T T连通，但任舍去一边就不连通连通，但任舍去一边就不连通连通，但任舍去一边就不连通连通，但任舍去一边就不连通先证明先证明T连通。连通。如果如果T不连通，由定义至不连通，由定义至少存在少存在2点点u,w之间无路可
43、通，则加上一之间无路可通，则加上一边边(u,w)也不会形成圈，与也不会形成圈，与已知已知T无圈无圈无圈无圈矛矛盾盾。再证明每舍去一边便不连通。再证明每舍去一边便不连通。如果如果T中有中有一边一边(u,v),舍去一边舍去一边(u,v)后图后图T-(u,v)仍然仍然连通，那么连通，那么T1=T-(u,v)由于没有圈是一个树，但由于没有圈是一个树，但T1加加一边后一边后(u,v)就是就是T仍无圈，与（仍无圈，与（4）中的）中的树树每加一新边必出现唯一圈矛盾每加一新边必出现唯一圈矛盾。b bf fe ed dTT1uwv55第55页，共56页，编辑于2022年，星期三证明（证明（5 5 5 5）T T
44、连通，但任舍去一边就不连通连通，但任舍去一边就不连通连通，但任舍去一边就不连通连通，但任舍去一边就不连通（6 6 6 6）T T T T任意两点，有唯一链相连任意两点，有唯一链相连根据根据T T连通，得到连通，得到连通，得到连通，得到T T中任意两点之间至少一条链相连；根中任意两点之间至少一条链相连；根据条件（据条件（5 5）：）：）：）：T连通，但任舍去一边就不连通，说明连通，但任舍去一边就不连通，说明T任意两点，有唯一链相连。任意两点，有唯一链相连。任意两点，有唯一链相连。任意两点，有唯一链相连。证明：（证明：（证明：（证明：（6 6 6 6）T T任意两点，有唯一链相连任意两点，有唯一链相连任意两点，有唯一链相连任意两点，有唯一链相连（1 1）T T是一棵树是一棵树是一棵树是一棵树树的定义：无圈且连通，得到证明。树的定义：无圈且连通，得到证明。56第56页，共56页，编辑于2022年，星期三