第8章图与网络分析.pptx

《第8章图与网络分析.pptx》由会员分享，可在线阅读，更多相关《第8章图与网络分析.pptx（213页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1页/共213页第2页/共213页第3页/共213页 在在实实际际的的生生产产和和生生活活中中，人人们们为为了了反反映映事事物物之之间间的的关关系系，常常常常在在纸纸上上用用点点和和线线来来画画出出各各式式各各样样的的示示意图。意图。引例引例2 2左图是我国北京、上海、重庆等十四个城市左图是我国北京、上海、重庆等十四个城市之间的铁路交通图，这里用之间的铁路交通图，这里用点表示城市，用点表示城市，用点与点之间的线表示城市之间的铁路线点与点之间的线表示城市之间的铁路线。诸。诸如此类还有城市中的市政管道图，民用航空如此类还有城市中的市政管道图，民用航空线图等等。线图等等。连云港连云港武汉武汉南京南

2、京徐州徐州上海上海北京北京塘沽塘沽青岛青岛济南济南天津天津郑州郑州第4页/共213页 有有六六支支球球队队进进行行足足球球比比赛赛，我我们们分分别别用用点点v1v6 6表表示示这这六六支支球球队队，它它们们之之间间的的比比赛赛情情况况，也也可可以以用用图图反反映映出出来来，已已知知v1 1队队战战胜胜v2 2队队，v2 2队队战战胜胜v3 3队队，v3 3队队战战胜胜v5 5队队，如如此此等等等等。这这个个胜胜负负情况，可以用下图所示的情况，可以用下图所示的有向图有向图反映出来。反映出来。引例引例3 3v3v1v2v4v6v5第5页/共213页图的基本概念与模型图的基本概念与模型点：点：研究对

3、象（车站、国家、球队）；研究对象（车站、国家、球队）；点间连线：点间连线：对象之间的特定关系（陆地间有桥、铁对象之间的特定关系（陆地间有桥、铁路线、两球队比赛及结果路线、两球队比赛及结果)。对称关系：对称关系：桥、道路、边界；用不带箭头的连线表桥、道路、边界；用不带箭头的连线表 示，称为边。示，称为边。非对称关系：非对称关系：甲队胜乙队，用带箭头的连线表示，甲队胜乙队，用带箭头的连线表示，称为弧。称为弧。图：图：点及边（或弧）组成。点及边（或弧）组成。注意：注意：一般情况下，图中的相对位置如何，点与点之间线的长短曲直，对于反一般情况下，图中的相对位置如何，点与点之间线的长短曲直，对于反映研究对

