图论及其算法在数学建模中的应用

[摘要]图论从诞生至今已近300年，但很多问题一直没有很好地解决。随着计算机科学的发展，图论又重新成为了人们研究讨论的热点，这里通过提出实际问题、将问题转化并建立模型的方式简单介绍图论及其算法在数学建模中的一些应用。主要有求最短路径的Dijkstra算法、Floyd算法，求最佳匹配的匈牙利算法、KM（KuhnMunkres）算法，求最小生成树的Kruskal算法、Prim算法，求网络最大流的FordFulkerson标号算法，求解图的色数的禁忌搜索算法，求平图的DMP平面性算法，求最优邮路的EdmondsJohnson算法，求解TSP问题的Christofides近似算法等。

[关键词]图论；数学建模；算法

[基金项目]湖南省大学生研究性学习与创新型实验计划项目：图论及其算法在数学建模中的应用。

1 引 言

《图论》起源于在1736年瑞士数学家Euler提出的哥尼斯堡七桥问题，它是组合数学的一个重要分支。由于图论研究的是个体及其关系的学科，其应用领域十分广阔，不仅局限于数学和计算机科学，还涵盖了社会学、交通管理、电信领域等等。因此图论在数学建模中的应用也就非常广泛，而其算法在求解模型时非常有效。各大数学建模竞赛赛题有很多与图论及其算法有重要联系，例如历届全国数学建模竞赛：93B：足球队排名；94A：逢山开路；94B：锁具装箱；95B：天车与冶炼炉的作业调度；97B：截断切割的最优排列；98B：灾情巡视的最佳路线；99B：钻井布局；07B：乘公交，看奥运；2011B：交巡警服务平台的设置与调度等。此处我们就只着重于阐述图论在数学建模中常见的几种算法及其算法思想，介绍其具体应用，使大家初步领略到图论的魅力。

相关概念：

图：三元有序组G（V（G），E（G），φ（G）），其中V（G）是非空的顶点集，E（G）是不与V（G）相交的边集，φ（G）是关联函数，它使G的每条边对应于G的顶点对。

赋权图：对G的每条边e，可以赋一个实数ω（e），成为e的权，G连同它边上的权成为赋权图。

匹配：给定一个二部图G，M为G边集的一个子集，如果M满足当中的任意两条边都不依附于同一个顶点，则称M是G的一个匹配。

最佳匹配：如果G为加权二部图，则权值和最大的完备匹配称为最佳匹配。

最小生成树：如果加权连通图G的子图T包含G的所有顶点，则称T是G的生成子图；若T是树，则称T为G的生成树，并称其权值和最小的生成为G的最小生成树。

2 常用算法及其应用

2。1 求最短路径的Dijkstra算法、Floyd算法

最短路径问题：设有一个铁路系统连接着若干个城市，x0是该系统中的一个固定城市。在该系统中试求从x0到其他各城市的最短路线。

这是图论中的重要问题，也是数学建模中的常见问题，例如1998年全国大学生数学建模竞赛B题：灾情巡视路线中就涉及此类问题。构造一个加权图G，其顶点xi表示各城市，其边表示连接各城市的铁路，边上的权表示各铁路的造价，问题可转化为求图G中某一点到其他各点最短路（单源性问题），一般用Dijkstra标号算法；求非负赋权图上任意两点间的最短路（多源性问题），一般用Floyd算法。这两种算法均适用于有向非负赋权图。这两种算法的主要理论依据是：若v0，v1，…，vm是图G中从v0到vm的最短路，则1≤k≤m，v0，v1，…，vk必为G中从v0到vk的最短路。即最短路是一条路，且最短路的任一段也是最短路。

对于单源性问题：假设在u0到v0的最短路中只取一条，则从u0到其余顶点的最短路将构成一棵以u0为根的树。因此，可采用树生长的过程来求指定顶点到其余顶点的最短路。这就是Dijkstra标号算法的基本思路。

对于多源性问题：直接在图的带权邻接矩阵中用插入顶点的方法依次构造出v个矩阵D1，D2，…，Dv，使最后得到的矩阵Dv成为图的距离矩阵，距离矩阵中的元素dij表示vi到vj的距离，同时也求出插入点矩阵以便得到两点间的最短路径。

2。2 求最佳匹配的匈牙利算法、KM（KuhnMunkres）算法

工作分配问题（一）：给n个工作人员x1，x2，…，xn安排n项工作y1，y2，…，yn。n个工作人员中每个人能胜任一项或几项工作，但并不是所有工作人员都能从事任何一项工作。 对所有的工作人员能不能都分配一件他所能胜任的工作？

这可转化为求二部图的完美匹配，一般用匈牙利算法，它的主要理论依据是下述定理1：

定理1 M是图G的最大匹配，则G中无M的可增广路。

工作分配问题（二）：给n个工作人员x1，x2，…，xn安排n项工作y1，y2，…，yn。如果每个工作人员工作效率不同，要求工作分配的同时考虑总效率最高。

我们构造一个二部赋权图G=（X，Y，E，F），这里X={x1，x2，…，xn}，Y={y1，y2，…，yn}，F（xi，yj）为工作人员xi胜任工作yj时的工作效率。则问题转化为：求二部赋权图G的最佳匹配。 如1994年B题：锁具装箱[3]。可采用KuhnMunkras算法求解。

在求G的最佳匹配时，总可以假设G为完备二部赋权图。若xi与yj不相邻，可令F（xi，yj）=0。 同样地，还可虚设点x或y，使|X|=|Y|。如此就将G转化为完备二部赋权图，而且不会影响结果。

