浅谈图论在高职院校专业中的应用

开篇：润墨网以专业的文秘视角，为您筛选了一篇浅谈图论在高职院校专业中的应用范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

【摘 要】图论作为应用数学的一个分支，在职业院校的某些专业中还是很有必要讲授的，它起着服务性作用.在教学过程中将枯燥的数学能与相关专业相结合，有利于提高学生学习数学的积极性。文章主要列举了图论在物流管理和计算机专业中的应用。

【关键词】图论；专业；应用

图论作为应用数学的一个分支是一门理论学科，也是一门工具性学科。在理学、工学、管理学、经济学等各个领域都发挥着作用。高职开设数学课的主要目的是提高学生的文化素质以及为专业服务。在高职院校的专业中介绍一些图论的相关知识很有必要。在教学过程中，将枯燥的数学与相关专业结合，有利于提高学生学习数学的积极性，使数学的广泛应用性得到体现，也可以提高学习的趣味性，这已成为许多高职院校数学教学改革的主要方向之一。 以下列举了图论在物流管理和计算机专业中的应用。

一、图论在物流管理方面的应用

例：如图1所示，某物流公司需从 到 两地运输货物，问如何选择路线使得运输路线最短？

图1

解：这个实际问题可转化为用Dijkstra算法求图1中点v1到点v8的最短路。

（1）首先给v1以P标号，P（v1）=0，给其余所有点T标号，T（v1）=+∞（i=2，…，8）。

（2）由于（v1，v2），（v1，v3）边属于E，且v2，v3为T标号，所以修改这两个点的标号：

T（v2）=min{T（v2），P（v1）+l12}=min{+∞，0+4}=4

T（v3）=min{T（v3），P（v1）+l13}=min{+∞，0+6}=6

（3）比较所有T标号，T（v2）最小，所以令P（v2）=4，并记录路径（v1，v2）。

（4）v2为刚得到P标号的点，考察边（v2，v4），（v2，v5）的端点v4，v5。

T（v4）=min{T（v4），P（v2）+l24}=min{+∞，4+5}=9

T（v5）=min{T（v5），P（v2）+l25}=min{+∞，4+4}=8

（5）比较所有T标号，T（v3）最小，所以令P（v3）=6，并记录路径（v1，v3）。

（6）考察v3，

T（v4）=min{T（v4），P（v3）+l34}=min{9，6+4}=9

T（v5）=min{T（v5），P（v3）+l35}=min{8，6+7}=8

（7）全部T标号中，T（v5）最小，所以令P（v5）=8，并记录路径（v2，v5）。

（8）考察v5，

T（v6）=min{T（v6），P（v5）+l56}=min{+∞，8+5}=13

T（v7）=min{T（v7），P（v5）+l57}=min{+∞，8+6}=14

（9）全部T标号中，T（v4）最小，所以令P（v4）=9，并记录路径（v2，v4）。

（10）考察v4，

T（v6）=min{T（v6），P（v4）+l46}=min{13，9+9}=13

T（v7）=min{T（v7），P（v5）+l47}=min{14，9+7}=14

（11）全部T标号中，T（v6）最小，所以令P（v6）=13，并记录路径（v5，v6）。

（12）考察v6，

T（v7）=min{T（v7），P（v6）+l67}=min{14，13+5}=14

T（v8）=min{T（v8），P（v6）+l68}=min{+∞，13+4}=17

（13）全部T标号中，T（v7）最小，所以令P（v7）=14，并记录路径（v5，v7）。

（14）考察v7，

T（v8）=min{T（v8），P（v7）+l78}=min{17，14+1}=15

（15）因只有一个T标号T（v8），令P（v8）=15，记录路径（v7，v8），计算结束。全部计算结果可知，v1到v8之间的最短路为v1v2v5v7v8，长度是15，同时得到v1点到其余各点的最短路（如图2所示实线部分）。

图2

二、图论在计算机方面的应用

例：如图3所示，是一个局域网的示意图，图中每个结点表示一台计算机，每一条边表示关联的两台计算机之间可以直接敷设网络线，边上的数字表示该网络线的敷设距离，问怎样选择线路使敷设的网络线总长最短？

图3

解：这实质上是求该图的最小生成树，用避圈法如下：（1）图3中边（v1，v6）的权最小，开始时图A只包括结点v2，v6以及边（v2，v6）。（2）在图3中与图A邻接的所有边中权最小的一条边是（v1，v2）。将（v1，v2）连同其一个端点v1添加到图A中。 （3）在图3中与图A邻接的所有边中权最小的一条边是（v5，v6）。将（v5，v6）连同其一个端点v5添加到图A中。到现在为止的图A如图4（a）所示。

图4

为了节省篇幅，后面的步骤省略。图4画出了全步骤中的3个。最后的图4（c）就是所求的最小生成树。即沿这样的线路敷设网络线总长最短。在教学在中，将这些应用实例与课堂教学结合起来，使学生感到了数学的重要性，增强了学生学习的主动性，培养了学生理论联系实际的学风和勇于探究，大胆创新，不断进取的精神，让学生亲自体会运用所学知识去解决实际问题的乐趣，从而大大提高了学生学习的积极性。

参考文献

[1] 付淑娟. 谈谈数学在物流工程项目中的应用[J].商场现代化，2008（3）：72.

[2] 刘锋.物流运筹学[M].上海交通大学出版社，2005.

[3] 马新顺等.在高等数学中引入实验课的实践[J].工科数学，2000（3）.

作者简介：徐敏（1978- ），女，江苏江阴人，研究生毕业，讲师，青海交通职业技术学院，研究方向：高等数学教学。