4、象之间的关系，显的并不重要，因此，图论中的图与几何图，工程图映研究对象之间的关系，显的并不重要，因此，图论中的图与几何图，工程图等本质上不同。等本质上不同。第6页/共213页一、图与网络的基本知识一、图与网络的基本知识（一）（一）图与网络的基本概念图与网络的基本概念 EADCB 1、一个、一个图图是由是由点和连线点和连线组成。（连线可带箭头，也组成。（连线可带箭头，也可不带，前者叫可不带，前者叫弧弧，后者叫，后者叫边边）第7页/共213页一一个个图图是是由由点点集集 和和 中中元元素素的的无无序序对对的的集集合合 构构成成的的二二元元组组，记记为为G G=(=(V V，E E)，其其中中 V

5、V 中中的的元元素素 叫叫做做顶顶点点，V 表表示示图图 G 的的点点集集合合；E 中中的的元素元素 叫做叫做边边，E 表示图表示图 G 的边集合。的边集合。v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10例例图图1第8页/共213页 2 2、如如果果一一个个图图是是由由点点和和边边所所构构成成的的，则则称称其其为为无无向向图图，记记作作G G=(V V，E E)，连连接接点点的的边边记记作作 v vi i ,v vj j，或或者者 v vj j ,v vi i。3 3、如果一个、如果一个图是由点和弧所构成图是由点和弧所构成的，那么称它为的，那么称它为有有向图向图，记作，记作

6、D D=(=(V,AV,A)，其中其中V V 表示有向图表示有向图D D 的点集合，的点集合，A A 表表示有向图示有向图D D 的弧集合。一条方向从的弧集合。一条方向从v vi i指向指向v vj j 的弧，记作的弧，记作(v vi i ,v,vj j)。v4v6v1v2v3v5V=v1,v2,v3,v4,v5,v6，A=(v1,v3),(v2,v1),(v2,v3),(v2,v5),(v3,v5),(v4,v5),(v5,v4),(v5,v6)图图2第9页/共213页5 5、如果两个端点之间有两条、如果两个端点之间有两条 以上的边，称为以上的边，称为多重边多重边。6 6、一个无环、无多重边

7、的图称为、一个无环、无多重边的图称为简单图简单图，含有多重边的图称为含有多重边的图称为多重图多重图。7、无向完全图无向完全图每一对顶点间都有边相连的简单图；每一对顶点间都有边相连的简单图；有向完全图有向完全图指每一对顶点之间有且仅有一条有指每一对顶点之间有且仅有一条有向边的简单图。向边的简单图。4 4、一条边的两个端点是相同的、一条边的两个端点是相同的,称此边为称此边为环环。v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10第10页/共213页v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10 次为零的点次为零的点弧立点弧立点 8 8、以点、以点v v为端点的边

8、的个数称为点为端点的边的个数称为点v v 的的次，记作次，记作图中图中 d(v1)=4，d(v6)=4（环计两次环计两次）次为偶数的点次为偶数的点偶点偶点次为次为1 1的点的点悬挂点悬挂点悬挂点的关联边悬挂点的关联边悬挂边悬挂边次为奇数的点次为奇数的点奇点奇点v7第11页/共213页 定理定理1 1 任何图中，顶点次数的总和等于边数的任何图中，顶点次数的总和等于边数的2 2倍。倍。所有顶点的入次之和等于所有顶点的出次之和。所有顶点的入次之和等于所有顶点的出次之和。有向图中：有向图中：l以以v vi i 为始点的边数称为点为始点的边数称为点v vi i 的出次，用的出次，用 表示；表示；l以以v

9、 vi i 为终点的边数称为点为终点的边数称为点v vi i 的入次，用的入次，用 表示；表示；v vi i 点的出次和入次之和就是该点的次点的出次和入次之和就是该点的次。定理定理2 2 在任一图中，奇点的个数必为偶数。在任一图中，奇点的个数必为偶数。第12页/共213页 一个称为始点（或发点），记作一个称为始点（或发点），记作v1，一个称为终点（或收点），记作一个称为终点（或收点），记作vn，其余的点称为中间点。其余的点称为中间点。9 9、在实际应用中，给定一个图、在实际应用中，给定一个图G=G=（V V，E E）或有向图）或有向图 D=D=（V V，A A），在），在V V中指定两个点中指

10、定两个点:对每一条弧对每一条弧 ，对应一个数，对应一个数 ，称为弧上的，称为弧上的“权权”。通常把这种。通常把这种赋权的图赋权的图称为称为网络网络。第13页/共213页e3v1v2v3v4v5v6e7e8e1e2e4e5e6e9e10若链中所含的边均不相同，称为若链中所含的边均不相同，称为简单链简单链所含的点均不相同的链称为所含的点均不相同的链称为初等链初等链 ,也称通路。也称通路。1010、由两两相邻的点及其相关联的边构成的点边序列、由两两相邻的点及其相关联的边构成的点边序列称为称为链链。第14页/共213页图的连通性图的连通性链：链：设图设图G=G=（V V，E E）中有一个点、边交替序）

11、中有一个点、边交替序列列 v v1 1,e,e1 1,v,v2 2,v vn-1n-1,e,en-1n-1,v,vn n，若，若e ei i=(v vi i,v,vi+1i+1)，即这，即这(n-1n-1)条边把条边把n n个顶点串个顶点串连起来连起来，我们称这个交替序列为图，我们称这个交替序列为图G G中的一中的一条链，而称点条链，而称点v v1 1,v,vn n为该链的两个端点。为该链的两个端点。对于简单图链也可以仅用点的序列来表示。如果一条链的如果一条链的两个端点是同一个点两个端点是同一个点，则称它为，则称它为闭链或圈闭链或圈；如果一条链的如果一条链的各边均不相同各边均不相同，则称此链为

12、，则称此链为简单链简单链；更若一条链的更若一条链的各点、各边均不相同各点、各边均不相同，则称该链为，则称该链为初等链初等链。v1v3v5e1e2v7v8e7v2v4v6e3e4e5e6e8e9简单链简单链：1=（v2，v1，v3，v6，v4，v3，v5）初等链初等链：2=（v2，v1，v3，v5）第15页/共213页图的连通性图的连通性最短链最短链:网络中链上权值的和称为链的长度，网络中链上权值的和称为链的长度，以点以点v v1 1,v,vn n为端点的诸链中长度最短的链为端点的诸链中长度最短的链称为这两点的最短链。称为这两点的最短链。连通图：连通图：如果图如果图G=G=（V V，E E）中的

13、）中的任意任意两点都两点都是其某一条链的两个端点，则称图是其某一条链的两个端点，则称图G G是连是连通图，否则，称图通图，否则，称图G G是不连通的。是不连通的。v1v3v5e1e2v7v8e7v2v4v6e3e4e5e6e8e9为不连通图，有两为不连通图，有两个连通分图组成个连通分图组成 11 11、图中任意两点之间均至少有一条通路，则称此图、图中任意两点之间均至少有一条通路，则称此图 为为连通图连通图，否则称为，否则称为不连通图不连通图。第16页/共213页v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)e5e7v1v2v5v6v7e1e6e8(b)子图子

14、图v1v2v3v4v5v6v7e1e6e7e9e10e11(c)支撑子图支撑子图第17页/共213页第18页/共213页e3v1v2v3v4v5v6e7e8e1e2e4e5e6e9e10图图3 3 3 3一个图中任意两点间至少有一条链相连，则称此图一个图中任意两点间至少有一条链相连，则称此图为连通图。任何一个不连通图都可以分为若干个连为连通图。任何一个不连通图都可以分为若干个连通子图，每一个子图称为原图的一个分图。通子图，每一个子图称为原图的一个分图。v4v6v1v2v3v5e e2 2e e1 1e e3 3e e4 4e e5 5e e6 6e e7 7e e8 8e e9 9e e101

15、0图图4 4 4 4第19页/共213页 对于网络（赋权图）对于网络（赋权图）G=（V，E），其中边，其中边有权有权 ，构造矩阵，构造矩阵 ，其中：，其中：设图设图G=（V，E）中顶点的个数为中顶点的个数为n，构造一个，构造一个 矩阵矩阵 ，其中：，其中：（二）图的矩阵表示（二）图的矩阵表示称称矩阵矩阵A A为网络为网络G的的权矩阵权矩阵 称称矩阵矩阵A A为网络为网络G的的邻接矩阵邻接矩阵 第20页/共213页例例权矩阵权矩阵邻接矩阵邻接矩阵v5v1v2v3v4v64332256437第21页/共213页 思考：思考：有甲、乙、丙、丁、戊、己六名运动员报名参加有甲、乙、丙、丁、戊、己六名运动

16、员报名参加A A、B B、C C、D D、E E、F F六个项目的比赛，下表中打的是个运动员报名参加比赛的项目，问六个项目的比赛六个项目的比赛，下表中打的是个运动员报名参加比赛的项目，问六个项目的比赛顺序应如何安排？做到每名运动员都不连续地参加两项比赛。顺序应如何安排？做到每名运动员都不连续地参加两项比赛。ABCDEF分析分析：点表示项目，边表示两个项目有同一名运动员参加：点表示项目，边表示两个项目有同一名运动员参加目的目的：在图中找出点序列，：在图中找出点序列，使得依次排列的两个点不使得依次排列的两个点不相邻，就找到了每名运动相邻，就找到了每名运动员不连续参加两项比赛的员不连续参加两项比赛的

17、安排方案安排方案A、C、B、F、E、D(不唯一不唯一)第22页/共213页二二、中国邮递员问题中国邮递员问题 一、欧拉回路与道路一、欧拉回路与道路定定义义 连连通通图图G中中，若若存存在在一一条条道道路路，经经过过每每边边一一次次且且仅仅一一次次，则则称称这这条条路路为为欧欧拉拉道道路路。若若存存在在一一条条回回路路，经经过过每每边边一一次次且且仅仅一一次次，则则称称这这条条回回路为路为欧拉回路欧拉回路。推论推论 一个多重连通图一个多重连通图G有欧拉道路的充分必要条有欧拉道路的充分必要条件是件是G有且仅有两个奇点。有且仅有两个奇点。具有欧拉回路的图称为具有欧拉回路的图称为欧拉图欧拉图。定理定理

18、 一个多重连通图一个多重连通图G是欧拉图的充分必要条件是欧拉图的充分必要条件是是G中无奇点。中无奇点。第23页/共213页u一个邮递员，负责某一地区的信件投递。他每天要一个邮递员，负责某一地区的信件投递。他每天要从邮局出发，走遍该地区所有街道再返回邮局，问从邮局出发，走遍该地区所有街道再返回邮局，问应如何安排送信的路线可以使所走的总路程最短？应如何安排送信的路线可以使所走的总路程最短？u图论语言描述：给定一个连通图图论语言描述：给定一个连通图G，每边有非负权，每边有非负权l(e)，要求一条回路过每边至少一次，且满足总权最小。，要求一条回路过每边至少一次，且满足总权最小。二、中国邮路问题二、中国

19、邮路问题l中国邮路问题可转化为如下问题：中国邮路问题可转化为如下问题：在连通图在连通图G=(V,E)中，求一个边集中，求一个边集E1 E ，把，把G中属中属于于E E1 1的边均变为两重边得到图的边均变为两重边得到图G*=G+E1，使其满足，使其满足G*无奇点，且无奇点，且 最小。最小。第24页/共213页u奇偶点图上作业法奇偶点图上作业法（1 1）每条边最多重复一次；）每条边最多重复一次；（2 2）对图）对图G G中每个初等圈来讲，重复边的中每个初等圈来讲，重复边的长度和不超过圈长的一半。长度和不超过圈长的一半。v定理定理：已知图：已知图G*=G+E1无奇点，则无奇点，则最小的充分必要条件为

20、最小的充分必要条件为：第25页/共213页（1 1）找找出出图图G中中的的所所有有的的奇奇顶顶点点，把把它它们们两两两两配配成成对对，而而每每对对奇奇点点之之间间必必有有一一条条通通路路，把把这这条条通通路路上上的的所所有有边边作作为为重重复复边边追追加加到到图图中中去去，这这样样得得到到的的新连通图必无奇点。新连通图必无奇点。（2 2）如果边）如果边e=（u,v）上的重复边多于一条，则上的重复边多于一条，则可从重复边中去掉偶数条，使得其重复边至多为一可从重复边中去掉偶数条，使得其重复边至多为一条，图中的顶点仍全部都是偶顶点。条，图中的顶点仍全部都是偶顶点。（3 3）检查图中的每一个圈，如果每

21、一个圈的重复）检查图中的每一个圈，如果每一个圈的重复边的总长不大于该圈总长的一半，则已经求得最优边的总长不大于该圈总长的一半，则已经求得最优方案。如果存在一个圈，重复边的总长大于该圈总方案。如果存在一个圈，重复边的总长大于该圈总长的一半时，则将这个圈中的重复边去掉，再将该长的一半时，则将这个圈中的重复边去掉，再将该圈中原来没有重复边的各边加上重复边，其它各圈圈中原来没有重复边的各边加上重复边，其它各圈的边不变，返回步骤（的边不变，返回步骤（2 2）。）。u奇偶点图上作业法奇偶点图上作业法第26页/共213页 判判定定标标准准1 1:在在最最优优邮邮递递路路线线上上，图图中中的的每每一一条条边边

22、至多有一条重复边。至多有一条重复边。判判定定标标准准2 2 :在在最最优优邮邮递递路路线线上上，图图中中每每一一个个圈圈的重复边总权小于或等于该圈总权的一半。的重复边总权小于或等于该圈总权的一半。例：求解下图所示网络的中国邮路问题，图中数字为例：求解下图所示网络的中国邮路问题，图中数字为该边的长。该边的长。v1v2v3v4v5v6v7v8v9243449556434第27页/共213页v1v2v3v4v5v6v7v8v9243449643455v1v2v3v4v5v6v7v8v9243449556434v1v2v3v4v5v6v7v8v9243449556434v1v2v3v4v5v6v7v8

23、v9243449556434l12+2 l23+2 l36+l89+2 l78+l69+l14+2 l47=51 第28页/共213页v1v2v3v4v5v6v7v8v9243449556434第29页/共213页树：不含圈的连通图五个城市连通电话线问题n什么是连通图：任意两点之间都有一条链相连。n什么是圈：起点和终点相同的链叫做圈。已知有五个城市，要在它们之间架设电话线，要求任何两个城市都可以互相通话（允许通过其它城市），并且电话线的根数最少。二、树的基本概念第30页/共213页树的基本性质任意两点之间有且只有一条链；图是树的充要条件：任意两个顶点之间只有一条链；若树有p个顶点，则共有q=p

24、-1条边；图是树的充要条件：连通图，边数=顶点数1。五个城市连通电话线问题第31页/共213页树树村庄1村庄4村庄3村庄6村庄2村庄5村庄7如果如果G=G=（V V，E E）是一个无圈的连通图，则称）是一个无圈的连通图，则称G G为为树树。树中必存在次为树中必存在次为1 1的点（悬挂点）的点（悬挂点）树中任两点必有一条链且仅有一条链；树中任两点必有一条链且仅有一条链；在树的两个不相邻的点之间添加一条边，就得到一个圈；在树的两个不相邻的点之间添加一条边，就得到一个圈；反之，去掉树的任一条边，树就成为不连通图；反之，去掉树的任一条边，树就成为不连通图；n n个顶点的树有（个顶点的树有（n-1n-1

25、）条边。）条边。树是无圈连通图中边数最多的，也是最脆弱的连通图！树是无圈连通图中边数最多的，也是最脆弱的连通图！第32页/共213页1 1、连通且不含圈的无向图称为树。、连通且不含圈的无向图称为树。树中次为树中次为1 1的点称为树叶，次大于的点称为树叶，次大于1 1的点称为分支点。的点称为分支点。第33页/共213页任何树图中必存在次为任何树图中必存在次为1的点的点.证明：证明：用反证法用反证法.假设树图中不存在次为假设树图中不存在次为1的点的点.又连通图中不存在孤立点，故树图中所有顶点的次又连通图中不存在孤立点，故树图中所有顶点的次2.又可知与又可知与v2,v3关联的边的其他端点关联的边的其

26、他端点v4,v5，同样同样d(v4)2,d(v5)2，可继续一可继续一直往下推。直往下推。而图的顶点的总数是有限的，故最后必然回到前面的而图的顶点的总数是有限的，故最后必然回到前面的某一顶点，于是在图中出现了圈，这与树的定义产生了矛某一顶点，于是在图中出现了圈，这与树的定义产生了矛盾盾.v1v2v3v4v5 不妨设不妨设d(v1)=2,既既v1有两条关联边，有两条关联边，设关联边的其他两个端点为设关联边的其他两个端点为v2,v3，而，而d(v2)2,d(v3)2，悬挂点悬挂点悬挂边悬挂边第34页/共213页第35页/共213页第36页/共213页第37页/共213页一个图一个图G 有生成树的充

27、要条件是有生成树的充要条件是G 是连通图。是连通图。v1v2v3v4v5v1v2v3v4v5第38页/共213页145241575237图的部分树（支撑树）图的部分树（支撑树）如果图如果图G=G=（V V，E E）的部分图）的部分图G G=（V V，E E）是树，）是树，则称则称G G是是G G的的部分树（或支撑树）部分树（或支撑树）。村庄1村庄4村庄3村庄6村庄2村庄5村庄7部分树上各树枝上权值的和称为它的长度，其中长度部分树上各树枝上权值的和称为它的长度，其中长度最短的部分树，称其为该图的最短的部分树，称其为该图的最小部分树最小部分树（最小支撑（最小支撑树）。树）。点保留点保留边可去边可去

28、仍是树仍是树不唯一不唯一思考：如何铺设电话线，使得思考：如何铺设电话线，使得电话线长度最少？电话线长度最少？第39页/共213页定义 树、生成树：无圈的连通图称为树；若G1是G2的一个支撑子图并且是一棵树，则称G1是G2的一棵生成树。图83(a)是一棵树，图83(b)是图81的一棵生成树。v3e7e4e8e5e6e1e2e3v1v2v4v5v1v1图81图83(a)图83(b)v3e2e3v2v5v3e7e8e6e2v2v4v5第40页/共213页定理：图G=（V，E）有生成树的充分必要条件为G是连通图。v3e7e4e8e5e6e1e2e3v1v2v4v5第41页/共213页生成树的寻求方法在

29、图中，每步选出一条边使它与已选边不构成圈，直到选够n-1 条边为止。（）深探法步骤：任取一点v，给v以标号；若某点u已得标号i，检查其端点w是否已标号；若端点w未标号，则给w以标号i+1;重复 若端点均已标号，则退到标号i1的点，重复。第42页/共213页(2)广探法任取一点v，给v以标号；检查其所有端点wi是否已标号；若端点w未标号，则给所有wi以标号i+1;对标号i+1的点重复。01112212223334第43页/共213页（3）破圈法在图中任意取一个圈，从圈上任意舍弃一条边，将这个圈破掉；重复上述步骤，直到图中没有圈为止。v1v2v3v4v5v6v7v8v0v1v2v3v4v5v6v7

30、v8v0例：某乡有9个自然村，其乡间道路如下图，要求：以v0村为中心沿道路架设有线广播网络，应如何架设？第44页/共213页7 7个村庄要在他们之间架设电话线，要求任何两个村庄都可以互相通电话个村庄要在他们之间架设电话线，要求任何两个村庄都可以互相通电话(允许允许中转中转)，并且，并且电话线根数最少电话线根数最少？引例引例村庄1村庄4村庄3村庄6村庄2村庄5村庄7分析分析：用七个点代表村庄，如果在某两个村庄之间架设电：用七个点代表村庄，如果在某两个村庄之间架设电话线，则相应的在两点之间连一条边，这样电话线网就可话线，则相应的在两点之间连一条边，这样电话线网就可以用一个图来表示，并且满足如下要求

31、：以用一个图来表示，并且满足如下要求：连通图连通图图中有圈的话，从圈中任去掉一条边，余下的图仍连通图中有圈的话，从圈中任去掉一条边，余下的图仍连通为什么？为什么？第45页/共213页第46页/共213页求最小树的方法：求最小树的方法：一、破圈法：在给定连通图一、破圈法：在给定连通图G G G G中，任取一圈，去掉一条中，任取一圈，去掉一条最大权边（若有两条或两条以上的权均是最大权边，则最大权边（若有两条或两条以上的权均是最大权边，则任意去掉其中一条），在余图中任取一圈，去掉一条最任意去掉其中一条），在余图中任取一圈，去掉一条最大权边，重复下去，直到余图中无圈为止，即得到图大权边，重复下去，直到

32、余图中无圈为止，即得到图G G G G的最小树。的最小树。二、避圈法：在给定连通图二、避圈法：在给定连通图G G G G中，任取权值最小的一条中，任取权值最小的一条边，在未选边中选一条权值最小的边，要求所选边与已边，在未选边中选一条权值最小的边，要求所选边与已选边不构成圈，重复下去，直到不存在与已选边不构成选边不构成圈，重复下去，直到不存在与已选边不构成圈的边为止，已选边与顶点构成的图圈的边为止，已选边与顶点构成的图T T T T即为所求的最小即为所求的最小树。树。第47页/共213页最小树的应用：电信网络（计算机网络、电话专用线网络、有线电视网络等等）的设计 低负荷运输网络的设计，使得网络中

33、提供链接的部分（如铁路、公路等 等）的总成本最小 高压输电线路网络的设计电器设备线路网络（如数字计算机系统）的设计，使得线路总长度最短 连接多个场所的管道网络设计 求最小树是在一个无向连通图G中求一棵最小生成树。第48页/共213页v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636方法一：破圈法方法一：破圈法步骤：步骤：1、先任取一个圈，从圈中去掉一条权最大的边，若在同一个圈中有几条都是权最、先任取一个圈，从圈中去掉一条权最大的边，若在同一个圈中有几条都是权最大边，则任选其中的一条边去掉。大边，则任选

34、其中的一条边去掉。2、在余下的子图中，重复上述步骤，直至没有圈为止。、在余下的子图中，重复上述步骤，直至没有圈为止。第49页/共213页v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636第50页/共213页v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 12323第51页/共213页v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 12323第52页

35、/共213页v1v1v7v7v4v4v3v3v2v2v5v5v6v615159 9161625253 3282817174 41 12323第53页/共213页v1v1v7v7v4v4v3v3v2v2v5v5v6v615159 9161625253 3282817174 41 12323第54页/共213页v1v1v7v7v4v4v3v3v2v2v5v5v6v69 925253 3282817174 41 12323第55页/共213页v1v1v7v7v4v4v3v3v2v2v5v5v6v69 925253 3282817174 41 12323第56页/共213页v1v1v7v7v4v4v3

36、v3v2v2v5v5v6v69 93 3282817174 41 12323第57页/共213页v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 3282817174 41 12323第58页/共213页v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 317174 41 12323总权数总权数=1+4+9+3+17+23=57=1+4+9+3+17+23=57第59页/共213页v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636方法二：避圈法方法二：避圈法避圈法：开始

37、选一条最小权的边，在以后的每一步中，避圈法：开始选一条最小权的边，在以后的每一步中，总从未被选取的边中选一条权最小的边，并使之与已总从未被选取的边中选一条权最小的边，并使之与已选取的边不构成圈，如果同时有几条都是最小权的边，选取的边不构成圈，如果同时有几条都是最小权的边，则可从中任选一条。则可从中任选一条。第60页/共213页v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636第61页/共213页v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 32828

38、17174 41 123233636第62页/共213页v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636第63页/共213页v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636第64页/共213页v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636总权数总权数=1+4+9+3+17+23=57=1+4+9+3+17+2

39、3=57第65页/共213页v1v2v3v4v514231352破圈法求最小树：破圈法求最小树：v1v2v3v4v514231352第66页/共213页v1v2v3v4v514231352避圈法求最小树：避圈法求最小树：v1v2v3v4v514231352第67页/共213页5v1v2v3v4v5v6843752618图61例例 用破圈法求图用破圈法求图6 61 1的最小树。的最小树。图62图图6 62 2就是图就是图6 61 1的最小部分树，最小树长为的最小部分树，最小树长为 w(T)=4+3+5+2+1=15w(T)=4+3+5+2+1=15。当一个圈中有多个相同的最长边时，不能同时都去掉

40、，只能去掉其中任意一条边。当一个圈中有多个相同的最长边时，不能同时都去掉，只能去掉其中任意一条边。最小部分树有可能不唯一，但最小树的长度相同最小部分树有可能不唯一，但最小树的长度相同 第68页/共213页（2 2）避圈法：取图）避圈法：取图G G的的n n个孤立点个孤立点v v1 1，v v2 2，v vn n 作为作为一个支撑图，从最短边开始往支撑图中添加，见圈回避，一个支撑图，从最短边开始往支撑图中添加，见圈回避，直到连通（有直到连通（有n n1 1条边）条边）v1v2v3v4v5v643521图63在图在图6 63 3中，如果添加边中，如果添加边 v v1 1,v v2 2 就形成圈就形

41、成圈v v1 1,v v2 2,v v4 4，这时就应避开添加边这时就应避开添加边 v v1 1,v v2 2，添加下一条最短边，添加下一条最短边 v v3 3,v v6 6。破圈法和避圈法得到树的形状可能不一样，但最小树的。破圈法和避圈法得到树的形状可能不一样，但最小树的长度相等长度相等 5v1v3v515v2v4v684375268Min w(T)=15第69页/共213页最小生成树解法1（Kruskal算法）避圈法：这种方法每步从图中挑选一条边，满足：（1）它与已经选出的边不构成圈；（2）它是满足条件（1）的权最小的边，直到选够n-1条边为止。1412131445532452141213

42、14455324529个顶点，8条边第70页/共213页避圈法另一种表述先去掉图G的所有边，只留下顶点，每次放回一条权最小的边，使之与已经放回的边不构成圈，反复进行，直到有（n-1）条边为止。9482333791423316个顶点，5条边第71页/共213页最小生成树解法（2）破圈法：这种方法每步从图中任选一个圈，然后去掉该圈中权最大的边，直到图中没有圈为止。14121314455324529个顶点，8条边第72页/共213页破圈法举例948233379194823337916个顶点，5条边第73页/共213页破圈法举例破圈法举例v4v2v3v16215846最小生成树最小生成树的权的权=9/

43、v4v2v3v1621546v4v2v3v162154/v4v2v3v16214/v4v2v3v1621第74页/共213页例：例：分别用避圈法和破圈法求下图的最小部分树分别用避圈法和破圈法求下图的最小部分树.ABCDFE1632445231.避圈法避圈法ABCDFE1632244523VABCDFE163244523ABCDFE163244523ABCDFE163244523ABCDFE163244523ABCDFE163244523第75页/共213页分别用避圈法和破圈法求下图的最小部分树分别用避圈法和破圈法求下图的最小部分树.ABCDFE1632445232.破圈法破圈法ABCDFE13

44、244523ABCDFE1324423ABCDFE132423ABCDFE13242第76页/共213页避圈法（加边法）：去掉G中所有边，得到n个孤立点；然后加边；加边的原则：从最短边开始添加，加边的过程中不能形成圈，直到连通（n1条边）。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521Min C(T)=15求最小树的方法：避圈法和破圈法 第77页/共213页破圈法：任取一圈，去掉圈中最长边，直到无圈。v1v2v3v4v5v6435215v1v2v3v4v5v6843752618第78页/共213页v1v2v3v4v5v643521得到最小树：Min C(T)=1

45、5第79页/共213页(3)矩阵求解算法 步骤1：构造一个矩阵，651572344v1v2v3v4v5v6第80页/共213页T651572344v1v2v3v4v5v6第81页/共213页步骤2：从矩阵中任一行开始，用T表明节点入树，划去该节点所在的列。T第82页/共213页步骤3：在标T的行中选取最小元素，用方框表示，将对应的边入树，将新得到节点标T，划去所在列。TT第83页/共213页步骤4：重复步骤3。TTT第84页/共213页矩阵计算方法TTTT第85页/共213页矩阵计算方法TTTTT第86页/共213页矩阵计算方法TTTTTT第87页/共213页矩阵计算结果第88页/共213页6

46、83572348第89页/共213页根树及其应用定义 有向树：若一个有向图是一棵树，则称这个有向图为有向树。定义 若有向树T恰有一个结点的入次为0，其余各点入次均为1，则称T为根树。v1v2v3v4v5v6v7v8v9v10v11第90页/共213页v1v2v3v4v5v6v7v8v9v10v11入次为0的点，称为根出次为0的点，称为叶其它顶点，称为分枝点根到某顶点vi的道路长度，称为vi点的层次。第91页/共213页定义 在根树T中，若每个顶点的出次小于或等于m，则称T为m叉树。若每个顶点的出次恰好等于m或零，则称T为完全m叉树。v1v2v3v4v5v6v7v8v9v10v11当m=2时，称

47、为二叉树、完全二叉树。v1v2v3v4v5v6v7第92页/共213页记二叉树各叶子的权为pi，根到各叶子的距离（层次）为 li二叉树的总权数：v1v2v3v4v5v6v7最优二叉树：满足总权最小的二叉树称为最优二叉树。霍夫曼（D A Huffman)给出了一个求最优二叉树的算法，又称霍夫曼树。第93页/共213页例1、s=6，其权分别为4，3，2，2，1，求最优二叉树。123243365第94页/共213页例1、s=6，其权分别为4，3，2，2，1，求最优二叉树。123243396515123243396515第95页/共213页例：最优检索问题用计算机进行图书分类。现有五类图书共100万册

