图论模型(第一讲).ppt

1、数学建模,图论方法专题,图论在数学建模中的应用,建立 OR/MS理论模型的一般步骤,模型准备,模型假设,模型分析,模型构成,模型求解,模型应用,模型检验,下一页,网络优化,图论在数学建模中的应用主要涉及网络优化模型,网络 = 赋(加)权图 网络优化问题, 即在网络中求权最大（或最小）的某类子网络 基本而重要的网络优化问题有: 最小树问题 最短路问题 网络流问题 中国邮递员问题 旅行售货员问题 匹配问题,网络优化模型简介,网络优化,网络优化的例子,1.1 公路连接问题 某个地区有若干个主要城市，现在准备修建高速公路把这些主要城市连接起来，使得其中任何一个城市都可以直接或间接的通过高速公路到达另一

2、个城市，假设已经知道了任意两个城市之间修建高速公路的成本，那么应选择在那些城市修建高速公路使得所花费的成本最少？,1.2 最短路问题 一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地，从甲地到乙地的公路网纵横交错，因此有多种行车路线，那么司机应选择哪条行车路线呢？假设司机的货车运行速度是恒定的，那么这个问题就可转化为从甲地到乙地寻找一条最短路。,网络优化,网络优化,2.图论的基本概念,1) 图的概念,2) 赋权图与子图,3) 图的矩阵表示,4) 图的顶点度,5) 路和连通,1) 图的概念,定义 一个图G是指一个二元组(V(G),E(G)，其中:,其中元素称为图G的顶点.,组成的集合，即

3、称为边集,其中元素称为边.,定义 图G的阶是指图的顶点数|V(G)|, 用,来表示；,2) E(G)是顶点集V(G)中的无序或有序的元素偶对,定义 若一个图的顶点集和边集都是有限集，则称,其为有限图. 只有一个顶点的图称为平凡图，其他的,所有图都称为非平凡图.,定义若图G中的边均为有序偶对,称G为有向,边 为无向边，称e连接 和 ，顶点 和 称,连接,，称 为e的尾，称 为e的头.,若图G中的边均为无序偶对 ，称G为无向图.称,为e的端点.,既有无向边又有有向边的图称为混合图.,常用术语,1) 边和它的两端点称为互相关联.,2)与同一条边关联的两个端点称,为相邻的顶点，与同一个顶点,点关联的两

4、条边称为相邻的边.,3) 端点重合为一点的边称为环，,端点不相同的边称为连杆.,4) 若一对顶点之间有两条以上的边联结，则这些边,称为重边,5) 既没有环也没有重边的图，称为简单图,常用术语,6) 任意两顶点都相邻的简单图,称为完全图. 记为Kv.,7) 若 ， ，且X 中任意两顶点不,，,相邻，Y 中任意两顶点不相邻，则称为二部图或,偶图；若X中每一顶点皆与Y 中一切顶点相邻,称为,完全二部图或完全偶图,记为 (m=|X|,n=|Y|),8) 图 叫做星.,2) 赋权图与子图,定义 若图 的每一条边e 都赋以,一个实数w(e)，称w(e)为边e的权，G 连同边上的权,称为赋权图.,定义 设

5、和 是两个图.,1) 若 ,称 是 的一个子图,记,2) 若 ， ，则称 是 的生成子图.,3) 若 ，且 ，以 为顶点集，以两端点,均在 中的边的全体为边集的图 的子图，称,为 的由 导出的子图，记为 .,4) 若 ，且 ，以 为边集，以 的端点,集为顶点集的图 的子图，称为 的由 导出的,边导出的子图，记为 .,3) 若 ，且 ，以 为顶点集，以两端点,均在 中的边的全体为边集的图 的子图，称,4) 若 ，且 ，以 为边集，以 的端点,集为顶点集的图 的子图，称为 的由 导出的,边导出的子图，记为 .,为 的由 导出的子图，记为 .,3) 图的矩阵表示,邻接矩阵:,1) 对无向图 ，其邻接