KuhnMunkras算法流程：（1）初始化可行顶标的值；（2）用匈牙利算法寻找完备匹配；（3）若未找到完备匹配则修改可行顶标的值；（4）重复（2）（3）直到找到相等子图的完备匹配为止。

2。3 求最小生成树的Kruskal算法、Prim算法

筑路选线问题：欲修筑连接n个城市的铁路，已知i城与j城之间的铁路造价为Cij，设计一个线路图，使总造价最低。

这类问题很多，如某城市内供气、供水、供电以及通讯等系统的设计。我们把这类问题称为最小连接问题，问题转化为在一个连通加权图上求权最小的连通生成子图，显然，即求权最小的生成树，称最小生成树。一般采用Kruskal算法或Prim算法求解。

为使生成树上边的权值之和最小，显然，其中每一条边的权值应该尽可能地小。Kruskal算法的做法就是：先构造一个只含n个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在SG上加上这条边，如此重复，直至加上n-1条边为止。

Prim算法的基本思想：

从连通网络G={V，E}中的某一顶点u0出发，选择与它关联的具有最小权值的边（u0v），将其顶点加入到生成树的顶点集合U中。

以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边（u0v），把它的顶点加入到集合U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。

2。4 求网络最大流的FordFulkerson标号算法

运输方案设计：把商品由产地运往销地，交通网上每个路段运输容量给定的条件下，设计一个运输方案，使得运输量最大。这可转化为图论中的最大流问题。

1956年，Ford和Fulkson给出求最大流的2F算法。

基本思想：从任何一个可行流开始，沿增广路对流进行增广，直到网络中不存在增广路为止。 问题的关键在于如何有效地找到增广路，并保证算法在有限次增广后一定终止。

2。5 求解图的色数的禁忌搜索算法

地图着色问题：把无环图G的顶点皆染上颜色，使相邻顶点颜色不同，且使用的颜色数最少，则称这个颜色数为G的色数，记为χ（G）。

很多实际问题可转化为地图着色问题，如：

（1）考试日程问题： 选修课考试安排时，要避免任何一名学生所选不同课程在同一天考，问最少几天才能完成？

（2）存储安全问题： 某公司生产若干种化学制品，其中有些制品如果放在一起可能发生化学反应，引起危险。因此公司必须把仓库分成相互隔离的若干区。问至少要划分多少小区，才可安全存放？

（3）频率分配问题： 地面上有若干无线电发射台，对每台分配一个频率供其使用，频率用自然数从1起编号，称为信道号码，为排除同信道的干扰，要求使用同信道的发射台相距必须大于指定的正数d，问至少要几个信道？

一般采用禁忌搜索法求解。它是对局部领域搜索的扩展。传统局部领域搜索是基于贪婪思想在当前解的领域中进行搜索，搜索性能完全依赖于领域结构和初始解的选取，搜索结果容易陷入局部极小而无法保证全局最优。而禁忌搜索从一个初始可行解s开始，通过变换得解的领域函数V（s），按照某种选择策略从中选取一个解s*，从s移动到s*，把s*作为一个新解，重新叠代搜索，直到满足退出机制。为避免循环和陷入局部最优，禁忌搜索使用禁忌表记录已经到达的局部最优点，也即最近进行的移动状态。在下一步的搜索中利用规定的禁忌规则，在一定搜索次数内不允许选择这些已被禁的搜索点，从而可以跳出局部最优的限制。

2。6 其他算法

2。6。1 求平图的DMP平面性算法

印刷电路板的设计问题：当设计和制造印刷电路板时，首先遇到的问题是判定一个给定的电路图是否能被印刷在同一层板上而使导线不发生短路？若能，怎样给出具体的布线方案？

上述问题转化为判定印刷线路版对应的图是否是平面图？若是，给出它的一个平面表示。DMP平面性算法可判定简单图的平面性并给出其平面表示。

2。6。2 求最优邮路的EdmondsJohnson算法

中国邮递员问题：一个邮递员每次投递邮件都要走遍他所负责的投递区域内的内条街道，完成投递后回到邮局。他应怎样选择路线使他所走的总路程最短？

问题转化为在加权图中求一条回，经过每条边且权和最小。EdmondsJohnson算法是在求Euler图的Euler圈的Fluery算法的基础上改进，先求图中各奇度点间的最短路径将图中奇度点进行配对，并加边使之变成Euler图，再利用Fluery算法求得其Euler圈，即为所求的最优解。

2。6。3 求解TSP问题的Christofides近似算法

旅行售货商（TSP）：设v1，v2，…，vn为n个城市，城市之间的路程已知，售货商从v1出发，走遍所有城市一次且仅一次回到v1，并使总旅程最短。对于这类问题没有最优解法，只有近似解法：Christofides近似算法。事实上，目前还没有发现比Christofides近似算法更接近于最优解的有效近似算法。

3 小 结

图论提供了一个自然的结构，由此而产生的数学模型几乎适合于所有科学领域，只要这个领域研究的主题是“对象”和“对象”之间的关系。而图论中的相关算法成了模型求解的重要工具，此处提到的算法并未涵盖图论中的所有算法，望读者通过本文进一步认识图论，并能运用图论中的算法和算法思想解决更多的问题。

[参考文献]

[1]J。A。Bondy M。S。R。Murty。Graph Theory with Applications[M]。London：Am。Elsvier，New York，1976。

[2]徐俊明。图论及其应用（第三版）[M]。北京：中国科学技术大学出版社，2010。

[3]姜启源，谢金星，叶俊。数学模型（第三版）[M]。北京：高等教育出版社，2003。

推荐访问:建模 算法 数学 图论