1、1数学建模中的图论方法一、引言我们知道，数学建模竞赛中有问题 A 和问题 B。一般而言，问题 A 是连续系统中的问题，问题 B 是离散系统中的问题。由于我们在大学数学教育内容中，连续系统方面的知识的比例较大，而离散数学比例较小。因此很多人有这样的感觉，A 题入手快，而 B 题不好下手。另外，在有限元素的离散系统中，相应的数学模型又可以划分为两类，一类是存在有效算法的所谓 P 类问题，即多项式时间内可以解决的问题。但是这类问题在 MCM 中非常少见，事实上，由于竞赛是开卷的，参考相关文献，使用现成的算法解决一个 P 类问题，不能显示参赛者的建模及解决实际问题能力之大小；还有一类所谓的 NP 问题
2、，这种问题每一个都尚未建立有效的算法，也许真的就不可能有有效算法来解决。命题往往以这种 NPC 问题为数学背景，找一个具体的实际模型来考验参赛者。这样增加了建立数学模型的难度。但是这也并不是说无法求解。一般来说，由于问题是具体的实例，我们可以找到特殊的解法，或者可以给出一个近似解。图论作为离散数学的一个重要分支，在工程技术、自然科学和经济管理中的许多方面都能提供有力的数学模型来解决实际问题，所以吸引了很多研究人员去研究图论中的方法和算法。应该说，我们对图论中的经典例子或多或少还是有一些了解的，比如，哥尼斯堡七桥问题、中国邮递员问题、四色定理等等。图论方法已经成为数学模型中的重要方法。许多难题由
3、于归结为图论问题被巧妙地解决。而且，从历年的数学建模竞赛看，出现图论模型的频率极大，比如：AMCM90B扫雪问题；AMCM91B寻找最优 Steiner 树；AMCM92B紧急修复系统的研制( 最小生成树)AMCM94B计算机传输数据的最小时间( 边染色问题)CMCM93B足球队排名(特征向量法)CMCM94B锁具装箱问题(最大独立顶点集、最小覆盖等用来证明最优性)CMCM98B灾情巡视路线(最优回路)等等。这里面都直接或是间接用到图论方面的知识。要说明的是，这里图论只是解决问题的一种方法，而不是唯一的方法。本文将从图论的角度来说明如何将一个工程问题转化为合理而且可求解的数学模型，着重介绍图论
4、中的典型算法。这里只是一些基础、简单的介绍，目的在于了解这方面的知识和应用，拓宽大家的思路，希望起到抛砖引玉的作用，要掌握更多还需要我们进一步的学习和实践。2二、基本概念和性质首先给出图论中的一些基本概念。1一个图 G 由一个顶点集 V 和一个边的集 E 组成。E 中每个元素 e 是连接顶点集 V 中两个顶点 u 和 v 的边，称 e 与 u，v 关联。我们规定连接两个顶点 u、v 至多有一条边，且一条边的两个顶点不重合，这种图称为简单图。2顶点集为 V，边集为 E 的图 G 通常记为 G=（V ，E ） 。图 G1=（V 1，E 1）称为 G 的子图，如果 V1 V， E1 E。3顶点 v
5、的度(或“次”)是指与 v 相关联的边的个数。图 G 的度数之和为边数的两倍。4若图 G 中任意两个顶点 u、v 之间都存在连接它们的路，称 G 为连通图。5W=v0e1v1e2ekvk，其中 eiE，vjV，ei 与 vi-1，vi 关联，称 W 是图 G 的一条道路。v0 是起点，vk 是终点；各边相异的道路叫做行迹，各顶点相异的道路叫做轨道；起点和终点重合的道路为回路；起点和终点重合的轨道为圈；包含图中每条边的回路称为 Euler 回路；含 Euler 回路的图称为 Euler 图。6一个无圈的连通图称为树。树是最简单而最重要的一类图。树有下列重要性质：性质：1)在树中去掉任意一条边，所
6、得的图是不连通的。2)在树中任意两个不相邻的顶点 u、v 之间添加一条新的边，所得的图恰有一个圈。下述定理是树的判断定理：定理：若图 G 具有下列性质中的两条，则它是树，且也具有第三条性质。(1)G 是连通图；(2)G 没有圈；(3)G 的顶点数 =G 的边数+1。7如果图 G=（V，E）的子图 Gt=（V t，E t）是一个树，且 Vt=V，称 G t 是 G 的生成树。G连通的充要条件是 G 有生成树。生成树一般而言数量很大。8设对图 G=（V，E）的每一条边 e 赋予一个实数 W（ e） ，称为 e 的权，G 称为赋权图(加权图)。假设 G 是连通的赋权图，要找 G 的连通子图 G *=
7、（V，E*） ，使得 W（G*）= 为最Ee)(小。显然 G*应为 G 的一个生成树。G 的权最小的生成树称为 G 的最小生成树。三、算法介绍31 最短轨道问题3背景：给定连接若干城市的铁路网，寻求从指定城市 v0 到各城 v 去的最短道路。数学模型：图 G 为一赋权图，对任给的 vV(G)，寻求轨道 P(v0,v)，使得W(P(v0,v)=minW(P),P 取自所有 v0 到 v 的轨道集合其中 W(P)是轨道 P 上各边权之和。这一问题可用迪克斯特拉(Dijkstra)算法解决。基本思想：从起点 v0 开始，逐步寻找到达各点的最短路，在每一步都对顶点记录一个数，称之为该点的标号，它表示
8、v0 到该点的最短距离的上界，或就是 v0 到该点的最短距离。实际上每一步都通过把至少一个具有 T 标号的点变成 P 标号( 即把一个不是最短距离标号的顶点变成是最短距离标号的顶点)，这样最多经过 |V(G)|-1 步就可完成。步骤：记 l(v)为 v0 到 v 的距离。(1) l(v0)=0，l(v) = ，(vv0)；S0=v0，i=0 。(2) 对 vSi，minl(v)，l(vi)+w(viv)代替 l(v)；这样找到点 vi1 使得 l(v)取最小值，v(i1)(Si的余集)。令 S(i1)Siv(i+1)。(3) i=|V(G)|-1 时停止，否则， i+1，转到(2)。实例：CM
9、CM94A公路选址问题。32 求最小生成树1克罗斯克尔(Kruskal)算法(1956 年)，俗称“避圈法”背景：筑路选线问题 欲修筑连接 n 个城市的铁路，已知 i 城与 j 城之间的铁路造价为 Cij。设计一个线路图，使总造价最低。分析：选线问题的数学模型是在连通加权图上求权最小的连通生成子图。显然，权最小的连通生成子图是一个生成树，即求取连通加权图上的权最小的生成树，这就归结为最小生成树问题。这个问题可由克罗斯克尔(Kruskal)算法解决。思路：从“边”着手选最小生成树。步骤：设 G 为由 m 个节点组成的连通赋权图。(1) 先把 G 中所有的边按权值大小由小到大重新排列，并取权最小的
10、一条边为树 T 中的边。即选e1E，使得 w(e1)min。(2) 从剩下的边中按(1) 中的排列取下一条边。若该边与前面已取进 T 中的边构成一个回路，则舍弃该边，否则也把它取进 T 中。若 e1，e2 ，ei 已经选好，则从 Ee1 ，e2，ei中选取ei1，使得 Ge1，e2 ，ei ，ei+1 中无圈，且 w(ei+1)=min。(3) 重复步骤(2)，直到 T 中有 m1 条边为止。则 T 为 G 的最小生成树。4该算法的复杂度为 O(eloge)，其中 e 是图 G 中的边数。2普莱姆(Prim)算法思路：从点入手来选边步骤：(1) 在图 G 中任取一个节点 vi1，并放入 T 中
11、。(2) 令 SV(G)/V(T)，V(G)、V(T)分别是 G、T 的节点集。(3) 在所有连接 V(T)节点与 S 节点的边中，选出权值最小的边(u0,v0)，即w(u0,v0)=minw(u,v)|uV(T), vS。(4) 将边(u0,v0)放入 T 中。(5) 重复步骤(2)(4) ，直到 G 中节点全部取完。该算法的复杂度为 O(n2)，其中 n 为图 G 的节点数。31975 年管梅谷提出的“破圈法”33 Steiner 生成树实际背景：在已有网络上选择连通几个城市的最廉价交通或通讯网。数学模型：从已知的加权连通图上求取最小的树状子图，使此树包含指定的顶点子集。第一个的边长为 ，
12、第二个的边长为 1，总费用第二个更少。3分析：与传统的最小生成树相比，这里可以引入若干“虚拟站”并构造一个新的 Steiner 树，这样可以降低由一组站生成的传统的最小生成树所需的费用(降低的费用大概为 13.4%)。而且为构造一个有 n 个顶点的网络的费用，最低的 Steiner 树决不需要多于(n2) 个虚设站。当然，有时最小Steiner 生成树与最小生成树相同。寻求最小 Steiner 生成树的算法有 Melzak 算法(1961 年)，但是这是一个指数时间的算法，现在没有多项式时间的算法，换句话说它是一个 NP 问题。而且，这里的要求是用直折线代替欧氏直线距离，因而不能利用直接的算法
13、。所以在解决这样的问题的时候，为减少运算的时间，理论上的分析是必要的：比如树的长度的下界，Steiner 树的存在性，虚设站的位置等等。常用的算法还包括穷举法、模拟退火法等。Melzak 算法：其基础是 3 点 steiner 树，即 3 点 Fermat 问题的几何作图法。参考 2，Page375。模拟退火法原理：模拟退火法(Simulated annealing, SA)是模拟热力学中经典粒子系统的降温过程，来求解极值问题。当孤立粒子系统的温度以足够慢的速度下降时，系统近似处于热力学平衡状态，最后系统将达到本身的最低能量状态，即基态，这相当于能量函数的全局极小点。其步骤如下(也5称为 Me
14、tropolis 过程)：（1） 给定初始温度 T0，及初始点，计算该点的函数值 f(x)。（2） 随机产生扰动 x，得到新点 x=x+x，计算新点函数值 f(x),及函数值差 f=f(x)-f(x)。（3） 若 f0，则接受新点，作为下一次模拟的初始点；（4） 若 f0，则计算新点接受概率： ，产生 0，1区间上均匀分布的伪随机数 r,r0,1 ，如果 p(f)r，则接受新点作为下一次模拟的初始点；否则放弃新点，仍取原来的点作为下一次模拟的初始点。模拟退火法实例：1 MCM91B(通讯网络中的极小生成树) 是一个求 STEINER 生成树问题，参见工科数学专辑Page：7078。2、CMCM
15、 97A 题97 年全国大学生数模竞赛 A 题“零件的参数设计”，可以归结为非线性规划模型，由于目标函数很复杂，且又是一个多维函数，因此求解比较困难，为应用模拟退火法进行求解，将 7 个自变量的取值范围进行离散化，取步长为 0.0001，这样，所有 7 个变量取值就组成了一个极为庞大的离散空间, 而这个问题变成组合优化模型。这个问题算法的状态调整规则是：每次从 7 个自变量中随机选取 1-4 个，让选取的自变量随机移动，考虑选取的自变量在两个方向移动组合，从中选取最佳的作为候选者，自变量移动的距离随着温度的降低而减少，为避免陷入局部极小，可以从多个随机选取的初始值开始计算，算法的其它步骤同上。
16、3、CMCM 98B 题98 年全国大学生数学建模竞赛 B 题“ 水灾巡视问题”，是一个推销员问题，本题有 53 个点，所有可能性大约为 exp(53),目前没有好方法求出精确解，既然求不出精确解，我们使用模拟退火法求出一个较优解，将所有结点编号为 1 到 53，1 到 53 的排列就是系统的结构，结构的变化规则是：从 1 到 53 的排列中随机选取一个子排列，将其反转或将其移至另一处，能量 E 自然是路径总长度。具体算法描述如下：步 1： 设定初始温度 T，给定一个初始的巡视路线。步 2：步 3 -8 循环 K 次步 3：步 4-7 循环 M 次6步 4：随机选择路线的一段步 5：随机确定将
17、选定的路线反转或移动，即两种调整方式：反转、移动。步 6：计算代价 D，即调整前后的总路程的长度之差步 7：按照如下规则确定是否做调整：如果 D0，则按照 EXP(-D/T)的概率进行调整步 8：T*0.9T ，降温34 Euler 回路设 G 是一个图，若存在这样一条回路，使它经过图中的每条边且只经过一次又回到起始节点，就称这样的回路为 Euler 回路。背景：哥尼斯堡七桥问题定理：对连通图 G，下列条件是相互等价的：(1) G 是 Euler 图；(2) G 的每个节点的度数都是偶数；(3) G 的边集可以分解为若干个回路的并。对有向图，出度入度。算法：弗罗莱(Fleury)算法(1921
18、)(1) 任给 v0V(G)，Rv0(2) 设路 Rv0e1v1e2v2eivi 已选定，则从 E(G)e1,e2,ei中选边 ei+1，且满足：ei+1 与 vi 相连；除非已无选择，ei+1 不要选 E(Gi)E(G) e1,e2,ei 中的桥(注：桥，去掉之后图不连通)(3) 重复(2)，直到不能再选为止实例：MCM90B 铲雪问题中单车道单车扫雪地图是 Euler 图的情形。说明：如果图 G 不是 Euler 图，也就是说不存在 Euler 回路，这时候求解就比较困难。求解前需要做一些处理，添加一个边子集 E1，E1G G1 构成一个 Euler 图，然后再寻找 Euler 回路。注意
19、图 G 不是 Euler 图时，必有偶数个奇数度的节点，可以给这些节点两两配对，求两点间的最短路，将这些最短路画在一起构成附加边子集 E1。这里的困难在于：奇数度的节点较多时，配对方案也多。735 网络中的最大流背景：把商品从生产地运往市场，交通网上每个路段能力给定的条件下，设计一个运输方案，使得运输最快。网络：规定起点 s、中间点和终点 t 的赋权图。数学模型：有向图 G，每边加权 c(e)，称 c(e)为边 e 之容量，设 G 为严格的有向图，则称这个有向的加权图为一个网络。映射 f：E(G)R 满足(c1) 任给 eE(G)，0f(e)c(e) ；(c2) 任给 vV(G)s,t， 0；
20、其中 a(v)是以 v 为头的边集( 流进)，b(v)(vef)(vef是以 v 为尾的边集(流出) ，即除起点和终点外，各节点流入量总和等于流出量总和。称 f(e)为流函数，称F )(tef)(tef为流量。我们的目标是寻找一个流函数 f，使其流量最大。1956 年，福特(Ford) 和福尔克逊(Fulkerson)提出了求最大流的算法。最大流最小割定理：流过网络的最大流量等于最小割集的容量。2F 算法：(1) 对每边 e，选 f(e)0；(2) 标志顶 s，其它顶未标志；(3) 选可“向前标志”或可“向后标志”的顶 v。若无此种顶可选时，停止，现流函数即为最大流；若有此种顶可选时，则得到新
21、的标志顶 v 及标志边 e。若 vt，则转(4)；否则转(3) 。(4) 设已得标志之轨为(此轨为无向的 )se1v1e2v2ett，从 t 开始沿此轨逆行，令，)(min1il若 ei 是前进边，即在有向图中 eivi1vi(sv0，tvl )，则 f(ei)f(ei) ；若 ei 是后退边，即在有向图中 eivivi1，则 f(ei)f(ei) ；(5) 转(2)。向前和向后标志的含义如下：若 euv，u 已有标志，v 没有标志，且 c(e)f(e)，则称通过边e 可以向前标志顶点 v，且规定(e) c(e) f(e)，得到标志边 e。若 evu，u 已有标志，v 没有标志，且 f(e)0
22、，则称通过边 e 可以向后标志顶 v，规定(e)f(e)，且得到标志边 e。(e) 的含义是8边 e 上可以增载的上界。说明：1 如果每边之容量 c(e)都是有理数，则 2F 算法在有限步之内可以求得最大流。2 容量有上下界的网络，需要构造附加网络。3.6 最小费用 最大流问题这是在上述讨论的基础上增加关于使费用最小的目标。解决的办法是采用“对偶法原理”：1 先用上面讨论的方法求出网络的最大流量；2 然后在原始的网络中福德算法找出从起点 v s 到终点 v t 的最短路线最短增广链；3 在该增广链上找出最大调整量，并调整流量得到一个可行流，则此可行流的费用最小。如果此时流量等于最大流量，那么它
23、就是最小费用最大流；否则应继续调整。应用：运输问题，如 CMCM2000B 钢管的采购和运输问题。说明：1这里的介绍只是图论中的一部分内容，更多的需要我们进一步学习。2算法都是描述性的，有些可以找到现成的程序，但是最好是自己实现。3这里的例子只是解决问题的一种方法，不是唯一的方法。4注意实际应用中直接利用所给算法解决问题的情况很少，通常只是解决问题的一部分，而且需要建立模型，把实际问题用图论术语描述出来。所以要善于利用这里的工具。其它方面的应用，如工序问题，最大独立集，最小覆盖集，邮递员问题，规划审核技术，关键轨道方法，可靠通信网络的构造问题，班级人员分配等等。37 工序问题统筹方法是组织生产
24、计划的方法，它用网络图表达生产和工程的进度，计算各项工序的有关时间参数。一项工程总是由许多相互独立的工序组成的，各道工序之间有一定的先后次序。完成每道工序需要的时间（不妨设单位为小时）称为工序的长度。因此我们可以用一个各条边有方向的图（称为有向图）表示各项工序之间的互相依赖关系。以一条有向变来表示一道工序，有向边的权即为此工序的长度，有向边的起点和终点分别表示相应工序的开工和完工，称为事项，9前接工序和完工事项即为后续工序和开工事项。实例：上海 MCM91B四、网络规划的应用1最小生成树网络规划例 1 例 1求下图的一个最小生成树。解：首先取 G 1=（V 1，E 1） ，V 1=v0，E 1
25、=其次，一端属于 V1，一端不属于 V1 的最短边是 v0v1，所以有G2=（ V2，E 2） ，V 2=v0，v 1，E 2=v0v1。现在，一端属于 V2，一端不属于 V2 的最短边是 v1v3，所以有G3=（ V3，E 3） ，V 3=v0，v 1，v 3，E 3=vov1，v 1v3。类似做下去，最后得最小生成树的边为：v0v1，v 1v3，v 2v3，v 2v5，v 5v6，v 4v6。 2存储粮食模型网络规划例 2例 2某乡有七个村 A1， A2，.，A7，需储存粮食数量分别为 50，75，62，40，100，80，35吨。各村之间有公路连通，如图。现要选择某村建立仓库储存所有粮食
26、，问应选择何处最好？解：图上连结两村的边所注的数字表示该段公路的千米数。我们的目的是选择仓库的位置使运粮的吨千米数最小。首先比较 A1 和 A2 两处。在比较这两个村庄时，因为仓库无论建在 A1 或A2，其他各村的粮食都要先运到 A2，所以我们可认为除 A1 外各村的粮食都集中在 A2，共 357吨。现在事情很明显，仓库建在 A2 时需把 50 吨粮食运 3 千米到 A2，建在 A1 时需把 357 吨粮食运 3 千米到 A1，所以 A2 较 A1 好。以后我们不再考虑 A1，因此可把 A1 的粮食移到 A2 以简化问题。同理 A5 也不必考虑，它的粮食可集中到 A4。考虑其他五个村。我们猜想
27、现在粮食数量大的村庄可能是个好主意。假定选择 A4，我们考虑A6 是否会更好：A2、 A7 的粮食少运 4 千米，而 A3、 A4 的粮食多运 4 千米，可见 A4 较 A6 好。同理可证 A4 比其他各村都好。因此仓库应建在 A4。 3工作顺序模型网络规划例 310例 3某工厂的改造工程由下列 7 道工序组成：A ：拆迁；B：工程设计；C：土建工程设计，前接工序为 B；D：采购设备，前接工序为 B；E：厂房土建，前接工序为 A、C； F：设备安装，前接工序为 D、E；G：设备调试，前接工序为 F。那么我们可用图 3.4 表示这个工程，其中 S 表示整个工程的开工， t 表示完工。有时，为了表
28、示工序之间的顺序关系，需要引入虚工序。注意，用来表示工程进度的有向图是不允许有回路的。现在我们研究网络图的各种时间参数。考虑图 3.5 表示的网络，我们把各事项（即图的顶点）编号，一般要求每一工序的开工事项（即箭尾）的编号少于完工事项的编号（即箭头） 。每条有向边旁所标数字为相应工序的长度。某一工序 A 的最早开工时间 t E (A)，表示该工序最早可在整个工程开工后 t E (A)小时开工，这时间仅与该工序的开工事项有关，所以也可以说某一事项的最早时间 t E (k)，例如图 3.5 中，事项 4 的最早时间是 9（即工序 1-4 和 2-4 都完成的时间） 。因而有下列递推公式ik表示起点
29、为 i，终点为 k 的有向边。整个工程完工事项的最早时间，就是全工程完工的最短时间，称为总工期，记为 TE 。某一工序的最迟完工时间（或该工序完工事项的最迟时间） t E (k)，是在不误总工期的条件下，该工序最迟应在整个工程开工后 t L (A)小时完成。因此实际上，t E (k)就是由事项 1 到事项 k 的最长路的长度。t L (k)就是 T E 减去 k 到 n 的最长路的长度。因而（2）的第二式也可写成工序ij的总时差定义为 即不误总工期的条件下该工序的开工时间的机动时间，即可延迟开工的时间；而工序 ij的自由时差定义为 即在不误下道工序最早开工时间的前提下，该工序开工时间的机动时间。
