数模图论tp2016.

《数模图论tp2016.》由会员分享，可在线阅读，更多相关《数模图论tp2016.（83页珍藏版）》请在金锄头文库上搜索。

1、2019/11/9,西安理工大学理学院 唐平,1,图 论 模 型,主讲：唐 平,数学建模培训,2019/11/9,西安理工大学理学院 唐平,2,图论模型,图论基本概念 最短路径算法 最小生成树算法 遍历性问题 二分图与匹配,网络流问题 关键路径问题 系统监控模型 着色模型,2019/11/9,西安理工大学理学院 唐平,3,1、图论的基本概念,问题1(哥尼斯堡七桥问题): 能否从任一陆地出发通过每座桥恰好一次而回到出发点？,2019/11/9,西安理工大学理学院 唐平,4,欧拉指出： 如果每块陆地所连接的桥都是偶数座，则从任一陆地出发，必能通过每座桥恰好一次而回到出发地.,2019/11/9,西

2、安理工大学理学院 唐平,5,问题2(哈密顿环球旅行问题): 十二面体的20个顶点代表世界上20个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？,2019/11/9,西安理工大学理学院 唐平,6,问题3(四色问题): 对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了.,问题4(关键路径问题): 一项工程任务,大到建造一座大坝,一座体育中心,小至组装一台机床,一架电视机, 都要包括许多工序.这些工序相互约束,只有在某些工序完成之后, 一个工序才能开始. 即它们之间存在完成的先后次序关系,一般认为这些关系是预知的, 而且也能够预计完成每个工

3、序所需要的时间. 这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目, 影响工程进度的要害工序是哪几个？,2019/11/9,西安理工大学理学院 唐平,7,图的定义,图论中的“图”并不是通常意义下的几何图形或物体的形状图, 而是以一种抽象的形式来表达一些确定的事物之间的联系的一个数学系统.,定义1 一个有序二元组(V, E ) 称为一个图, 记为G = (V, E ), 其中, V称为G的顶点集, V, 其元素称为顶点或结点, 简称点; E称为G的边集, 其元素称为边, 它联结V 中的两个点, 如果这两个点是无序的, 则称该边为无向边, 否则, 称为有向边. 如果V = v1,

4、 v2, , vn是有限非空点集, 则称G为有限图或n阶图.,2019/11/9,西安理工大学理学院 唐平,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/11/9,西安理工大学理学院 唐平,9,对于一个图

5、G = (V, E ), 人们常用图形来表示它, 称其为图解. 凡是有向边, 在图解上都用箭头标明其方向.,例如, 设V = v1 , v2 , v3 , v4, E = v1v2 , v1v3 , v1v4 , v2v3 , v2v4 , v3v4, 则G = (V, E ) 是一个有4个顶点和6条边的图, G的图解如下图所示.,2019/11/9,西安理工大学理学院 唐平,10,一个图会有许多外形不同的图解, 下面两个图表示同一个图G = (V, E )的图解.其中 V = v1 , v2 , v3 , v4, E = v1v2 , v1v3 , v1v4 , v2v3 , v2v4 ,

6、v3v4.,这两个图互为同构图,今后将不计较这种外形上的差别,而用一个容易理解的、确定的图解去表示一个图.,2019/11/9,西安理工大学理学院 唐平,11,有边联结的两个点称为相邻的点, 有一个公共端点的边称为相邻边. 边和它的端点称为互相关联. 常用d(v)表示图G中与顶点v关联的边的数目, d(v)称为顶点v的度数. 对于有向图,还有出度和入度之分. 用N(v)表示图G中所有与顶点v相邻的顶点的集合.,d(v1)= d(v3)= d(v4)=4, d(v2)=2.,握手定理：,2019/11/9,西安理工大学理学院 唐平,12,我们今后只讨论有限简单图：,(1) 顶点个数是有限的; (

7、2) 任意一条边有且只有两个不同的点与它相互关联; (3) 若是无向图, 则任意两个顶点最多只有一条边与之相联结; (4) 若是有向图, 则任意两个顶点最多只有两条边与之相联结. 当两个顶点有两条边与之相联结时，这两条边的方向相反. 如果某个有限图不满足(2)(3)(4),可在某条边上增设顶点使之满足.,2019/11/9,西安理工大学理学院 唐平,13,定义2 若将图G的每一条边e都对应一个实数F (e), 则称F (e)为该边的权, 并称图G为赋权图(网络), 记为G = (V, E , F ).,定义3 任意两点均有通路的图称为连通图. 定义4 连通而无圈的图称为树, 常用T表示树.,2

