第8章 图与网络分析课件

《第8章 图与网络分析课件》由会员分享，可在线阅读，更多相关《第8章 图与网络分析课件（36页珍藏版）》请在金锄头文库上搜索。

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

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

3、E中的元素ek叫做边。 当V,E为有限集合时，G称为有限图，否则，称为无限图。,两个点u,v属于V，如果边(u,v)属于E，则称u,v两点相邻。u,v称为边(u,v)的端点。,两条边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为终点的有向边(或称弧)，这时图G称为有向图 一条边的两个端点

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

5、结悬挂点的边称为悬挂边。 次为零的点称为孤立点。 次为奇数的点称为奇点。 次为偶数的点称为偶点。,定理1 任何图中，顶点次数的总和等于边数的2倍。 证明：由于每条边必与两个顶点关联，在计算点的次时，每条边均被计算了两次，所顶点次数的总和等于边数的2倍。 定理2 任何图中，次为奇数的顶点必为偶数个。 证明：设V1和V2分别为图G中奇点与偶点的集合(V1V2=V)。由定理1知：,偶数,偶数,偶数,定义6 有向图中，以vi为始点的边数称为点vi的出次，用d+(vi)表示，以vi为终点的边数称为点vi的入次，用d-(vi)表示。vi点的出次与入次之和就是该点的次。容易证明有向图中，所有顶点的入次之和等

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

7、中没有重复的点和重复的边者为初等链。 定义9 无向图G中,连结 与 的一条链,当与 是同一个点时,称此链为圈。圈中既无重复点也无重复边者为初等圈。 （1）对于有向图可以类似于无向图定义链和圈、初等链，此时不考虑边的方向。而当链(圈)上的边方向相同时,称为道路(回路)。 （2）对于无向图来说，道路与链、回路与圈意义相同。,定义10 一个图中任意两点间至少有一条链相连，则称此图为连通图。任何一个不连通图都可以分为若干个连通子图，每一个称为一个分图。 三、图的矩阵表示 图的矩阵表示方法有权矩阵、邻接矩阵、关联矩阵、回路矩阵、割集矩阵等。 定义11 网络（赋权图）G=（V，E），其中边(vi,vj)有

8、权wij,构造矩阵A=(aij)nn,其中,则称A为网络G的权矩阵,例：写出上图的权矩阵。 定义12 对于图G=（V，E），|V|=n，构造一个矩阵A =(aij)nn ，其中：,则称A为图G的邻接矩阵,例：邻接矩阵表示上图。,v5,四、欧拉回路与中国邮路问题 （一）欧拉回路与道路 定义13 连通图G中，若存在一条道路，经过每边一次且仅一次，则称这条路为欧拉道路。若存在一条回路，经过每边一次且仅一次则称这条回路为欧拉回路。欧拉图含有欧拉回路。 定理3 无向连通图G是欧拉图，当且仅当G中无奇点。 推论1 无向连通图G为欧拉图，当且仅当G的边集可划分为若干个初等回路。 推论2 无向连通图G有欧拉道

9、路，当且仅当G中恰有两个奇点。,定理4 连通有向图G是欧拉图，当且仅当它每个顶点的出次等于入次。 （二）中国邮路问题 一个邮递员，负责某一地区的信件投递。他每天要从邮局出发，走遍该地区所有街道再返回邮局，问应如何安排送信的路线可以使所走的总路程最短？这个问题是我国管梅谷教授在1962年首先提出的。因此国际上通称为中国邮路问题。用图论的语言描述：给定一个连通图G，每边有非负权l(e)，要求一条回路过每边至少一次，且满足总权最小。,第二节 树,一、树的概念和性质 （一）几个树的例子 （1）乒乓球单打比赛抽签后，可用图来表示。,（2）某企业的组织结构。,（二）定义14：连通且不含圈的图称为树。树中次

10、为1的点称为树叶，次大于1的点称为分枝点。 （三）树的性质 定理6 图T=（V，E），|V|=n，|E|=m，则下列关于树的说法是等价的。 （1）T是一个树。 （2）T无圈，且m=n-1。 （3）T连通，且m=n-1。 （4）T无圈，但每加一新边即得惟一一个圈。 （5）T连通，但任舍去一个边就不连通。 （6）T中任意两点，有惟一链相连。,树的性质 任何树必有树叶(即次数为1的节点)。 树中任意两点之间有且仅有一条链连接相通。任意去掉一条树枝，该树就被分割成两互不连通的子图。 树的任意两个顶点间添加一条边（称为连枝），就构成一个回路。仅用一条连枝构成的回路称为单连枝回路，也称为基本回路 一连通图

11、可能具有很多树，这些树都是原连通图的部分图，即包括了原连通图的所有顶点。 连枝的集合是原连通图相应的余树，或称补树。余树可能是树，也可能不是树，甚至是非连通图。,二、图的生成树 定义15 若图G的生成子图是一棵树，则称该树为G的生成树(支撑树)。或简称为图G的树。图G中属于生成树的边称为树枝，不在生成树中的边际为弦。,定理7 图G(V，E)有生成树的充分必要条件为G是连通图。 寻找生成树的方法 （1）深探法 步骤如下（用标号法） 在点集V中任取点v。给v以标号0。 若某u点已得标号i，检查一端点为u的各边，另一端点是否均已标号。 若有(u，w)边之w未标号，则结w以标号i十1，记下边(u，w)

12、。今w代u，重复 。 若这样的边的另一端点均已有标号，就退到标号为i-1的r点，以r代u，重复。直到全部点得到标号为止。,例：试用深探法求下图中的一棵生成树,0,1,2,3,4,5,6,7,8,9,10,11,12,13,（2）广探法 步骤如下： 在点集V中任取一点v，给v以标号0。 令所有标号为i的点集为Vi，检测查Vi，VVi中的边端点是否均已标号。对所有未标号之点均标以i+1，记下这些边。 对标号i+1的点重复步骤，直到全部点得到标号为止。 例：用广探法求上图中的一棵生成树。,三、最小生成树问题 定义16 连通图G(V，E)、每条边上有非负权L(e)。一棵生成树所有树枝上权的总和，称为这

13、个生成树的权。具有最小权的生成树称为最小生成树(最小支撑树)简称最小树。 算法1 (Kruskal算法) （1）将所有的边按从小到大的顺序排列 （2）将每条边加入到生成子图中，如构成圈则舍去。 （3）重复（2）过程，直到所有的边试验完毕。,将边按权从小到大排序 ( 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,

14、v6),(v5,v7),(v2,v5),(v5,v6),(v2,v4), (v3,v6),(v3,v4),(v1,v3),(v1,v2),其权为：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 若

15、一个有向图在不考虑边的方向时是一棵树，则称这个有向图为有向树。 定义18 有向树T，恰有一个结点入次为0，其余各点入次均为1，则称T为根树（又称外向树）。根树中入次为0的点称为根。根树中出次为0的点称为叶，其他顶点称为分枝点。由根到某一顶点vi的道路长度（设每边长度为1），称为点vi的层次。,定义 19 在根树中，若每个顶点的出次小于或等于m，称这棵树为m叉树。若每个顶点的出次恰好等于m或零，则称这棵树为完全m叉树。当m=2时，称为二叉树、完全二叉树。 在实际问题中常讨论叶子上带权的二叉树。令有s个叶子的二叉树T各叶子的权分别为pi，根到各叶子的距离(层次)为li(i1，s)，这样二叉树T的总权数,满足总权最小的二叉树称为最优二叉树。霍夫曼(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万册，C类5万册，D类l0万册，E类15万册。问如何安排分检过程，可使总的运算（比较）次数最小?,