借助图论方法，指导数学建模

唐纪芳

[摘 要] 图论方法是数学建模的重要方法，通过利用图式，很多数学难题都能得以快速巧妙地解决。根据多年的教学实践经验，浅谈了几点借助图论方法，指导学生数学建模的策略，旨在提高学生解决问题的能力，升华其数学素养。

[关 键 词] 高职；数学建模；图论

[中图分类号] G712 [文献标志码] A [文章编号] 2096-0603（2018）08-0170-01

图论是离散数学的一个重要分支，工程技术、自然科学、经济管理等领域的诸多问题通过借用图论方法建立数学模型，都能得以迎刃而解。下面笔者针对图论的几种重要算法及其应用展开了简单的论述。

一、最短轨道问题，变换标号

最短轨道问题指的是在给出的一个网络中，找出任意两点之间的最短路线及其长度。运用图论方法求解最短路问题时，首先需要从路线的起点开始，逐步寻找到达各点的最短路线，并且需要在每一步都对顶点记录一个数，即做出该点的标号，随后不断变换标号，把一个不是最短距离标号的顶点变成是最短距离标号的顶点，最后得到最短的一条线路。应用该算法可以高效地解决交通路网的布置、景观路线的安排、运输路线的设计等实际问题。教师在进行教学时，可以引导学生将实际问题转化为图论中的最短轨道问题，抽象出数学模型。

比如，笔者在对项目管理专业的高职学生进行教学时，设计了如下的问题让学生进行作答：某建设单位A有一批钢筋需要从城市v1运送到施工单位所在城市v6，已知六座城市v1、v2、v3、v4、v5、v6之間的路网形式如下图所示，请问选择哪一条运输路线才能使成本最低呢？学生在解决这一问题时，建立了数学模型：W（P（v1，v6））=min{W（P），P取自所有v1到v6的轨道集合}，然后通过数次的迭代与标号变换，找到了最短路线：v1→v3→v2→v4→v5→v6，且最短距离为12。

二、探究Euler回路，节点配对

随着科学技术的发展，电路结构变得越来越复杂，图论方法在电路结构设计与计算中扮演着十分重要的角色。Euler回路是由数学家欧拉在解决“七桥问题”时创设的，对于电气等专业的高职学生，通过应用Euler回路对复杂电路进行分析，对支路的联结点进行配对，有助于得到最简回路电流方程组，简化电路的求解。

比如，笔者在引导相关专业的学生学习Euler回路时，带大家探究了如下的电路问题：如下图2所示，电路中有A、B、C、D、E五个节点，8条支路，13个回路……求解该电路。在探究这一问题时，笔者引导学生将欧拉回路的思想渗透到电路的分析与计算中来，选择网孔作为一组独立回路，4个网孔分别如下图3所示，最后得到了7个电路方程，成功求解了该电路问题。

三、求最小生成树，有效避圈

高职数学内容一般比较抽象，学生在解决一些涉及离散型变量的数学问题时，常常会觉得比较吃力、困难。图论方法具有直观形象的优点，比如说最小生成树原理，通过用点与边组成图形表示现实世界中的各种关系，能够使关系变得简单明了，易于解决。克罗斯克尔算法也叫做“避圈法”，利用该方法能够有效建构选线问题等题型的数学模型。因此在教学时，教师可以引导学生善于从题目中抽象出最小生成树模型，提高他们解决专业相关问题的能力。

图论在实际的生产生活中有着非常广泛的应用，其内容与高职专业密切相关，教师应注重结合专业合理组合图论的教学内容，使高职数学的教学更加专业化、高效化。

参考文献：

[1]乔友付.数学建模在《图论》教学中的作用[J].教育教学论坛，2013（37）：65-66.

[2]卜月华，王维凡，吕新忠.图论及其应用[M].东南大学出版社，2015.