8、019/11/9,西安理工大学理学院 唐平,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个状态向量作为顶点,将可能互相转移的状态用线段连接起来构成一个图. 根据此图便可找到渡河方

9、法.,2019/11/9,西安理工大学理学院 唐平,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到A1

10、0的路. 从图中易得到两条路： A1 A6 A3 A7 A2 A8 A5 A10; A1 A6 A3 A9 A4 A8 A5 A10.,2019/11/9,西安理工大学理学院 唐平,16,图的矩阵表示, 邻接矩阵 邻接矩阵表示了点与点之间的邻接关系.一个n阶图G的邻接矩阵A = (aij )nn , 其中,2019/11/9,西安理工大学理学院 唐平,17,无向图G的邻接矩阵A是一个对称矩阵., 权矩阵 一个n阶赋权图G = (V, E, F)的权矩阵A = (aij ) nn , 其中,有限简单图基本上可用权矩阵来表示.,2019/11/9,西安理工大学理学院 唐平,18,无向图G的权矩阵A

11、是一个对称矩阵.,2019/11/9,西安理工大学理学院 唐平,19, 关联矩阵（略） 一个有m条边的n阶有向图G的关联矩阵A = (aij )nm , 其中,若vi是ej的始点; 若vi是ej的终点; 若vi与ej不关联.,有向图的关联矩阵每列的元素中有且仅有一个1,有且仅有一个 - 1.,2019/11/9,西安理工大学理学院 唐平,20,一个有m条边的n阶无向图G的关联矩阵A = (aij )nm , 其中,若vi与ej关联; 若vi与ej不关联.,无向图的关联矩阵每列的元素中有且仅有两个1.,2019/11/9,西安理工大学理学院 唐平,21,2、最短路径算法,定义1 设P(u, v)

12、 是赋权图G = (V, E , F) 中从点u到v的路径, 用E(P) 表示路径P(u, v)中全部边的集合, 记,则称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/11/9,西安理工大学理学院 唐平,22,重要性质：,若v0 v1 vm 是图G中从v0到vm的最短路, 则1km, v0v1 vk 必为G中从v0到vk的最短路.,即：最短路是一条路，且最短路的任一段也是最短路. 求

13、非负赋权图G中某一点到其它各点最短路，一般用Dijkstra标号算法；求非负赋权图上任意两点间的最短路，一般用Floyd算法. 这两种算法均适用于有向非负赋权图. 下面分别介绍两种算法的基本过程.,2019/11/9,西安理工大学理学院 唐平,23,Dijkstra算法,指标（a为起点） 设T为V的子集，P=V-T且aT，对所有tT，设 l(t)表示从a到t的所有通路中距离最短的一条的长度，且这条路径中不包含T中其他的结点，则称l(t)为t关于集合P的指标，若不存在这样的路径，这记l(t)= 注：l(t)不一定是从a到t的最短路径，因为最短路径中可能包含T中其他的节点。 定理1 若t是T中关于

14、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) (t T), (3)令P=PUx,T=T-x,l(t)表示T中结点t关于P的指标,则 l(t)=minl(t),l(x)+w(x,t),2019/11/9,西安理工大学理学院 唐平,24,Dijkstra算法（求a点到其他点的最短路径）,1、初始化，P=a，T=V-a，对每个结点t计算指标 l(t)=w(a,t) 2

15、、设x为T中关于P有最小指标的点, 即:l(x)=min(l(t) (tT), 3、若T=,则算法结束; 否则,令P=P Ux,T=T-x 按照公式l(t)=minl(t),l(x)+w(x,t), 计算T中每一个结点t关于P的指标. 4、P代替P,T代替T,重复步骤2,3 （ 其中：w(x,y)为图的权矩阵）,2019/11/9,西安理工大学理学院 唐平,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) (tT); 3、若T=,则算法结束; 否则,令P=P Ux,T=T-x 按照公式l(t)=minl(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/11/9,西安理工大学理学院 唐平,26,A B C D E F G H A 0 2 6 B 2 0 7 1 3 C 7 0 4 3 D 4 0 5 2 E 3 5 0 2 2 F 1 2 0 1 G 6 3 1 0 4 H 2 2 4 0,例 求