6、矩阵 ，其中：,(以下均假设图为简单图:无重边和自回路).,2) 对有向图 ,其邻接矩阵 ,其中：,其中：,3) 对有向赋权图 , 其邻接矩阵 ,对于无向赋权图的邻接矩阵可类似定义.,关联矩阵,1) 对无向图 ，其关联矩阵 ,其中：,2) 对有向图 ，其关联矩阵 ,其中：,4) 图的顶点度,定义 1) 在无向图G中，与顶点v关联的边的数目(环,算两次),称为顶点v的度或次数，记为d(v)或 dG(v).,称度为奇数的顶点为奇点，度为偶数的顶点为偶点.,2) 在有向图中，从顶点v引出的边的数目称为顶点,v的出度，记为d+(v)，从顶点v引入的边的数目称为,v的入度，记为d -(v). 称d(v)

7、= d+(v)+d -(v)为顶点v的,度或次数,定理,的个数为偶数,推论 任何图中奇点,5) 路和连通,定义1) 无向图G的一条途径（或通道或链）是指,一个有限非空序列 ，它的项交替,地为顶点和边，使得对 ， 的端点是 和 ,称W是从 到 的一条途径，或一条 途径. 整,数k称为W的长. 顶点 和 分别称为的起点和终点 ,而 称为W的内部顶点.,2) 若途径W的边互不相同但顶点可重复，则称W,为迹或简单链.,3) 若途径W的顶点和边均互不相同，则称W为路,或路径. 一条起点为 ,终点为 的路称为 路,记为,定义,1) 途径 中由相继项构成子序列,称为途径W的节.,2) 起点与终点重合的途径称

8、为闭途径.,3) 起点与终点重合的的路称为圈(或回路)，长,为k的圈称为k阶圈，记为Ck.,4) 若在图G中存在(u,v)路，则称顶点u和v在图G,中连通.,5) 若在图G中顶点u和v是连通的，则顶点u和v之,之间的距离d(u,v)是指图G中最短(u,v)路的长；若没,没有路连接u和v，则定义为无穷大.,6) 图G中任意两点皆连通的图称为连通图,7) 对于有向图G，若 ，且 有,类似地，可定义有向迹，有向路和有向圈.,头 和尾 ，则称W为有向途径.,例 在右图中：,途径或链：,迹或简单链：,路或路径：,圈或回路：,哥尼斯堡七桥示意图,问题1:七桥问题 能否从任一陆地出发通过每座桥恰好一次而 回

9、到出发点？,图论的基本概念,七桥问题模拟图:,欧拉指出：如果每块陆地所连接的桥都是偶数座，则从任一陆地出发，必能通过每座桥恰好一次而回到出发地。,图论的基本概念,用图论思想求解以下各题,例1、一摆渡人欲将一只狼，一头羊，一篮菜从 河西渡过河到河东，由于船小，一次只能带一物 过河，并且，狼与羊，羊与菜不能独处，给出渡 河方法。,图论的基本概念,下一页,解：,用四维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,

10、0),(1,0,0,0)也是 不允许的，,图论的基本概念,下一页,人在河西：,（1,1,1,1）,（1,1,1,0）,（1,1,0,1）,（1,0,1,1）,（1,0,1,0）,（0,1,0,1）,（0,1,0,0）,（0,0,1,0）,（0,0,0,1）,（0,0,0,0）,人在河东：,以十个向量作为顶点，将可能互相转移的状态 连线，则得10个顶点的偶图。,问题：如何从状态（1,1,1,1）转移到（0,0,0,0）？,方法：从（1,1,1,1）开始，沿关联边到达没有到达 的相邻顶点，到（0,0,0,0）终止，得到有向图即是。,图论的基本概念,例2、考虑中国象棋的如下问题： （1）下过奇数盘棋