48、，其中有A类50万册，有B类20万册，C类5万册，D类10万册，E类15万册。问如何安排分检过程，可使总的运算次数最小？算法步骤：1.将s个叶子按权由小至大排序；2.将二个具有最小权的叶子合并成一个分枝点，其权为p1+p2；将新的分枝点作为一个叶子，合并，第96页/共213页解：构造一棵具有5个叶子的最优二叉树，其叶子的权分别为50，20，5，10，15.步骤如下：1.将5个叶子按权由小到大排序：5，10，15，20，50 2.找出二个最小权的叶子，合并成一个分枝点，其权为15；依次，继续。103015205050100总权为：5151234第97页/共213页分检过程是：先把A类50万册从总

49、数中分检出来，其次将B类20万册分检出来，然后再将E类15万册分检出来，最后再将D、C分检出来。AABBEEDCDNYNYNYNY第98页/共213页例3：P235、例110.050.450.050.080.120.25一等品五等品四等品三等品二等品等外品0.100.300.180.551.0测试顺序第99页/共213页v典例:会议日程安排某单位要在今后的三天内召开6个会议,每天上下午各安排一个会议，参加会议的领导如下会议A:朱、马、牛、姬、江、姚会议B:朱、杨、张、江会议C:马、姬、侯、王、姚会议D:朱、姬、张会议E:杨、侯、王会议F:刘、杨、王、江、姚第100页/共213页每位领导每天最多

50、只参加一个会议。会议A要安排在第一天上午,会议F安排在第三天下午，会议B要安排在任何一天的下午。试根据上述要求排出一个会议日程表，使各位领导都能参加相应的会议第101页/共213页ABCDEF会议日程安排如下:上午 下午第一天 会议A E 第二天 会议C B第三天 会议D F 解:用节点表示会议，若两个会议能安排在一天，则用连线连接。第102页/共213页 10名学生参加名学生参加 6 门考试，每人每天最多考门考试，每人每天最多考 1 门，门，A 必须第必须第1天上午，天上午，F最后考，最后考，B安排在下午，三天结束。安排在下午，三天结束。学生学生学生学生 课程课程课程课程 A B C D E