第7章图论pptppt课件.ppt

第7章 图 论,7.1 问题驱动：最佳灾情巡视路线 根据最新天气预报，某县将要遭遇特大暴雨，为预防洪涝灾情发生，提前做好预防工作，县政府决定抽调各职能部门相关人员组成三个工作组到各乡镇、村进行巡视。假设你是县政府秘书，请设计最佳巡视路线。,1.图论基本知识 2.图论与网络模型 （1）最短路问题 （2）最小生成树 （3）遍历 （4）网络流问题,7.2 图论基本知识,7.2.1 起源 哥尼斯堡是东普鲁士的一座城市，第二次世界大战后划归苏联，也就是现在的加里宁格勒。 普莱格尔河流经此城市，河中有两个孤岛，有七座桥将两岛及岛与河岸相连，如图所示。当时那里的居民热衷于这样一个问题：从一个点出发，能否通过每座桥一次且仅一次，最后回到原来的出发点？,7.2.2 图论中的一些基本概念,1.有序三元组 称为一个图。其中 （1） 是有穷非空集，称为顶点集，其中的元素叫图G的顶点。 （2） 称为边集，其中的元素叫图G的边。 （3） 是从边集到顶点集中的有序或无序的元素偶对的集合的映射，称为关联函数。,2.边有方向的图，称为有向图，边无方向的图称为无向图。连接两个顶点至多有一条边，且一条边的两个顶点不重合的图称为简单图。,3.图 、 ，若 、 ，则称图 是 的子图。如图中的（b）即为图（a）的子图。,6.任意两个顶点之间都有边相连的简单图，称为完备图。 7.如果图 的子图 是一棵树，且 ，则称 是 的生成树。 8.设对图 的每一条边 赋予一个实数 ，称为边的权，则称 为赋权图(或加权图)。连通的赋权图的权和最小的生成树称为的最小生成树 9.有向图 中，每边加权 ，则称这个赋权的有向图为一个网络，记作 , 其中c为容量函数，c(e)称为边e的容量，X与Y为网络的发点集与收点集，X的顶点称作发点或源，Y的顶点称作收点或汇，其余为中间点集。 10.网络 中，若函数 满足 任给 ， (2) 任给 ， ，其中 是 以为终点的边集， 是以 为起点的边集，称 为网络的一个流， 为边的流量。,7.2.3 图的矩阵表示 图的矩阵表示常用的有两种形式：邻接矩阵和关联矩阵。邻接矩阵常用于研究图的各种道路的问题，关联矩阵常用于研究子图的问题。由于矩阵的行列有固定的顺序，因此在用矩阵表示图之前，须将图的结点和边加以编号（定序），以确定与矩阵元素的对应关系。 1.邻接矩阵 设 是一简单有向图，结点集为 。构造矩阵 其中 则称A为有向图G的邻接矩阵。 这个定义也适用于无向图，只须把其中的有向表示换成无向表示就行了。 对于赋权图，其邻接矩阵记作 ，其中：,2.关联矩阵 设 是一个无环的有向图， 。构造矩阵 ，其中 称M是G的关联矩阵。 设 是无环的无向图， 。构造矩阵 ，其中 ,称M为G的关联矩阵。,例1 图的邻接矩阵是,例2 图的关联矩阵如下,7.3 图论与网络模型,7.3.1最短路问题 假设给定连接若干城市的公路网，寻求从指定城市到各城去的最短路线。 设指定城市为图的一个顶点 ，其余任一城市为图的一个顶点 ，连接任意两城市的公路为图的边 ， 为边之长，即在加权图中求 两点之间的路径 ，使该路径上的边权之和最小，即 解决这一问题可以用迪克斯特拉（Dijkstra）算法， 0-1规划法、动态规划法求解。本节主要介绍0-1规划法。,设1为起点， n为终点。引入 表示：若弧(i,j)在最短路上, ；否则， 。Z为目标函数上各弧的路程之和。起点1必定有一条弧出发,所以， 终点n必定有一条弧到达,所以 。 其它点有两种情况： (1)点i不在最短路上，即无进线弧，也无出线弧。满足： ，且 (2)点i在最短路上，即有进线弧，也有出线弧。满足： ，且 改写上述两个等式为：,例3 在图中，点表示城市，现有7个城市，点与点之间的连线表示城市间有道路相连，连线旁的数字表示道路的长度。某人计划从城市A到城市 D去，请设计出路程最短的路线。,解：本题要求城市A到城市 D的最短路线设计方案，城市间路长作为边上的权，问题就转化为两点间的最短路问题，编写LINGO程序求解如下： model: sets: city/A, B1, B2, C1, C2, C3, D/; road(city, city)/ A,B1 A,B2 B1,C1 B1,C2 B1,C3 B2,C1 B2,C2 B2,C3 C1,D C2,D C3,D/: w, x; endsets data: w = 2 4 3 3 1 2 3 1 1 3 4; enddata n=size(city); min=sum(road: w*x); for(city(i) | i #ne# 1 #and# i #ne# n: sum(road(i,j): x(i,j) = sum(road(j,i): x(j,i); sum(road(i,j)|i #eq# 1 : x(i,j)=1; end LINGO软件计算结果如下 Global optimal solution found at iteration: 0 Objective value: 6.000000 Variable Value Reduced Cost X( A, B1) 1.000000 0.000000 X( B1, C1) 1.000000 0.000000 X( C1, D) 1.000000 0.000000 即最短路是, 最短路长为6个单位。,7.3.2最小生成树 欲修筑连接n个城市的铁路，已知i城与j城之间的铁路造价为Cij。设计一个线路图，使修筑铁路的总造价最低。 设计要求铁路将n个城市连通，不要求任意两城直达，但总造价最低。将城市看作点，城市之间欲修的铁路看作边，而城市间的铁路造价作权，则构成一个赋权连通图，该问题就是在赋权连通图中求权值最小的连通子图，即边权之和最小的生成树。数学模型 。 解决这类构造最小生成树问题的算法有Kruskal算法、Prim算法、破圈法、整数规划法。本节主要介绍整数规划法。,整数规划法 假设 表示点i到点j的权，当两个节点没有线路相通时， 。 设0-1变量,当 ,表示从节点i到节点j的边在树中;当 ,表示从节点i到节点j的边不在树中。 目标函数: 约束条件： （1）假设根节点为 ，根节点只有出去的线路，且出去的线路不少于1条，但没有进来的线路,有 ； （2）其它节点（除根节点外）必须有且只有一条线路进来，即 。 仅仅上述条件还不够，因为一棵树是连通且不能有圈的。引入变量 ，其中 ，为避免形成圈，约束,综上，求最小生成树模型,例4 某地区共有1个城市（标记为1）和9个乡镇（标记为2-10）组成，该地区不久将用上天然气，其中城市1含有井源。现要设计一供气系统，使得从城市1到每个乡镇（2-10）都有一条管道相通，并且铺设的管子的量尽可能的少。下表给出了城镇之间的距离。,解：本题要求设计一条管道使得城市1到每个乡镇（2-10）都相通，但总长最短。将城市、乡镇看作点，之间连线看作边，之间距离作边权，构成一个赋权连通图。求使各点相互连通，总长最短的连线，即权和最小的生成树。 编写LINGO程序求解如下： model: sets: city/110/:u; link(city, city): distance, x; endsets data: distance = 0 8 5 9 12 14 12 16 17 22 8 0 9 15 16 8 11 18 14 22 5 9 0 7 9 11 7 12 12 17 9 15 7 0 3 17 10 7 15 15 12 16 9 3 0 8 10 6 15 15 14 8 11 17 8 0 9 14 8 16 12 11 7 10 10 9 0 8 6 11 16 18 12 7 6 14 8 0 11 11 17 14 12 15 15 8 6 11 0 10 22 22 17 15 15 16 11 11 10 0; enddata n=size(city); min=sum(link: distance*x);,for(link : bin(x); for(city(k) |k #gt# 1 : sum(city(i)| i #ne# k: x(i,k)=1; for(city(j)| j #gt# 1 #and# j #ne# k: u(j) = u(k) + x(k,j) - (n-2)*(1-x(k,j) + (n-3)*x(j,k); ); sum(city(j)| j #gt# 1: x(1,j)=1; for(city(k) |k #gt# 1 :u(k)=n-1-(n-2)*x(1,k); ); end 在上述程序中，利用变量(u)来保证所选的边不构成圈。计算结果如下： Global optimal solution found at iteration: 34 Objective value: 60.00000 Variable Value Reduced Cost X( 1, 2) 1.000000 8.000000 X( 1, 3) 1.000000 5.000000 X( 3, 4) 1.000000 7.000000 X( 3, 7) 1.000000 7.000000 X( 4, 5) 1.000000 3.000000 X( 5, 8) 1.000000 6.000000 X( 7, 9) 1.000000 6.000000 X( 9, 6) 1.000000 8.000000 X( 9, 10) 1.000000 10.00000 连接这10个城镇的最小距离为60公里。,7.3.3 遍 历 一、中国邮路问题 一位邮递员从邮局选好邮件去投递，然后返回邮局，他必须经过所负责投递的每条街道至少一次，为他设计一条投递路线，使得他行程最短。这个问题称为中国邮路问题。 定义 设G=(V,E)是连通无向图 （1）经过G的每边正好一次的回路称为欧拉回路。 （2）存在欧拉回路的图称为欧拉图。 （3）经过G的每边正好一次的道路称为欧拉道路。 左图中 是一条欧拉道路，但无欧拉回路，所以不是欧拉图。右图存在欧拉回路 ，所以是欧拉图。,定理 连通图G是欧拉图当且仅当G不含奇次顶点。 将投递区的街道用边表示，街道的长度用边权表示，邮局街道交叉口用点表示，则一个投递区构成一个赋权连通无向图中国邮递员问题转化为：在一个非负赋权连通图中，寻求一个权最小的回路这样的回路称为最佳回路。 对于欧拉图，可由Fleury算法求出图的一个欧拉回路即是最佳回路。 对于无向加权连通图，设 为从 i到 j 经过的次数，则得如下数学模型,二、推销员问题 一名推销员准备前往若干城市推销产品，如何为他设计一条旅行路线，使其从驻地出发，经过每个城市至少一次，最后返回出发地的总行程最小？这个问题称为推销员问题。 若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离（或时间、费用），于是推销员问题就转化为在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题。 定义 设G=(V,E)是连通无向图 （1）经过G的每个顶点正好一次的圈，称为G的哈密尔顿圈或H圈。 （2）含H圈的图称为哈密尔顿图或H图。,定义 在加权图G=(V,E)中， （）权最小的哈密尔顿圈称为最佳H圈。 （）经过每个顶点至少一次的权最小的闭通路称为最佳推销员回路。 一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，同样最佳推销员回路也不一定是最佳哈密尔顿圈。 定理 在加权图G=(V,E)中，若对任意x,y,z V，zx,zy,都有 w(x,y) w(x,z)+w(z,y) ，则图G的最佳H圈也是最佳推销员回路。 最佳推销员回路问题可转化为最佳H圈问题方法是由给定的图G=(V,E)构造一个以V为顶点集的完备图G=(V,E)，E的每条边(x,y)的权等于顶点x与y在图中最短路的权。即：w(x,y)=mindG(x,y) 定理 加权图G的最佳推销员回路的权与G的最佳H圈的权相同。,加权图中求最佳推销员回路问题就转化为再完备加权图中寻求最佳H圈问题，而求H圈至今仍无有效算法。我们常采用近似算法，如二边逐次修正法，或建立数学模型用软件求解。设当从 到 时， ，否则， ， ，则得如下模型,例5 某公司计划在某地区作广告宣传，各城镇之间的距离如表,推销员从城市1出发，经过各个乡镇，再回到城市1，为节约开支，公司希望推销员走过这10 个城镇的总距离最少。,解：本题是最佳推销员问题，编写LINGO程序如下 model: sets: city/110/:u; link(city, city): distance, x; endsets data: distance = 0 8 5 9 12 14 12 16 17 22 8 0 9 15 16 8 11 18 14 22 5 9 0 7 9 11 7 12 12 17 9 15 7 0 3 17 10 7 15 15 12 16 9 3 0 8 10 6 15 15 14 8 11 17 8 0 9 14 8 16 12 11 7 10 10 9 0 8 6 11 16 18 12 7 6 14 8 0 11 11 17 14 12 15 15 8 6 11 0 10 22 22 17 15 15 16 11 11 10 0; enddata n=size(city); min=sum(link: distance*x); for(link : bin(x); for(city(k) :sum(city(i)| i#ne# k: x(i,k)=1; sum(city(j)| j #ne# k: x(k,j)=1;);,for(city(i): for(city(j) | j #gt# 1 #and#i #ne# j : u(i)-u(j)+n*x(i,j)=n-1);); for(city(i):u(i)=n-1); for(link : bin(x); end 变量u是用来保证所选的边除第1点外不构成圈。 LINGO软件计算结果如下： Global optimal solution found at iteration: 90 Objective value: 73.00000 Variable Value Reduced Cost X( 1, 2) 1.000000 8.000000 X( 2, 6) 1.000000 8.000000 X( 3, 1) 1.000000 5.000000 X( 4, 3) 1.000000 7.000000 X( 5, 4) 1.000000 3.000000 X( 6, 9) 1.000000 8.000000 X( 7, 10) 1.000000 11.00000 X( 8, 5) 1.000000 6.000000 X( 9, 7) 1.000000 6.000000 X( 10, 8) 1.000000 11.00000 旅行商经过10 个城镇的最短距离为73公里，次序,7.3.4 网络流问题 现实生活中存在很多网络，铁路网、通信网、运输网等。把商品从生产地运往市场，交通网上每个路段能力给定的条件下，设计一个运输方案，使得运输最快。 在单源单汇具有容量上限的网络中求从源到汇的流量最大的流。求网络最大流中有Ford-Fulkerson算法，但是网络最大流也是一个线性规划问题。其数学模型如下：其中1发点，表示收点。 最小费用最大流问题数学模型,例6 现需要将城市s的石油通过管道运送到城市t，中间有4个中转站v1v2v3v4 , 城市与中转站的连接，由于输油管道的长短不一或地质等原因，使每条管道上运输费用也不相同，因此，除考虑输油管道的最大流外，还需要考虑输油管道输送最大流的最小费用，如图示是带有运费的网络，其中第1个数字是网络的容量，第2个数字是网络的单位运费。,解： 本例所提出的问题就是最小费用最大流问题，即考虑网络在最大流情况下的最小费用，先求网络最大流，编写LINGO程序如下： model: sets: nodes/s,1,2,3,4,t/; links(nodes, nodes)/ s,1 s,2 1,2 1,3 2,4 3,2 3,t 4,3 4,t/: c, f; endsets data: c = 8 7 5 9 9 2 5 6 10; enddata max = f(s,t); for(links (i,j) :f(i,j)=c(i,j); for(nodes(i):sum(links(j,i):f(j,i)=sum(links(i,j):f(i,j); end LINGO软件的计算结果如下: Global optimal solution found at iteration: 6 Objective value: 14.00000 Variable Value Reduced Cost FLOW 14.00000 0.000000 F( S, 1) 7.000000 0.000000 F( S, 2) 7.000000 0.000000 F( 1, 2) 2.000000 0.000000 F( 1, 3) 5.000000 0.000000 F( 2, 4) 9.000000 -1.000000 F( 3, 2) 0.000000 0.000000 F( 3, T) 5.000000 -1.000000 F( 4, 3) 0.000000 1.000000 F( 4, T) 9.000000 0.000000,在网络最大流的限制下，求输油管道输送最大流的最小费用，编写LINGO程序如下： model: sets: nodes/s,1,2,3,4,t/; links(nodes, nodes)/ s,1 s,2 1,2 1,3 2,4 3,2 3,t 4,3 4,t/: c, u, f; endsets data: c= 8 7 5 9 9 2 5 6 10; u= 2 8 5 2 3 1 6 4 7; enddata f(s,t)=14; min=sum(links:u*f); for(links(i,j):f(i,j)=c(i,j); for(nodes(i):sum(links(j,i):f(j,i)=sum(links(i,j):f(i,j); end LINGO软件的计算结果如下: Global optimal solution found at iteration: 3 Objective value: 205.0000 Variable Value Reduced Cost F( S, 1) 8.000000 -1.000000 F( S, 2) 6.000000 0.000000 F( 1, 2) 1.000000 0.000000 F( 1, 3) 7.000000 0.000000 F( 2, 4) 9.000000 0.000000 F( 3, 2) 2.000000 -2.000000 F( 3, T) 5.000000 -7.000000 F( 4, T) 9.000000 0.000000 因此，最大流的最小费用是205单位。,7.4驱动问题建模求解 7.4.1 问题分析 题中给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线。从若干可能的安排或方案中寻求最优安排或方案，数学上把这种问题称为最优化或优化问题。 将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为推销员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次再回到点O，使得总权（路程或时间）最小。本题即推销员问题的延伸多推销员员问题。 7.4.2 假 设 1汽车在路上的速度总是一定，不会出现抛锚等现象； 2巡视当中，在每个乡镇、村的停留时间一定，不会出现特殊情况而延误时间； 3每个小组的汽车行驶速度完全一样； 4分组后，各小组只能走自己区内的路，不能走其他小组的路，除公共路外。 5村镇被巡视一次后，再次经过时不会停留。,7.4.3模 型 的 建 立 与 求 解 将公路网图中，每个乡（镇）或村看作图中的一个节点，各乡（镇）、村之间的公路看作图中对应节点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化为在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次再回到O点，使得总程最小，此即最佳推销员回路问题。 在加权图G中求最佳推销员回路问题是NP完全问题，我们采用一种近似算法求出该问题的一个近似最优解，来代替最优解，算法如下： 1.用图论软件求出G中任意两个顶点间的最短路，构造出完备图 ， ， ； 2.输入图的一个初始H圈； 3.随机搜索出中若干个H圈； 4.对第2、3步所得的每个H圈，用二边逐次修正法进行优化，得到近似最佳H圈； 5.在第4步求出的所有H圈中，找出权最小的一个，此即要找的最佳H圈的近似解。 由于二边逐次修正法的结果与初始圈有关，故本算法第2、3步分别用两种方法产生初始圈，以保证能得到较优的计算结果。,具体求解如下： 此问题是多个推销员的最佳推销员回路问题，即在加权图G中求顶点集V的划分 ，将G分成n个生成子图 ，使得 （1）顶点 i=1，2，3n （2） （3） ，其中 为 的导出子图中的最佳推销员回 路， 为 的权，i，j=1，2，3n （4） 定义 称为分组的实际均衡度。 为最大容许均衡度。,从O点出发去其它点，要使路程较小应尽量走O点到该点的最短路。故用图论软件包求出O点到其余顶点的最短路，这些最短路构成一棵树，将从O点出发的树枝称为干枝，见下图，从图中可以看出，从O点出发到其它点共有6条干枝，它们的名称分别为，。,根据实际工作的经验及上述分析，在分组时应遵从以下准则： 一、尽量使同一干枝上及其分枝上的点分在同一组； 二、应将相邻的干枝上的点分在同一组； 三、尽量将长的干枝与短的干枝分在同一组。 根据上述分组准则，我们找到两种分组形式如下： 分组一：（，），（，），（，） 分组二：（，），（，），（，） 显然分组一的方法极不均衡，故考虑分组二。 对分组二中每组顶点的生成子图，求出近似最优解及相应的巡视路线。使用算法时，在每个子图所构造的完备图中，取一个尽量包含图中树上的边的H圈作为第2步输入的初始圈。分组二的近似解见下表 。,该分组的均衡度 ，此分法的均衡性很差。 为改善均衡性，将第组中的顶点C，2，3，D，4分给第组（顶点2为这两组的公共点），重新分组后的近似最优解见下表。 因该分组的均衡度 所以这种分法的均衡性较好。,习 题 1.从北京（Pe）乘飞机到东京(T)、纽约(N)、墨西哥城(M)、伦敦(L)、巴黎(Pa)五城市做旅游，每城市恰去一次再回北京，应如何安排旅游线，使旅程最短？各城市之间的航线距离如下表。,2.图的S、A、B、C、D、E、T分别代表7个村镇，它们之间的连线代表各村镇间的道路情况，连线旁的数字（权）代表各村镇间的距离。现要求沿道路架设电线，使上述村镇全部通上电，应如何架设使总的线路长度最短。 3.张先生打算购买一辆新轿车，轿车的售价是12万元人民币。轿车购买后，每年的各种保险费养护费等费用由表1所示。如果在5年之内，张先生将轿车售出，并再购买新年。5年之内的二手车销售价由表2所示。请你帮助张先生设计一种购买轿车的方案，使5年内用车的总费用最少。,4求下列网络的最小费用最大流，其中括号中第一个数字是容量，第二个数字是单位费用。 5.邮递员投递区域的街道分布如图所示，图中数字为街道长度（单位为公里）。“O”为邮局所在地，试为邮递员设计一条最佳的投递路线，使其每天完成投递任务并返回邮局所经历的路线最短。,