11、的人数是偶数个。 （2）马有多少种跳法？ （3）马跳出后又跳回起点，证明马跳了偶数步。 （4）红方的马能不能在自己一方的棋盘上不重复 的跳遍每一点，最后跳回起点？,图论的基本概念,下一页,例3、证明：在任意6人的集会上，总有3人互相认 识，或总有3人互相不认识。,解：以顶点表示人，以边表示认识，得6个顶点 的简单图G。,问题：3人互相认识即G包含K3为子图， 3人互相不认识即G包含（3,0）图为子图。,图论的基本概念,下一页,图论的基本概念,下一页,3最短路问题及算法,最短路问题是图论应用的基本问题，很多实际,问题，如线路的布设、运输安排、运输网络最小费,用流等问题,都可通过建立最短路问题模型

12、来求解.,最短路的定义,最短路问题的两种方法：Dijkstra和Floyd算法 .,1) 求赋权图中从给定点到其余顶点的最短路.,2) 求赋权图中任意两点间的最短路.,2) 在赋权图G中，从顶点u到顶点v的具有最小权,定义 1) 若H是赋权图G的一个子图，则称H的各,边的权和 为H的权. 类似地，若,称为路P的权,若P(u,v)是赋权图G中从u到v的路,称,的路P*(u,v)，称为u到v的最短路,3) 把赋权图G中一条路的权称为它的长，把(u,v),路的最小权称为u和v之间的距离，并记作 d(u,v).,1) 赋权图中从给定点到其余顶点的最短路,假设G为赋权有向图或无向图，G边上的权均非,负若

13、 ，则规定,最短路是一条路，且最短路的任一节也是最短路,求下面赋权图中顶点u0到其余顶点的最短路,Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.,1) 置 ，对 ， ， 且 .,2) 对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3) 若 ，则停止；若 ，则用 i+1 代,替i，并转2).,Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.,1) 置 ，对 ， ， 且 .,2) 对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3) 若 ，则停止；若 ，则用 i+1 代,替i，并转2).,Dijkstra算法: 求G中从顶

14、点u0到其余顶点的最短路.,1) 置 ，对 ， ， 且 .,2) 对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3) 若 ，则停止；若 ，则用 i+1 代,替i，并转2).,Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.,1) 置 ，对 ， ， 且 .,2) 对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3) 若 ，则停止；若 ，则用 i+1 代,替i，并转2).,定义 根据顶点v的标号l(v)的取值途径，使 到v,的最短路中与v相邻的前一个顶点w，称为v的先驱,点，记为z(v), 即z(v)=w.,先驱点可用于追踪最短路径.

15、例5的标号过程也,可按如下方式进行：,首先写出左图带权邻接矩阵,因G是无向图，故W是对称阵,Dijkstra算法：求G中从顶点u0到其余顶点的最短路,设G为赋权有向图或无向图，G边上的权均均非负.,对每个顶点，定义两个标记（l(v)，z(v)），其中:,l(v) ：表从顶点u0到v的一条路的权,z(v) ：v的先驱点，用以确定最短路的路线.,l(v)为从顶点u0到v的最短路的权,算法的过程就是在每一步改进这两个标记，使最终,S：具有永久标号的顶点集.,输入: G的带权邻接矩阵 w(u,v),备用-将求最短路与最短路径结合起来:,算法步骤：,首先写出带权邻接矩阵,例 求下图从顶点u0到其余顶点的

16、最短路,因G是无向图，故W是对称阵,如下图1-1给出一个非负赋权有向图,我们用顶点标号方法，遵循“让d1小的顶点v1优先生长的”原则，逐步生长这棵以v1为根的方向树T，令各顶点的标号如下表1-1所示。 表1-1,取,表1-2,取,有,一般的，如果已迭代至第 步，树 上已有 个顶点， 为在第 步长入树的顶点，则 第 步，对 ,令,对,我们把图1-1按dijkstra算法得到的以 为根的生成树展示 如下：,说明：,图1-2,对图1-2所示树 的生长标号过程，我们列成运算表格如下表1-3所示。,表1-3,如下图,如下图,注意：该题必须以手写的形式完成，步骤可以参考上例，过程要清晰，可以以最后运算表格

