基于图论理论的数学建模研究

　　摘要：图论理论是数学的一个重要分支，图论建模对客观事物进行了抽象化、简化，并用图论来描述客观事物的特征和内在联系。在图论中，数学建模方法具有特殊性。伴随着图论发展，图论理论与方法在学生数学建模比赛中得到广泛应用。运用通题方法，找出实际问题，用图论理论进行数学建模，探索在图论理论数学建模竞赛中的应用方法，如最大匹配二部图、最大点独立集、最大推销、哈密顿图、最小生成树等。针对这些领域中存在的各种问题，运用图论等相关方法，提出强有力的数学模型解决方案。

　　关键词：图论理论数学建模哈密尔顿图

　　近年来，在数学应用能力的培养中，培养学生运用数学解决实际问题的能力显得尤为重要。在大学数学教学中引入图论理论进行数学建模思想，是当前数学教学改革的一大趋势。由于图论中的概念和定理大多是从实际问题中抽象出来的，所以图论中大量模型和算法就成了数学建模的重要理论基础。基于此，笔者提出图论理论的数学建模方法，并在进行图论理论的数学建模过程中注重对概念、理论现实背景的介绍，引导学生运用数学建模的思维方式，学习与图论相关的概念、定理，探求其发展规律，从而更好地理解和掌握相关概念、理论。

　　一、基于图论理论的内涵

　　图论将数学建模的思想、方法与定理证明过程结合起来，将定理结论作为待建的具体模型，引导学生根据事先设定好的问题来寻求定理结论，从而得到定理证明。图论的证法是对客观事物进行抽象化、简单化，用图形来表现其特征和内在联系的过程。图论模型与其他数学模型相同，都是为了简化问题、突出重点，从而更加深入地研究问题的本质。图论是组合数学的一个重要分支，它的研究对象是由几个给定点和连接两点的边而组成的图形，通常用点来描述事物之间的特殊关系，连接两点的边用来表示事物之间的关系。图论在现实生活中得到了广泛的应用，也能解决许多实际问题。图论理论的应用范围涉及了许多学科，如物理、化学等。目前，很多课程都涉及图论知识，如离散数学、数据结构等，部分专业甚至把图论作为必修课。由于图论课程中存在概念多、公式复杂、定理难证明、理解难等问题，在一定程度上导致教学难度大、抽象度高、理解困难等现象，更谈不上让学生灵活地运用图论知识来解决各种实际问题，这种状况会使学生厌倦图论的学习。

　　目前，高校教学改革对数学教学越来越重视，数学建模的过程就是运用掌握的数学知识解决实际问题的过程，培养学生运用数学知识解决实际问题的意识是数学课程改革的重要内容之一，将数学建模的思想与方法和图论知识的广泛运用相结合，开展图论教学的研究与实践就显得尤为迫切。基于此，笔者提出了基于图论理论的数学建模，增加了数学建模的内容，使广大学生能够更好地学习和理解数学建模的基本思想方法，也培养了学生运用图论知识进行日常学习的意识，调动了学生学习图论的积极性。图论理论的数学建模解决方法包括优化、实时和结构化处理方法。图论模型在研究方法上与其他模型有很大不同，运用图论中的典型算法，对典型模型进行分析，这些特殊的算法和理论不能用于其他模型。此外，对于其他模型用较少的图解也能得到直观结果。

　　数学建模在自然科学、社会科学和机械工程领域都占有重要地位，解题思路渗透于自然科学的各个领域。根据日益增多的图论竞赛问题，教师可以列举图论竞赛中常见的一些数学建模问题，包括图论色彩、欧拉公式、DMP平面算法等。教师通过设计与图论课程相关的课后模拟活动，并选取符合学生实际、贴近生活的图论题目，激发学生对图论的应用意识与能力，提升学生运用图论知识解决数学和实际问题的能力。

　　二、基于图论理论的哈密尔顿图建模

　　原理一：设图G的每一个顶点都是一个圆，并将其称之为哈密顿圆。

　　原理二：设置加权图G=（V，E），将最小的哈密顿环被称为最佳H圈，保证每个圈经过每个顶点后都能顺利通过。

　　在数学建模过程中，添加关于灾情调查路线图数学模型。题目内容为：夏天的时候，县城发了洪水，官员和有关部门领导赶到县城巡视，巡视的路线是先从县里开始，到村里走完一圈之后再返回县城。三组巡逻队中哪组总行程最短，所需时间最短，然后研究人员巡逻问题、人员最佳回路问题及人员最佳循环问题。

　　为了找出最好的循环巡逻方法，首先结合图论理论建立一个数学模型，再根据特定的已知图G=（V，E'），E'构造一个完整的图G'=（V'，E'），V'每个边的权值对应于顶点y和x的相短路径，即E=（x，y）。

