第8章图与网络分析1.ppt

《第8章图与网络分析1.ppt》由会员分享，可在线阅读，更多相关《第8章图与网络分析1.ppt（36页珍藏版）》请在优知文库上搜索。

1、第八章 图与网络分析第一节 图与网络的基本知识第二节 树第三节 最短路问题第四节 最大流问题第五节 最小费用流问题（一）哥尼斯堡七桥难题 1736年瑞士数学家欧拉（E.Euler）在求解七桥一笔画难题时，就用了点线图来分析论证：每个点均有奇数条边时，一笔画问题无解。（要求不重边）CDAB(前苏)哥尼斯堡城中的普雷格尔河ACBD（二）“环球旅行”问题1857年，英国数学家哈密尔顿(Hamilton)发明了一种游戏，他用一个实心正12面体象征地球，正12面体的20个顶点分别表示世界上20座名城，要求游戏者从任一城市出发，寻找一条可经由每个城市一次且仅一次再回到原出发点的路，这就是“环球旅行”问题。

2、（要求不重点）（三）“中国邮路问题”一个邮递员从邮局出发要走遍他所负责的每条街道去送信，问应如何选择适当的路线可使所走的总路程最短。这个问题就与欧拉回路有密切的关系。第一节 图与网络的基本知识一、图与网络的基本概念（一）图及其分类5家企业业务往来关系甲乙戊丙丁由上面的例子可以看出，这里所研究的图与平面几何中的图不同，这里只关心图中有多少个点，点与点之间有无连线，至于连线的方式是直线还是曲线，点与点的相对位置如何，都是无关紧要的。工人与需要完成的工作电路网络城市规划交通运输、信息传递、物资调配甲乙丙丁戊ABCD定义1 一个图是由点集V=vi和V中元素的无序对的一个集合Eek所构成的二元组，记为G

3、(V,E)，V中的元素vi叫做顶点，E中的元素ek叫做边。当V,E为有限集合时，G称为有限图，否则，称为无限图。两个点u,v属于V，如果边(u,v)属于E，则称u,v两点相邻。u,v称为边(u,v)的端点。12345e1e2e3e4e5e6 两条边ei,ej属于E，如果它们有一个公共端点u，则称ei,ej相邻。边ei,ej称为点u的关联边。用m(G)|E|表示图G中的边数，用n(G)|V|表示图G的顶点个数。在不引起混淆情况下简记为m,n。对于任一条边(vi,vj)属于E，如果边(vi,vj)端点无序，则它是无向边，此时图G称为无向图。如果边(vi,vj)的端点有序，即它表示以vi为始点，vj

4、为终点的有向边(或称弧)，这时图G称为有向图 一条边的两个端点如果相同称此边为环(自回路)。两个点之间多于一条边的，称为多重边。定义2 不含环和多重边的图称为简单图，含有多重边的图称为多重图。（a）（b）（c）（d）定义3 每一对顶点间都有边相连的无向简单图称为完全图。有n个顶点的无向完全图记作Kn。有向完全图则是指每一对顶点间有且仅有一条有向边的简单图。定义4 图G(V,E)的点集V可以分为两个非空子集X,Y，即XUYV，XY，使得E中每条边的两个端点必有一个端点属于X，另一个端点属于Y则称G为二部图(偶图、二分图)，有时记作G(X,Y,E)。（二）顶点的次（度）定义5 以点v为端点的边数叫