17、的形式呈现，中间计算过程可以省略。,注意：该算法输入邻接矩阵的过程中要对称化。以下为对称化的步骤。,（1）若网络图为无向图，可采取如下输入方式，可节省大量输入时间。,（2）若网络图为有向图，必须要局部对称化处理，,例1.2 某公司在六个城市C1,C2,C6中有分公司，从Ci到Cj的直接航程票价记在下述矩阵的(i,j)位置上（ 表示无直接航路）。请帮助该公司设计一张从城市C1到其他城市间票价最低的路线图。,问题求解：因为该问题的网络图为无向图，无需把矩阵局部对称化，可直接在MATLAB命令窗口输入如下程序即可。 M=10000; a(1,:)=0,50,M,40,25,10; a(2,:)=ze

18、ros(1,2),15,20,M,25; a(3,:)=zeros(1,3),10,20,M; a(4,:)=zeros(1,4),10,25; a(5,:)=zeros(1,5),55; a(6,:)=zeros(1,6); a=a+a; d index1index2=opt_tulun_2(a),输出结果如下： d = 0 35 45 35 25 10 index1 = 1 6 5 2 4 3 index2 = 1 6 5 6 1 1,结果分析 d : 存放最短路径的值 index1 : 标号顶点顺序 index2 : 标号顶点索引 则由输出结果可得C1到其他城市间的最低路线图如右图所示,

19、1-1 利用dijkstra算法求v1到其他顶点的最短路，网络图如下所示。,2) 求赋权图中任意两顶点间的最短路,算法的基本思想,（I）求距离矩阵的方法.,（II）求路径矩阵的方法.,（III）查找最短路路径的方法.,Floyd算法：求任意两顶点间的最短路.,举例说明,算法的基本思想,（I）求距离矩阵的方法.,（II）求路径矩阵的方法.,在建立距离矩阵的同时可建立路径矩阵R,（III）查找最短路路径的方法.,然后用同样的方法再分头查找若：,（IV）Floyd算法：求任意两顶点间的最短路.,例 求下图中加权图的任意两点间的距离与路径.,插入点 v1，得：,矩阵中带“=”的项为经迭代比较以后有变化

20、的元素.,插入点 v2，得：,矩阵中带“=”的项为经迭代比较以后有变化的元素.,插入点 v3，得：,插入点 v4，得：,插入点 v5，得：,插入点 v6，得：,故从v5到v2的最短路为8,由v6向v5追溯:,由v6向v2追溯:,所以从v5到v2的最短路径为：,2.1 Floyd算法的MATLAB实现基本步骤,2.1 Floyd算法的案例分析,例2.1 计算图2-1中顶点 到 的最短距离和最短路。,图2-1,2.1 Floyd算法的案例分析,问题求解：直接利用Floyd算法的MATLAB程序求解即可。在MATLAB程序命令窗口输入： a=0 2 8 1 inf inf inf inf; 2 0

21、6 inf 1 inf inf inf; 8 6 0 7 5 1 2 inf; 1 inf 7 0 inf inf 9 inf; inf 1 5 inf 0 3 inf 8; inf inf 1 inf 3 0 4 6; inf inf 2 9 inf 4 0 3; inf inf inf inf 8 6 3 0; P u=f_path(a),2.1 Floyd算法的案例分析,输出结果为： P = 1 2 5 8 u = 11 P ：表示最短路 u : 表示最短路的权和,2.1 Floyd算法的案例分析,结果分析： 1代表v0,2代表v1,5代表v4,8代表v7, 则最短路径为v0 v1 v4

