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