5、做点v的次。记作deg(v)，简记为d(v).次为1的点称为悬挂点。连结悬挂点的边称为悬挂边。次为零的点称为孤立点。次为奇数的点称为奇点。次为偶数的点称为偶点。123456（a）1234（b）123（c）4定理1 任何图中，顶点次数的总和等于边数的2倍。证明：由于每条边必与两个顶点关联，在计算点的次时，每条边均被计算了两次，所顶点次数的总和等于边数的2倍。定理2 任何图中，次为奇数的顶点必为偶数个。证明：设V1和V2分别为图G中奇点与偶点的集合(V1V2=V)。由定理1知：mvdvdVvVv2)()(21偶数偶数偶数 定义6 有向图中，以vi为始点的边数称为点vi的出次，用d+(vi)表示，以

6、vi为终点的边数称为点vi的入次，用d-(vi)表示。vi点的出次与入次之和就是该点的次。容易证明有向图中，所有顶点的入次之和等于所有顶点的出次之和。（三）子图 定义7 图G(V,E)，若E是E的子集，V是V的子集，且E中的边仅与V中的顶点相关联，则称G(V,E)是G的一个子图。特别地，若VV,则G称为G的生成子图(支撑子图)。（四）网络 在实际问题中，往往只用图来描述所研究对象之间的关系还是不够的，与图联系在一起的，通常还有与点或边有关的某些数量指标，我们常称之为“权”，权可以代表如距离、费用、通过能力(容量)等等。这种点或边带有某种数量指标的图你为网络(赋权间)。二、连通图定义8 无向图G

7、=(V,E),若图G中某些点与边的交替序列可以排成的形式,且 ,则称这个点边序列连接 与 的一条链,链长为k。),.,(11102kkkiiiiiiivevevev),.,1)(,(1ktvvetttiii0ivkivp点边列中没有重复的点和重复的边者为初等链。定义9 无向图G中,连结 与 的一条链,当与 是同一个点时,称此链为圈。圈中既无重复点也无重复边者为初等圈。p（1）对于有向图可以类似于无向图定义链和圈、初等链，此时不考虑边的方向。而当链(圈)上的边方向相同时,称为道路(回路)。p（2）对于无向图来说，道路与链、回路与圈意义相同。0ivkivkiv0iv定义10 一个图中任意两点间至少

8、有一条链相连，则称此图为连通图。任何一个不连通图都可以分为若干个连通子图，每一个称为一个分图。三、图的矩阵表示图的矩阵表示方法有权矩阵、邻接矩阵、关联矩阵、回路矩阵、割集矩阵等。定义11 网络（赋权图）G=（V，E），其中边(vi,vj)有权wij,构造矩阵A=(aij)nn,其中其它0),(Evvwajiijij则称A为网络G的权矩阵例：写出上图的权矩阵。定义12 对于图G=（V，E），|V|=n，构造一个矩阵A=(aij)nn，其中：其它0),(1Evvajiij则称A为图G的邻接矩阵v1v2v3v4v5742943856例：邻接矩阵表示上图。v5v1v2v3v4四、欧拉回路与中国邮路问题

9、 （一）欧拉回路与道路 定义13 连通图G中，若存在一条道路，经过每边一次且仅一次，则称这条路为欧拉道路。若存在一条回路，经过每边一次且仅一次则称这条回路为欧拉回路。欧拉图含有欧拉回路。定理3 无向连通图G是欧拉图，当且仅当G中无奇点。推论1 无向连通图G为欧拉图，当且仅当G的边集可划分为若干个初等回路。推论2 无向连通图G有欧拉道路，当且仅当G中恰有两个奇点。定理4 连通有向图G是欧拉图，当且仅当它每个顶点的出次等于入次。（二）中国邮路问题 一个邮递员，负责某一地区的信件投递。他每天要从邮局出发，走遍该地区所有街道再返回邮局，问应如何安排送信的路线可以使所走的总路程最短？这个问题是我国管梅谷

10、教授在1962年首先提出的。因此国际上通称为中国邮路问题。用图论的语言描述：给定一个连通图G，每边有非负权l(e)，要求一条回路过每边至少一次，且满足总权最小。第二节 树一、树的概念和性质（一）几个树的例子（1）乒乓球单打比赛抽签后，可用图来表示。ABCDEFGIJKLMNH运动员（2）某企业的组织结构。厂长人事科财务科总工程师新产品开发科技术科生产副厂长生产科设备科供应科动力科销售科检验科经营副厂长（二）定义14：连通且不含圈的图称为树。树中次为1的点称为树叶，次大于1的点称为分枝点。（三）树的性质定理6 图T=（V，E），|V|=n，|E|=m，则下列关于树的说法是等价的。（1）T是一个树

11、。（2）T无圈，且m=n-1。（3）T连通，且m=n-1。（4）T无圈，但每加一新边即得惟一一个圈。（5）T连通，但任舍去一个边就不连通。（6）T中任意两点，有惟一链相连。树的性质任何树必有树叶(即次数为1的节点)。树中任意两点之间有且仅有一条链连接相通。任意去掉一条树枝，该树就被分割成两互不连通的子图。树的任意两个顶点间添加一条边（称为连枝），就构成一个回路。仅用一条连枝构成的回路称为单连枝回路，也称为基本回路 一连通图可能具有很多树，这些树都是原连通图的部分图，即包括了原连通图的所有顶点。连枝的集合是原连通图相应的余树，或称补树。余树可能是树，也可能不是树，甚至是非连通图。二、图的生成树

12、定义15 若图G的生成子图是一棵树，则称该树为G的生成树(支撑树)。或简称为图G的树。图G中属于生成树的边称为树枝，不在生成树中的边际为弦。e1e2e3e4e5e6e7e8e9（a）e1e2e3e7e8e9（b）定理7 图G(V，E)有生成树的充分必要条件为G是连通图。寻找生成树的方法（1）深探法步骤如下（用标号法）在点集V中任取点v。给v以标号0。若某u点已得标号i，检查一端点为u的各边，另一端点是否均已标号。若有(u，w)边之w未标号，则结w以标号i十1，记下边(u，w)。今w代u，重复。若这样的边的另一端点均已有标号，就退到标号为i-1的r点，以r代u，重复。直到全部点得到标号为止。例：

13、试用深探法求下图中的一棵生成树012345678910111213（2）广探法 步骤如下：在点集V中任取一点v，给v以标号0。令所有标号为i的点集为Vi，检测查Vi，VVi中的边端点是否均已标号。对所有未标号之点均标以i+1，记下这些边。对标号i+1的点重复步骤，直到全部点得到标号为止。例：用广探法求上图中的一棵生成树。三、最小生成树问题 定义16 连通图G(V，E)、每条边上有非负权L(e)。一棵生成树所有树枝上权的总和，称为这个生成树的权。具有最小权的生成树称为最小生成树(最小支撑树)简称最小树。算法1 (Kruskal算法)p（1）将所有的边按从小到大的顺序排列p（2）将每条边加入到生成

14、子图中，如构成圈则舍去。p（3）重复（2）过程，直到所有的边试验完毕。v1v2v3v4v5v6v7871452635432将边按权从小到大排序(v2,v3),(v4,v5),(v6,v7),(v4,v6),(v5,v7),(v2,v5),(v5,v6),(v2,v4),(v3,v6),(v3,v4),(v1,v3),(v1,v2)将边加入到新图中,如不构成回路则保留;否则,去掉.例：求下图的一棵最小支撑树(v2,v3),(v4,v5),(v6,v7),(v4,v6),(v5,v7),(v2,v5),(v5,v6),(v2,v4),(v3,v6),(v3,v4),(v1,v3),(v1,v2)v

15、1v2v3v4v5v6v7871456543223其权为：19定理8 用Kruskal算法得到的子图T*(e1,e2,en-1)是一棵最小树。算法2（破圈法）（1）从图G中任选一棵树T1。（2）加上一条弦e1，T1+e1中立即生成一个圈。去掉此圈中最大权边，得到新树T2。以T2代T1，重复（2）再检查剩余的弦，直到全部弦检查完毕为止。例：用破圈法求上图中的一棵最小生成树。定理9 图G的生成树T为最小树，当且仅当对任一e来说，e是T+e中与之对应的圈e中的最大权边。四、根树及其应用定义17 若一个有向图在不考虑边的方向时是一棵树，则称这个有向图为有向树。定义18 有向树T，恰有一个结点入次为0，

16、其余各点入次均为1，则称T为根树（又称外向树）。根树中入次为0的点称为根。根树中出次为0的点称为叶，其他顶点称为分枝点。由根到某一顶点vi的道路长度（设每边长度为1），称为点vi的层次。定义 19 在根树中，若每个顶点的出次小于或等于m，称这棵树为m叉树。若每个顶点的出次恰好等于m或零，则称这棵树为完全m叉树。当m=2时，称为二叉树、完全二叉树。在实际问题中常讨论叶子上带权的二叉树。令有s个叶子的二叉树T各叶子的权分别为pi，根到各叶子的距离(层次)为li(i1，s)，这样二叉树T的总权数siiilpTm1)(满足总权最小的二叉树称为最优二叉树。霍夫曼(D A Huffman)给出了一个求最优二叉树的算法，所以又称霍夫曼树。算法步骤为：（1）将s个叶子按权由小至大排序，不失一般性，设p1p2 ps。（2）将二个具有最小权的叶子合并成 一个分枝点，其权为p1+p2，将新的分枝点作为一个叶子。令ss-1，若s1停止，否则转（1）例8 S=6，其权分别为4,3,3,2,2,1，求最优二叉树。例9 最优检索问题。使用计算机进行图书分类。现有五类图书共l00万册，其中有A类50万册，B类20万册