22、 v7 最短权和为11,2.1 Floyd算法的案例分析,例2.2 计算上图中任意两点间最短距离和最短路。,问题求解：直接利用Floyd算法的MATLAB程序求解即可。在MATLAB程序命令窗口输入： a=0 2 8 1 inf inf inf inf; 2 0 6 inf 1 inf inf inf; 8 6 0 7 5 1 2 inf; 1 inf 7 0 inf inf 9 inf; inf 1 5 inf 0 3 inf 8; inf inf 1 inf 3 0 4 6; inf inf 2 9 inf 4 0 3; inf inf inf inf 8 6 3 0; P u=n2sho

23、rf(a,1,8)； 输出结果为： P = 1 2 5 8 u = 11,2.1 Floyd算法的案例分析,由输出结果可见与上例结果相同。该程序可求vivj的最短路，只需输入命令 P u=n2shorf(a,i+1,j+1)；即可 如： P u=n2shorf(a,3,8) P = 3 7 8 u = 5,2.1 Floyd算法的案例分析,结果分析： 3代表v2,7代表v6,8代表v7, 则最短路径为v2 v6 v7 最短权和为5.,（1）求非负赋权图G中某一点到其它各点最短路，一般用Dijkstra标号算法； 注意：Dijkstra标号算法只适用于全部权为非负情况。 （2）求非负赋权图上任意

24、两点间的最短路，一般用Floyd算法. 注意：Floyd算法可以适用于有负权的情况，还能判断是 否有负回路。 （3） 这两种算法均适用于有向赋权图.,二算法适用范围,dijkstra算法与floyd算法比较,例1.1 (设备更新问题)某企业使用一台设备,每年年初,企业都要作出决定,如果继续使用旧的,要付维修费；若购买一台新设备,要付购买费. 试制定一个5年更新计划,使总支出最少. 已知设备在每年年初的购买费分别为11,11, 12,12,13. 使用不同时间设备所需的维修费分别为5,6,8,11,18.,1.4 应用举例,一些初看起来似乎和最短路径问题不相干的问题，有时也可以构建成网络模型而用

25、最短路径算法来求解。,解 设bi 表示设备在第i 年年初的购买费,ci 表示设备使用i 年后的维修费, V=v1, v2, , v6,点vi表示第i 年年初购进一台新设备,虚设一个点v6表示第5年年底. E =vivj | 1ij6.,求v1到v6的最短路问题.,1.4 应用举例,由实际问题可知,设备使用三年后应当更新,因此删除该图中v1到v5 ,v1到v6 ,v2到v6的连线；又设备使用一年后就更新则不划算,因此再删除该图中v1v2 ,v2v3 ,v3v4 ,v4v5 ,v5v6 五条连线后得到,从上图中容易得到v1到v6只有两条路：,v1v3v6和v1v4v6.,而这两条路都是v1到v6的

26、最短路.,1.4 应用举例,1.4 多阶段存储问题,1.4.2 某工厂生产产品需要的原材料分3个阶段，根据供货条件，每次进货量 只能从5,7,10个单位中选一个方案，其运费 分别为120,138和160个单位。第 个阶段对原材料的需求量为 个单位： 已知第一个阶段初工厂仓库已存储该原料3个单位。仓库对该原材料最大库存量允许为6个单位。本阶段进货在本阶段就供应生产的原材料不必进仓库。每阶段末仓库存储的原材料需付存储费，每单位原材料的存储费为1个单位。现要求第3阶段末库存的原材料至少为1个单位。,问在保证生产需求的条件下，每阶段进货采用何种方案，能使运费和存储费总和最少？,解 ：我们作 平面直角坐标系。点 表示第阶段末仓库对该原材料的库存量 简单的符号说明,由每个阶段进货量与库存量之间的关系，可建立如下等式：,则可以设置有向边 的权为：,由此我们可以建立 如图2-1的网络模型。,图 2-1,下面我们来简单讨论一下图2-1的顶点和边是如何设立的。,（1）顶点 表示第一阶段初有原材料库存量3。,（2）,（3）,（4）,可见，图2-1中任意一条 的路径就代表一个三个阶段的进货方案，我们的问题就成为在图2-1中寻求最短路径。