数学建模培训资料PPT图论模型建模PPT

《数学建模培训资料PPT图论模型建模PPT》由会员分享，可在线阅读，更多相关《数学建模培训资料PPT图论模型建模PPT（82页珍藏版）》请在装配图网上搜索。

1、图图 论论 模模 型型数学建模培训1.图论基本概念2.最短路径算法3.最小生成树算法4.遍历性问题5. 网络流问题1 引言引言l 图论起源于图论起源于1818世纪。第一篇图论论文世纪。第一篇图论论文是瑞士数学家欧拉于是瑞士数学家欧拉于1736 1736 年发表的年发表的“哥尼哥尼斯堡的七座桥斯堡的七座桥”。 l哥尼斯堡七桥问题就是一个典型的例子。哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来。问题是个岛及岛与河岸联结起来。问题是要从这要从这四块陆地中的任何一块开始通过每一座桥四块陆地中的任何一块开始通过每一座桥

2、正好一次，再回到起点。正好一次，再回到起点。 当然可以通过试验去尝试解决这个问题，但当然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。该城居民的任何尝试均未成功。 欧拉为了解决这个问题，采用了建立数学模欧拉为了解决这个问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将型的方法。他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而每一座桥用连接相应两点的一条线来代替，从而得到一个有得到一个有四个四个“点点”，七条，七条“线线”的的“图图”。问题成为问题成为从任一点出发一笔画出七条线再回到起从任一点出发一笔画出七条线再回到起点点。欧拉考察了一般一

3、笔画的结构特点，给出了。欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则一笔画的一个判定法则：这个图是连通的，且每这个图是连通的，且每个点都与偶数线相关联，个点都与偶数线相关联，将这个判定法则应用于将这个判定法则应用于七桥问题，得到了七桥问题，得到了“不可能走通不可能走通”的结果，不但的结果，不但彻底解决了这个问题，而且开创了图论研究的先彻底解决了这个问题，而且开创了图论研究的先河。河。 我们首先通过一些例子来了解网络优化问题。我们首先通过一些例子来了解网络优化问题。例例1 1 最短路问题最短路问题（SPPSPPshortest path problemshortest path p

4、roblem） 一名货车司机奉命在最短的时间内将一车货物从一名货车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路因此有多种行车路线，这名司机应选择哪条线路呢？假设货车的运行速度是恒定的，那么这一问呢？假设货车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。题相当于需要找到一条从甲地到乙地的最短路。例例2 2 公路连接问题公路连接问题 某一地区有若干个主要城市，现准备修建高速公某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一

5、个城路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？公路，使得总成本最小？例例3 3 指派问题指派问题（assignment problemassignment problem） 一家公司经理准备安排名员工去完成项一家公司经理准备安排名员工去完成项任务，任务， 每人一项。由于各员工的特点不同，每人一项。由于各员工的特点不同，不

6、同的员工去完成同一项任务时所获得的回不同的员工去完成同一项任务时所获得的回报是不同的。报是不同的。 如何分配工作方案可以使总回报最大？如何分配工作方案可以使总回报最大？l上述问题有两个共同的特点：上述问题有两个共同的特点：一是一是它们的它们的目的都是从若干可能的安排或方案中寻求目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把某种意义下的最优安排或方案，数学上把这种问题称为最优化或优化这种问题称为最优化或优化（optimizationoptimization）问题；）问题；二是二是它们都易于它们都易于用图形的形式直观地描述和表达，数学上用图形的形式直观地描述和表达，数学上

7、把这种与图相关的结构称为网络把这种与图相关的结构称为网络（networknetwork）。与图和网络相关的最优化问）。与图和网络相关的最优化问题就是网络最优化或称网络优化题就是网络最优化或称网络优化 （netwoknetwok optimizationoptimization）问题。）问题。 2021-12-22 图论中的图论中的“图图”并不是通常意义下的几何图形或物并不是通常意义下的几何图形或物体的形状图体的形状图, , 而是以一种抽象的形式来表达一些确定的而是以一种抽象的形式来表达一些确定的事物之间的联系的一个数学系统事物之间的联系的一个数学系统. . 定义定义1 一个有序二元组一个有序二

