基于数学建模的图论课程探究
2019-04-14耿显亚
耿显亚
(安徽理工大学 数学与大数据学院，安徽 淮南 232001)
1 图论的基本思想
从哥尼斯堡七桥问题开始，图论发展了接近300年，慢慢趋于完善[1]。图论最本质的内容就是一种二元关系，这种关系可以用来表示某些抽象事物或者具体事物之间的直接联系以及间接联系。算法是人类运用智慧头脑设计的用来解决某些问题的一些列运算。有效的算法设计与分析可以帮助人们使问题更高效地得到解决。数学模型主要是对实际问题利用数学符号、式子、程序、图形等进行刻画，使抽象的问题转化为另一种更直观，更简单的表达方式并且为解决现实问题提供了一个思考方向。数学建模是一门应用数学，把数学理论回归现实并且应用到现实，从而解决生活中的实际问题。图论的相关理论与算法设计有着密不可分的联系，两者之间的完美结合可以使生活中的复杂疑难问题能够更高效地解决，提高效率[2]。
由于现代科技的飞速发展，几乎所有的领域都能见到使用图论的身影：如运筹学、物理学、生物、经济、管理科学、网络理论、信息论、控制论和计算机科学等领域。
2 数学建模的实例与图论算法
图论经过300年的发展，已经逐渐为广大人群所熟悉。图论的“图”与现实中的“图画”并不是一个概念，它可以抽象化地表达事物与事物之间的具体联系。很多人知道关于图论的知识是从哥尼斯堡七桥问题开始的，以及后来的一笔画问题。通过对图论历史与发展的研究，我们可以看出图论确实在许多领域中有十分广泛的应用。实际上，结合图论知识，我们可以解答一些比较简单的现实生活问题，如简单的匹配问题，或者安排座位问题等。越来越多的高校将图论看作是一门独特的学科，许多大学生对它展示了浓厚的兴趣，并开展了以图论为主要研究对象的建模比赛[3]。
本文通过提出一些数学建模问题，对问题进行思考分析，寻找问题的本质内容，最后利用图论算法来处理这些问题。
2.1 哈密顿回路问题
在图G中，若存在这样的一条路：路过每结点一次且只能一次，那么我们把这种略微特殊的路叫做哈密顿路。与上述定义相似，在图G中，若存在这样的一条回路：经过每个结点一次且只能一次，那么我们把这种略微特殊的回路叫做哈密顿回路。我们把具有哈密顿回路的图称为哈密顿图。之所以用哈密尔顿的名字来命名，是因为他在1857年为解释其刚发现的称为“Icosian演算”的一种非交换代数系统，发明了一种同名游戏[4]。与欧拉图不太一样的是，判断一个图是否为哈密尔顿图至今还没有一个简单的的充分必要条件，只有一些必要条件和充分条件。事实上在数学界已经证明，判定一个给定的图是否为哈密尔顿图的问题是困难的，不过，数学家们已经得到了一些判断关于哈密尔顿图是否存在的充分条件。定理：设n阶无向简单图G=
例：举行一个私人会议，有A,B,C,D,E,F,G7个人。已知如下条件：西班牙语；B会说西班牙语和汉语；C会说西班牙语；意大利语和俄语；D会说韩语和汉语；E会说罗马语和意大利语；F会说法语；韩语和俄语；G会说法语和白俄罗斯语。试求一个解决方案，恰当的安排这七个人的座位，目的是使每个人都能和他身边的人交谈？
我们还是用图来解决这个问题。可以这么做：建立一个图的模型，如图1所示，根据人物与语言确定结点，根据每个人会说的语言确定边。根据图论相关知识，用结点代表人物，则结点集合可表示为V={A,B,C,D,E,F,G}。如果在这七个人中某两个人具有相同的共同语言，即这两个人可以相互交流的话，我们就在这两个人所代表的点连一条边。问题就可以转化为：图G中是否存在一条哈密顿回路？由图G分析可以看出，我们所要找的哈密顿回路为A—B—D—F—G—E—C—A。所以该问题的解为：按A—B—D—F—G—E—C—A的顺序排座位，如图。
2.2 最短路径问题
最短路径问题在我们的实际生活中应用非常广泛。例如两个指定城市之间的道路铺设时间最少，交通费用最少问题等等。两个相连接的定点之间的边上通常有一定的权值，代表时间或费用等，一般根据具体问题而定。这些问题实质上就是求权值最小。
问题提出：在两个特定的城市间，有一个公路线路图，此公路线路图中有若干城市相连接。在公路线路图中寻找一条最短的公路线路。
问题分析：由问题我们可以经过分析得到一个图G。图中两个顶点之间的边上的权值可以代表顶点表示城市之间的距离。则该问题就转换为求两个指定顶点u1，v1间具备最小权的道路的问题。u1，v1间的最短路就是这条路线，u1，v1间的距离就是它的权，也可以记为d(u1，v1)。
问题求解：通过对问题的具体分析可知，若求一个城市到其他各个城市的最短路径用迪杰斯特拉(Dijkstra)算法进行解决是比较有效的。迪杰斯特拉算法相对而言是一种求最短路的比较成熟的算法。算法的大致过程为：
第一步：设定一个集合S，初始状态为空集。依次求此特定的顶点到各个点的距离，若不能到达选择用无穷大来代替。然后通过比较选择距离最短的一条边，并将与此条边关联的顶点计入到S集合中。同时也要将路径记录下来。
第二步：将S集合中的顶点作为中间过渡点，更新特定的顶点到各个顶点的最短路径，除去第一步中的最短路径，继续选择最短的路径，然后将最短路径中的还未计入S集合中的顶点计入到S集合中。
重复上面的步骤，直到S集合中出现全部的顶点，算法结束。
2.3 最小生成树问题
最小生成树问题：树通俗的说就是没有圈的连通图，常记为T。现有一个图为G，假设V(G)与V(T)完全一致，而E(T)是E(G)的子集，那么此时T为G的生成树。最小生成树是指具有最小权的生成树的图[5-6]。
问题提出：现在需要在n个城市之间修建石油管道，并且两城之间的石油管道造价已知，怎样设计线路才能使得总造价最低。
问题分析：这种类型问题可被总结为最小生成树问题，在赋权图中找出一个具备最小权的生成树为此问题对应的数学模型。
问题解决：Prim算法是在拥有最小成本边的基础上开始的，然后层层向外扩展，最后得到结论。其过程是这样的：在初始状态中只计入了一条成本最小的边以及与此条边关联的两个结点。然后寻找计入的下一条边以及相关的结点。需要满足的条件为：(1)这条边的一个结点已经计入生成树中，另一个结点还未计入生成树中。(2)此条边必须在满足(1)的情况下成本最小。依次类推，直到所有结点都计入到生成树中并形成一个连通网，结束运算。
求最小生成树的一般算法可描述为：针对图G，从空树T开始，往集合T中逐条选择并加入n-1条安全边(u,v)，最终生成一棵含n-1条边的最小生成树。
当一条边(u,v)加入T时，必须保证T∪{(u，v)}仍是MST的子集，我们将这样的边称为T的安全边。
Prim算法可以概括如下
1)首先输入：给定一个加权连通图G，其中顶点集合为V(G)，边集合为E(G)；
2)然后初始化：Vnew={x}，其中x为集合中V(G)的任一点(起始点)，Enew={ }，为空；
3)重复下列操作，直到Vnew=V：
a.在集合E(G)中选取权值最小的边(u,v)，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V(G)；
b.将v加入集合Vnew中，将(u,v)边加入集合Enew中；
4)输出：使用集合Vnew和Enew来描述所得到的最小生成树。
由于图中的所有关系是无限制的，即任意两个顶点之间都可能会有联系，所以图是一种比较复杂的数据结构。而图的应用在生活中极为广泛，近些年图论的迅速发展，使得图论已经渗入到各个分支中。图论搜索算法可以帮助我们解决日常生活中的棘手问题。在数学建模中除了文中提出的应用还有着其他的应用，如拓扑排序问题，二分图问题等。总的来说，图论算法的应用是十分广泛的，尤其是在研究以某种特定方式相关联的物体间的关系时。但是问题是具有多样性的，这就要求我们从具体问题出发，然后具体分析，勤于思考抽象出恰当的数学模型，并总结规律。这样才能更深入的研究数学建模中图论搜索算法的应用，更加灵活的为我们在现实生活中遇到的问题找到解决方案，数学才能最大化的发挥作用。
