《第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万册。问如何安排分检过程,可使总的运算(比较)次数最小?,