　　原理三：在加权完备条件下，完成了最优循环问题。

　　原理四：设v（G）≥3，循环路径存在条，绘制dG（u）+dG（v）≥u（G）的图形，且所有图形均含有哈密顿圆。

　　原理五：G'为最佳巡逻周期，图中最优巡逻周期权重为d。下列算法适用于探索权值图H=（h，g），其中初始巡逻路径为h，在图形g中给出；对于中任意两个顶点之间的短路，可用以下公式求解：g'=（v，e'），e'=（x，y），（x，y）=min3dg（x，y）用对角线法可以精确计算出初始循环。

　　利用双向法对巡逻路径环进行修正，并对巡逻路径进行优化，以求巡逻路径的近似值，每一个h圆都会得到一个重量较轻的巡逻路径圆。

　　三、基于图论理论的最短路径建模

　　在图论教学中，求最短路径是一个最为重要的问题，在数学建模中也经常遇到。例如，在图A中，对于有向非负加权图，寻找最短路径是有效的。图A中经常使用Floyd算法来寻找非负权图上任意两点间的最短路径，这两种算法都是最短路径。

　　如果v0，v1……vm是图A中从v0到vm的最短路径，且1≤k≤m，vk是图A中从v0到vk的最短路徑，也就是说，从v0到vk的最短路径是1≤k。在最短路径单源问题中，假设一个最短路径从u0到v0，然后再从u0到其他路径。结合树型结构图论可以找到从图顶点到其他顶点的最短路径。对于多源问题，将顶点直接插入图的加权邻接矩阵，然后获得最优路径矩阵D1，D2…，Du。

　　四、基于图论理论的色数禁忌搜索建模

　　如果非循环的MapReduce图中F的所有顶点都着色，使得相邻顶点具有不同颜色，且使用的色度量很小，那么色度量称为MapReduce的色度量，并记录为色度量。许多实际生活问题都可转化为地形图着色问题，以下将举例具体说明：

　　第一，考试安排。学生应避免在考试安排中选择不同课程，并要求考生至少提前几天完成考试安排。

　　第二，儲存安全。如果一个公司生产多种化学品，而且某些产品的生产线又混合在一起，就有可能会发生危险的化学反应。所以企业必须把仓库划分成不同的区域，那安全储存的地方将有多少？

　　第三，频率分配问题。若干无线电发射站，每一变送器有一个使用频率，频数也是频道数。

　　第四，那对同一信道而言，发送端到同一信道的距离必须大于一个指定正数以消除干扰，应该有多少条通道？

　　禁忌方法是局部搜索方法的延伸，通过禁忌搜索可快速解决色数方案的域值。禁忌搜索寻优效果完全取决于域结构和初值选择，禁忌算法易陷入局部极小，无法保证全局最优。禁忌搜索是建立在初始可行解s之上的，从s开始，经过变换得到色数禁忌解的域函数，按照选择策略从这个色数禁忌解中选取s*解，移动到新解上。为避免循环陷入局部最优，禁忌搜索采用禁忌表记录达到的局部最优，即最近搜索的移动状态。在下次搜索时，使用指定的禁止搜索点，不允许在特定搜索中选择，以此实现局部色数禁忌通道的检索和优化。

　　五、基于图论理论的最小生成树建模

　　基于图论理论的子图顶点必须是完全包在一起的，只比原图的边数少一点。子图是完全连接的，没有任何循环的无环图，称为最小生成树。按照最小生成树的定义，顶点只有两度，一度是顶点，也就是挂点；另外的顶点称为切点，且切点大于1。如果把果树的任何一个切口都切除，则最小生成树就会断裂。

　　定义最小生成树子图，且子图中生成树不带环，有条边的充分必要条件，在图中可以将工程管理问题转化为搜索最小权值树。在最小重量的树木中，建筑管理显然是最经济的，与求解最小生成树相同。解最小生成树的算法如下：第一，将各边权值按大小排序；第二，任选第一个边，找出下面这个边；第三，找出下一个边的基础是，前面的边与前面的边不兼容，从而形成一个循环；第四，反复直到找到边缘n1。该算法用来求解图中树形结构。

　　六、结语

　　图论为数学教学提供了一个天然结构，其所得到的数学模型几乎可以应用于所有科学领域。在图论中，只有当主题是“对象”和“对象”的关系时，相关算法才会成为模型求解的重要工具。数学建模思想的培养是一个综合性的过程，也是和其他能力协同发展的过程，教师需要在不同情况下对基于图论理论进行数学建模和讲解。通过教师的教学和讲解，能够帮助学生形成一个良好的思维习惯，加深对数学知识的掌握，提高学生的学习积极性，优化学生的知识结构和知识层次。希望通过这篇文章，帮助相关专业人员对图论有更深入的了解，有效提高教学效率。