8、元组(V, E ) 称为一个称为一个图图, 记为记为G = (V, E ), 其中其中 V称为称为G的顶点集的顶点集, V , 其元素称为其元素称为顶点顶点或或结点结点, 简称简称点点; E称为称为G的边集的边集, 其元素称为其元素称为边边, 它联结它联结V 中的两中的两个点个点, 如果这两个点是无序的如果这两个点是无序的, 则称该边为则称该边为无向边无向边, 否则否则, 称为称为有向边有向边. 如果如果V = v1, v2, , vn是有限非空点集是有限非空点集, 则称则称G为为有有限图限图或或n阶图阶图. 2021-12-22 如果如果E的每一条边都是无向边的每一条边都是无向边, 则称则称

9、G为为无向图无向图( (如如图图1)1); 如果如果E的每一条边都是有向边的每一条边都是有向边, 则称则称G为为有向图有向图( (如图如图2)2); 否则否则, 称称G为为混合图混合图. 图图1 1图图2 2并且常记并且常记V = v1, v2, , vn, |V | = n ;E = e1, e2, , em(ek=vivj ) , |E | = m.称点称点vi , vj为边为边vivj的的端点端点. 在有向图中在有向图中, 称点称点vi , vj分别为边分别为边vivj的的始点始点和和终点终点. 该图称为该图称为(n,m)图图2021-12-22 对于一个图对于一个图G = (V, E

10、), 人们常用图形来表示人们常用图形来表示它它, 称其为称其为图解图解. 凡是有向边凡是有向边, 在图解上都用箭头在图解上都用箭头标明其方向标明其方向. 例如例如, 设设V = v1 , v2 , v3 , v4, E = v1v2 , v1v3 , v1v4 , v2v3 , v2v4 , v3v4, 则则G = (V, E ) 是一个有是一个有4个顶个顶点和点和6条边的图条边的图, G的图解如下图所示的图解如下图所示. 2021-12-22 一个图会有许多外形不同的图解一个图会有许多外形不同的图解, , 下面两个图表示下面两个图表示同一个图同一个图G = (V, E )的图解的图解. .其

11、中其中V = v1 , v2 , v3 , v4,E = v1v2 , v1v3 , v1v4 , v2v3 , v2v4 , v3v4. 这两个图互为这两个图互为同构图同构图, ,今后将不计较这种外形上的差今后将不计较这种外形上的差别别, ,而用一个容易理解的、确定的图解去表示一个图而用一个容易理解的、确定的图解去表示一个图. .2021-12-22 有边联结的两个点称为有边联结的两个点称为相邻的点相邻的点, 有一个公共端点的有一个公共端点的边称为边称为相邻边相邻边. 边和它的端点称为边和它的端点称为互相关联互相关联. 常用常用d(v)表示表示图图G中与顶点中与顶点v关联的边的数目关联的边的

12、数目, d(v)称为顶点称为顶点v的的度数度数. 对对于有向图于有向图,还有还有出度出度和和入度入度之分之分. d(v1)= d(v3)= d(v4)=4,d(v2)=2.mvdnii2)(1握手定理：握手定理：2021-12-22 定义定义2 若将图若将图G的每一条边的每一条边e都对应一个实数都对应一个实数F (e), 则则称称F (e)为该边的为该边的权权, 并称图并称图G为为赋权图赋权图(网络网络), 记为记为G = (V, E , F ). 定义定义3 任意两点均有通路的图称为任意两点均有通路的图称为连通图连通图. 定义定义4 连通而无圈的图称为连通而无圈的图称为树树, 常用常用T表示

13、树表示树. 2021-12-22图的矩阵表示图的矩阵表示 邻接矩阵邻接矩阵 邻接矩阵表示了点与点之间的邻接关系邻接矩阵表示了点与点之间的邻接关系. .一个一个n阶图阶图G的邻接矩阵的邻接矩阵A = (aij )nn , 其中其中 ., 0;, 1EvEvaijijij0101100101001010A无向图无向图G的邻接矩阵的邻接矩阵A是一个对称矩阵是一个对称矩阵. . 0101101101011110A 权矩阵权矩阵 一个一个n阶赋权图阶赋权图G = (V, E, F)的权矩阵的权矩阵A = (aij ) nn , 其中其中 .,;0),(EvjiEvvvFaijijjiij2021-12-

14、2205420370860A无向图无向图G的权矩阵的权矩阵A是一个对称矩阵是一个对称矩阵. . 02420737064360A2021-12-22 关联矩阵（略）关联矩阵（略） 一个有一个有m条边的条边的n阶有向图阶有向图G的的关联矩阵关联矩阵A = (aij )nm , 其中其中 若若vi是是ej的始点的始点;若若vi是是ej的终点的终点;若若vi与与ej不关联不关联. ., 0, 1, 1ija1101100011011000000111011001A2021-12-22 一个有一个有m条边的条边的n阶无向图阶无向图G的关联矩阵的关联矩阵A = (aij )nm , 其中其中 若若vi与与

15、ej关联关联;若若vi与与ej不关联不关联. ., 0, 1ija110100101010011001000111A2021-12-22 定义定义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)

