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

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

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

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

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

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

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

7、们都易于它们都易于 用图形的形式直观地描述和表达，数学上用图形的形式直观地描述和表达，数学上 把这种与图相关的结构称为网络把这种与图相关的结构称为网络 （networknetwork）。与图和网络相关的最优化问）。与图和网络相关的最优化问 题就是网络最优化或称网络优化题就是网络最优化或称网络优化 （netwoknetwok optimizationoptimization）问题。）问题。 2021-5-5 图论中的图论中的“图图”并不是通常意义下的几何图形或物并不是通常意义下的几何图形或物 体的形状图体的形状图, , 而是以一种抽象的形式来表达一些确定的而是以一种抽象的形式来表达一些确定的 事

8、物之间的联系的一个数学系统事物之间的联系的一个数学系统. . 定义定义1 一个有序二元组一个有序二元组(v, e ) 称为一个称为一个图图, 记为记为g = (v, e ), 其中其中 v称为称为g的顶点集的顶点集, v , 其元素称为其元素称为顶点顶点或或结点结点, 简称简称点点; e称为称为g的边集的边集, 其元素称为其元素称为边边, 它联结它联结v 中的两中的两 个点个点, 如果这两个点是无序的如果这两个点是无序的, 则称该边为则称该边为无向边无向边, 否则否则, 称为称为有向边有向边. 如果如果v = v1, v2, , vn是有限非空点集是有限非空点集, 则称则称g为为有有 限图限图

9、或或n阶图阶图. 2021-5-5 如果如果e的每一条边都是无向边的每一条边都是无向边, 则称则称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的

10、的始点始点和和终点终点. 该图称为该图称为(n,m)图图 2021-5-5 对于一个图对于一个图g = (v, e ), 人们常用图形来表示人们常用图形来表示 它它, 称其为称其为图解图解. 凡是有向边凡是有向边, 在图解上都用箭头在图解上都用箭头 标明其方向标明其方向. 例如例如, 设设v = v1 , v2 , v3 , v4, e = v1v2 , v1v3 , v1v4 , v2v3 , v2v4 , v3v4, 则则g = (v, e ) 是一个有是一个有4个顶个顶 点和点和6条边的图条边的图, g的图解如下图所示的图解如下图所示. 2021-5-5 一个图会有许多外形不同的图解一个

11、图会有许多外形不同的图解, , 下面两个图表示下面两个图表示 同一个图同一个图g = (v, e )的图解的图解. .其中其中 v = v1 , v2 , v3 , v4, e = v1v2 , v1v3 , v1v4 , v2v3 , v2v4 , v3v4. 这两个图互为这两个图互为同构图同构图, ,今后将不计较这种外形上的差今后将不计较这种外形上的差 别别, ,而用一个容易理解的、确定的图解去表示一个图而用一个容易理解的、确定的图解去表示一个图. . 2021-5-5 有边联结的两个点称为有边联结的两个点称为相邻的点相邻的点, 有一个公共端点的有一个公共端点的 边称为边称为相邻边相邻边.

12、 边和它的端点称为边和它的端点称为互相关联互相关联. 常用常用d(v)表示表示 图图g中与顶点中与顶点v关联的边的数目关联的边的数目, d(v)称为顶点称为顶点v的的度数度数. 对对 于有向图于有向图,还有还有出度出度和和入度入度之分之分. d(v1)= d(v3)= d(v4)=4, d(v2)=2. mvd n i i 2)( 1 握手定理：握手定理： 2021-5-5 定义定义2 若将图若将图g的每一条边的每一条边e都对应一个实数都对应一个实数f (e), 则则 称称f (e)为该边的为该边的权权, 并称图并称图g为为赋权图赋权图(网络网络), 记为记为g = (v, e , f ).

13、定义定义3 任意两点均有通路的图称为任意两点均有通路的图称为连通图连通图. 定义定义4 连通而无圈的图称为连通而无圈的图称为树树, 常用常用t表示树表示树. 2021-5-5 图的矩阵表示图的矩阵表示 邻接矩阵邻接矩阵 邻接矩阵表示了点与点之间的邻接关系邻接矩阵表示了点与点之间的邻接关系. . 一个一个n阶图阶图g的邻接矩阵的邻接矩阵a = (aij )n n , 其中 其中 ., 0 ;, 1 ev ev a ij ij ij 0101 1001 0100 1010 a 无向图无向图g的邻接矩阵的邻接矩阵a是一个对称矩阵是一个对称矩阵. . 0101 1011 0101 1110 a 权矩阵

14、权矩阵 一个一个n阶赋权图阶赋权图g = (v, e, f)的权矩阵的权矩阵a = (aij ) n n , 其中 其中 ., ; ; 0 ),( ev ji evvvf a ij ijji ij 2021-5-5 054 203 70 860 a 无向图无向图g的权矩阵的权矩阵a是一个对称矩阵是一个对称矩阵. . 024 2073 706 4360 a 2021-5-5 关联矩阵（略）关联矩阵（略） 一个有一个有m条边的条边的n阶有向图阶有向图g的的 关联矩阵关联矩阵a = (aij )n m , 其中 其中 若若vi是是ej的始点的始点; 若若vi是是ej的终点的终点; 若若vi与与ej不

15、关联不关联. . , 0 , 1 , 1 ij a 1101100 0110110 0000011 1011001 a 2021-5-5 一个有一个有m条边的条边的n阶无向图阶无向图g的关联矩阵的关联矩阵a = (aij )n m , 其中 其中 若若vi与与ej关联关联; 若若vi与与ej不关联不关联. . , 0 , 1 ij a 110100 101010 011001 000111 a 2021-5-5 定义定义1 设设p(u, v) 是赋权图是赋权图g = (v, e , f) 中从点中从点u到到v 的路径的路径, 用用e(p) 表示路径表示路径p(u, v)中全部边的集合中全部边的

16、集合, 记记 )( )()( pee efpf 则称则称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的的最短路最短路. 2021-5-5 重要性质：重要性质： 若若v0 v1 vm 是是图图g中从中从v0到到vm的最短路的最短路, 则则 1km, v0v1 vk 必为必为g中从中从v0到到vk的最短路的最短路. 即：

17、最短路是一条路，且最短路的任一段也是最短即：最短路是一条路，且最短路的任一段也是最短 路路. 求非负赋权图求非负赋权图g中某一点到其它各点最短路，一般中某一点到其它各点最短路，一般 用用dijkstra标号算法；求非负赋权图上任意两点间的最标号算法；求非负赋权图上任意两点间的最 短路，一般用短路，一般用floyd算法算法. . 这两种算法均适用于有向非负赋权图这两种算法均适用于有向非负赋权图. . 下面分别介绍两种算法的基本过程下面分别介绍两种算法的基本过程. . 2021-5-5 dijkstra算法算法 l求最短路已有成熟的算法：迪克斯特拉求最短路已有成熟的算法：迪克斯特拉 （dijkst

18、radijkstra）算法，其基本思想是按距）算法，其基本思想是按距u u0 0 从近到远为顺序，依次求得从近到远为顺序，依次求得u u0 0到的到的g g各顶各顶 点的最短路和距离，直至所有顶点，算点的最短路和距离，直至所有顶点，算 法结束。为避免重复并保留每一步的计法结束。为避免重复并保留每一步的计 算信息，采用了标号算法。下面是该算算信息，采用了标号算法。下面是该算 法。法。 2021-5-5 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+dsp;lsr+drp,则对p点标号，并 将lsp的值标注在p点旁的小方框内。 l4、重复第3