数模培训_图论模型

2019/9/17南京信息工程大学数理学院费文龙1图论模型主讲：费文龙[e-mail]数学建模培训2019/9/17南京信息工程大学数理学院费文龙2图论模型1.图论基本概念2.最短路径算法3.最小生成树算法4.遍历性问题5.二分图与匹配6.网络流问题7.关键路径问题8.系统监控模型9.着色模型2019/9/17南京信息工程大学数理学院费文龙31、图论的基本概念ABCD哥尼斯堡七桥示意图问题1(哥尼斯堡七桥问题):能否从任一陆地出发通过每座桥恰好一次而回到出发点？2019/9/17南京信息工程大学数理学院费文龙4ABDC七桥问题模拟图欧拉指出：如果每块陆地所连接的桥都是偶数座，则从任一陆地出发，必能通过每座桥恰好一次而回到出发地.2019/9/17南京信息工程大学数理学院费文龙5问题2(哈密顿环球旅行问题):十二面体的20个顶点代表世界上20个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？哈密顿圈（环球旅行游戏）2019/9/17南京信息工程大学数理学院费文龙6问题3(四色问题):对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了.问题4(关键路径问题):一项工程任务,大到建造一座大坝,一座体育中心,小至组装一台机床,一架电视机,都要包括许多工序.这些工序相互约束,只有在某些工序完成之后,一个工序才能开始.即它们之间存在完成的先后次序关系,一般认为这些关系是预知的,而且也能够预计完成每个工序所需要的时间.这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目,影响工程进度的要害工序是哪几个？2019/9/17南京信息工程大学数理学院费文龙7图的定义图论中的“图”并不是通常意义下的几何图形或物体的形状图,而是以一种抽象的形式来表达一些确定的事物之间的联系的一个数学系统.定义1一个有序二元组(V,E)称为一个图,记为G=(V,E),其中①V称为G的顶点集,V≠,其元素称为顶点或结点,简称点;②E称为G的边集,其元素称为边,它联结V中的两个点,如果这两个点是无序的,则称该边为无向边,否则,称为有向边.如果V={v1,v2,…,vn}是有限非空点集,则称G为有限图或n阶图.2019/9/17南京信息工程大学数理学院费文龙8如果E的每一条边都是无向边,则称G为无向图(如图1);如果E的每一条边都是有向边,则称G为有向图(如图2);否则,称G为混合图.图1图2并且常记V={v1,v2,…,vn},|V|=n;E={e1,e2,…,em}(ek=vivj),|E|=m.称点vi,vj为边vivj的端点.在有向图中,称点vi,vj分别为边vivj的始点和终点.该图称为(n,m)图2019/9/17南京信息工程大学数理学院费文龙9对于一个图G=(V,E),人们常用图形来表示它,称其为图解.凡是有向边,在图解上都用箭头标明其方向.例如,设V={v1,v2,v3,v4},E={v1v2,v1v3,v1v4,v2v3,v2v4,v3v4},则G=(V,E)是一个有4个顶点和6条边的图,G的图解如下图所示.2019/9/17南京信息工程大学数理学院费文龙10一个图会有许多外形不同的图解,下面两个图表示同一个图G=(V,E)的图解.其中V={v1,v2,v3,v4},E={v1v2,v1v3,v1v4,v2v3,v2v4,v3v4}.这两个图互为同构图,今后将不计较这种外形上的差别,而用一个容易理解的、确定的图解去表示一个图.2019/9/17南京信息工程大学数理学院费文龙11有边联结的两个点称为相邻的点,有一个公共端点的边称为相邻边.边和它的端点称为互相关联.常用d(v)表示图G中与顶点v关联的边的数目,d(v)称为顶点v的度数.对于有向图,还有出度和入度之分.用N(v)表示图G中所有与顶点v相邻的顶点的集合.d(v1)=d(v3)=d(v4)=4,d(v2)=2.mvdnii2)(1握手定理：2019/9/17南京信息工程大学数理学院费文龙12我们今后只讨论有限简单图：(1)顶点个数是有限的;(2)任意一条边有且只有两个不同的点与它相互关联;(3)若是无向图,则任意两个顶点最多只有一条边与之相联结;(4)若是有向图,则任意两个顶点最多只有两条边与之相联结.当两个顶点有两条边与之相联结时，这两条边的方向相反.如果某个有限图不满足(2)(3)(4),可在某条边上增设顶点使之满足.2019/9/17南京信息工程大学数理学院费文龙13定义2若将图G的每一条边e都对应一个实数F(e),则称F(e)为该边的权,并称图G为赋权图(网络),记为G=(V,E,F).定义3任意两点均有通路的图称为连通图.定义4连通而无圈的图称为树,常用T表示树.2019/9/17南京信息工程大学数理学院费文龙14例一摆渡人欲将一只狼,一头羊,一篮菜从河西渡过河到河东.由于船小,一次只能带一物过河，并且狼与羊,羊与菜不能独处.给出渡河方法.解：用四维0-1向量表示(人,狼,羊,菜)在河西岸的状态(在河西岸则分量取1,否则取0),共有24=16种状态.在河东岸的状态类似记作.由题设,状态(0,1,1,0),(0,0,1,1),(0,1,1,1)是不允许的,从而对应状态(1,0,0,1),(1,1,0,0),(1,0,0,0)也是不允许的.以可允许的10个状态向量作为顶点,将可能互相转移的状态用线段连接起来构成一个图.根据此图便可找到渡河方法.2019/9/17南京信息工程大学数理学院费文龙15(1,1,1,1)(1,1,1,0)(1,1,0,1)(1,0,1,1)(1,0,1,0)(0,0,0,0)(0,0,0,1)(0,0,1,0)(0,1,0,0)(0,1,0,1)(0,1,0,1)(0,1,0,0)(0,0,1,0)(0,0,0,1)(0,0,0,0)(1,0,1,0)(1,0,1,1)(1,1,0,1)(1,1,1,0)(1,1,1,1)河西=(人,狼,羊,菜)河东=(人,狼,羊,菜)将10个顶点分别记为A1,A2,…,A10,则渡河问题化为在该图中求一条从A1到A10的路.从图中易得到两条路：A1A6A3A7A2A8A5A10;A1A6A3A9A4A8A5A10.2019/9/17南京信息工程大学数理学院费文龙16图的矩阵表示⑴邻接矩阵邻接矩阵表示了点与点之间的邻接关系.一个n阶图G的邻接矩阵A=(aij)n×n,其中.,0;,1EvEvaijijij0101100101001010A2019/9/17南京信息工程大学数理学院费文龙17无向图G的邻接矩阵A是一个对称矩阵.0101101101011110A⑵权矩阵一个n阶赋权图G=(V,E,F)的权矩阵A=(aij)n×n,其中.,;;0),(EvjiEvvvFaijijjiij有限简单图基本上可用权矩阵来表示.2019/9/17南京信息工程大学数理学院费文龙1805420370860A无向图G的权矩阵A是一个对称矩阵.02420737064360A2019/9/17南京信息工程大学数理学院费文龙19⑶关联矩阵（略）一个有m条边的n阶有向图G的关联矩阵A=(aij)n×m,其中若vi是ej的始点;若vi是ej的终点;若vi与ej不关联.,0,1,1ija有向图的关联矩阵每列的元素中有且仅有一个1,有且仅有一个-1.1101100011011000000111011001A2019/9/17南京信息工程大学数理学院费文龙20一个有m条边的n阶无向图G的关联矩阵A=(aij)n×m,其中若vi与ej关联;若vi与ej不关联.,0,1ija无向图的关联矩阵每列的元素中有且仅有两个1.110100101010011001000111A2019/9/17南京信息工程大学数理学院费文龙212、最短路径算法定义1设P(u,v)是赋权图G=(V,E,F)中从点u到v的路径,用E(P)表示路径P(u,v)中全部边的集合,记)()()(PEeeFPF则称F(P)为路径P(u,v)的权或长度(距离).定义2若P0(u,v)是G中连接u,v的路径,且对任意在G中连接u,v的路径P(u,v)都有F(P0)≤F(P),则称P0(u,v)是G中连接u,v的最短路.2019/9/17南京信息工程大学数理学院费文龙22重要性质：若v0v1…vm是图G中从v0到vm的最短路,则1≤k≤m,v0v1…vk必为G中从v0到vk的最短路.即：最短路是一条路，且最短路的任一段也是最短路.求非负赋权图G中某一点到其它各点最短路，一般用Dijkstra标号算法；求非负赋权图上任意两点间的最短路，一般用Floyd算法.这两种算法均适用于有向非负赋权图.下面分别介绍两种算法的基本过程.2019/9/17南京信息工程大学数理学院费文龙23Dijkstra算法指标（a为起点）设T为V的子集，P=V-T且a∈T，对所有t∈T，设l(t)表示从a到t的所有通路中距离最短的一条的长度，且这条路径中不包含T中其他的结点，则称l(t)为t关于集合P的指标，若不存在这样的路径，这记l(t)=∞注：l(t)不一定是从a到t的最短路径，因为最短路径中可能包含T中其他的节点。定理1若t是T中关于P由最小指标的结点，则l(t)是a和t之间的最短距离。定理2设T为V的子集，P=V-T，设(1)对P中的任一点p,存在一条从a到p的最短路径,这条路径仅有P中的点构成,(2)对于每一点t,它关于P的指标为l(t),令x为最小指标所在的点,即:l(x)=min(l(t))(tT),(3)令P'=P{x},T'=T-{x},l'(t)表示T'中结点t关于P'的指标,则l'(t)=min{l(t),l(x)+w(x,t)}2019/9/17南京信息工程大学数理学院费文龙24Dijkstra算法（求a点到其他点的最短路径）1、初始化，P={a}，T=V-{a}，对每个结点t计算指标l(t)=w(a,t)2、设x为T中关于P有最小指标的点,即:l(x)=min(l(t))(t∈T),3、若T=Ф,则算法结束;否则,令P'=PU{x},T'=T-{x}按照公式l'(t)=min{l(t),l(x)+w(x,t)},计算T'中每一个结点t'关于P'的指标.4、P'代替P,T'代替T,重复步骤2,3（其中：w(x,y)为图的权矩阵）2019/9/17南京信息工程大学数理学院费文龙25改进Dijkstra算法（求a点到其他点的最短路径）1、初始化，P={a}，T=V-{a}，对每个结点t计算指标l(t)=w(a,t),pro(t)=a;2、设x为T中关于P有最小指标的点,即:l(x)=min(l(t))(t∈T);3、若T=Ф,则算法结束;否则,令P‘=PU{x},T’=T-{x}按照公式l‘(t)=min{l(t),l(x)+w(x,t)},计算T’中每一个结点t‘关于P’的指标.若l(x)+w(x,t)l(t),pro(t)=x;4、P'代替P,T'代替T,重复步骤2,3（其中：w(x,y)为图的权矩阵）2019/9/17南京信息工程大学数理学院费文龙26ABCDEFGHA02∞∞∞∞6∞B207∞∞13∞C∞7043∞∞∞D∞∞405∞∞2E∞∞3502∞2F∞1∞∞201∞G63∞∞∞104H∞∞∞22∞40例求下图中A点到其他点的最短路.2161342272435ABFGHDCE2019/9/17南京信息工程大学数理学院费文龙27Floyd算法（求任意两点的最短路径）设A=(aij)n×n为赋权图G=(V,E,F)的权矩阵,dij表示从vi到vj点的距离,rij表示从vi到vj点的最短路中前一个点的编号.①