16、都有都有F (P0)F(P), 则称则称P0 (u, v) 是是G 中连接中连接u, v的的最短路最短路. 2021-12-22重要性质：重要性质： 若若v0 v1 vm 是是图图G中从中从v0到到vm的最短路的最短路, 则则 1km, v0v1 vk 必为必为G中从中从v0到到vk的最短路的最短路. 即：最短路是一条路，且最短路的任一段也是最短即：最短路是一条路，且最短路的任一段也是最短路路. 求非负赋权图求非负赋权图G中某一点到其它各点最短路，一般中某一点到其它各点最短路，一般用用Dijkstra标号算法；求非负赋权图上任意两点间的最标号算法；求非负赋权图上任意两点间的最短路，一般用短路，

17、一般用Floyd算法算法. . 这两种算法均适用于有向非负赋权图这两种算法均适用于有向非负赋权图. . 下面分别介绍两种算法的基本过程下面分别介绍两种算法的基本过程. .2021-12-22Dijkstra算法算法l求最短路已有成熟的算法：迪克斯特拉求最短路已有成熟的算法：迪克斯特拉（DijkstraDijkstra）算法，其基本思想是按距）算法，其基本思想是按距u u0 0从近到远为顺序，依次求得从近到远为顺序，依次求得u u0 0到的到的G G各顶各顶点的最短路和距离，直至所有顶点，算点的最短路和距离，直至所有顶点，算法结束。为避免重复并保留每一步的计法结束。为避免重复并保留每一步的计算信

18、息，采用了标号算法。下面是该算算信息，采用了标号算法。下面是该算法。法。2021-12-22 Dijkstra算法算法 用dij表示两相邻点i与j的距离。若i与j不相邻，令dij=，显然dii=0.用Lsi表示从s点到i点的最短距离。现要求从s点到某一点t的最短路，用DijkstraDijkstra算法步骤如下：算法步骤如下：l1、从s点出发，因Lss=0，将此值标注在s旁的小方框内，表示s已标号。l2、从s点出发，找出与s相邻的点中距离最小的一个，设为r，将Lsr=Lss+dsr的值标注在r旁，表明r已标号。l3、从已标号的点出发，找出与这些点相邻的所有未标号点p。若有Lsp=minLss+

19、dsp;Lsr+drp,则对p点标号，并将Lsp的值标注在p点旁的小方框内。l4、重复第3步，一直到t点得到标号为止。例例 求下图求下图v1v1点到点到v7v7点的最短路点的最短路. .Foyd算法的基本思想例例 求下图中任意两点间的最短路求下图中任意两点间的最短路. .例例 设备更新问题设备更新问题l某人购买一台摩托车，准备在今后4年内使用，他可在第1年初购一台新车，连续使用4年，也可于任何一年年末卖掉，于下一年初换一台新车。已知各年初的新车购置见下表1，不同役龄车的使用维护费及年末处理价见表2.要求确定该人使用摩托车的最优更新策略，使4年内用于购买、更换及使用维护的总费用为最省。 2021

20、-12-22 表1 单位：万元 第一年第二年第三年第四年年初购置价2.52.62.83.1 表2 单位：万元摩托车役龄（年）01122334年使用维护费0.30.50.81.2该役龄年末处理费21.61.31.1l构造有向图，以点-表示各年初（同时也是上一年年末），弧（i，j）旁的数字表示第i年初买新车到第j年初（即第j-1年末）卖掉时的总支出（i0则这条链叫相对于流f的增广链。l当有增广链存在时，找出l再令0,uminuffciii对对非增广链上的弧iiifuallforfuallforff.l定理1：流f*是最大流当且仅当网络中没有关于f*的增广链。l定理2：在网络st的最大流量等于它的最小割集的容量。4、求网络最大流的标号算法)(s