1、1浅谈图论在高职院校专业中的应用【摘 要】图论作为应用数学的一个分支，在职业院校的某些专业中还是很有必要讲授的，它起着服务性作用.在教学过程中将枯燥的数学能与相关专业相结合，有利于提高学生学习数学的积极性。文章主要列举了图论在物流管理和计算机专业中的应用。 【关键词】图论；专业；应用 图论作为应用数学的一个分支是一门理论学科，也是一门工具性学科。在理学、工学、管理学、经济学等各个领域都发挥着作用。高职开设数学课的主要目的是提高学生的文化素质以及为专业服务。在高职院校的专业中介绍一些图论的相关知识很有必要。在教学过程中，将枯燥的数学与相关专业结合，有利于提高学生学习数学的积极性，使数学的广泛应用
2、性得到体现，也可以提高学习的趣味性，这已成为许多高职院校数学教学改革的主要方向之一。 以下列举了图论在物流管理和计算机专业中的应用。 一、图论在物流管理方面的应用 例：如图 1 所示，某物流公司需从 到 两地运输货物，问如何选择路线使得运输路线最短？ 图 1 解：这个实际问题可转化为用 Dijkstra 算法求图 1 中点 v1 到点 v8的最短路。 2（1）首先给 v1 以 P 标号，P（v1）=0，给其余所有点 T 标号，T（v1）=+（i=2，8） 。 （2）由于（v1，v2） ， （v1，v3）边属于 E，且 v2，v3 为 T 标号，所以修改这两个点的标号： T（v2）=minT（v
3、2） ，P（v1）+l12=min+，0+4=4 T（v3）=minT（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）=minT（v4） ，P（v2）+l24=min+，4+5=9 T（v5）=minT（v5） ，P（v2）+l25=min+，4+4=8 （5）比较所有 T 标号，T（v3）最小，所以令 P（v3）=6，并记录路径（v1，v3） 。 （6）考察 v3， T（v4）=minT
4、（v4） ，P（v3）+l34=min9，6+4=9 T（v5）=minT（v5） ，P（v3）+l35=min8，6+7=8 （7）全部 T 标号中，T（v5）最小，所以令 P（v5）=8，并记录路径（v2，v5） 。 （8）考察 v5， T（v6）=minT（v6） ，P（v5）+l56=min+，8+5=13 T（v7）=minT（v7） ，P（v5）+l57=min+，8+6=14 3（9）全部 T 标号中，T（v4）最小，所以令 P（v4）=9，并记录路径（v2，v4） 。 （10）考察 v4， T（v6）=minT（v6） ，P（v4）+l46=min13，9+9=13 T（v7）
5、=minT（v7） ，P（v5）+l47=min14，9+7=14 （11）全部 T 标号中，T（v6）最小，所以令 P（v6）=13，并记录路径（v5，v6） 。 （12）考察 v6， T（v7）=minT（v7） ，P（v6）+l67=min14，13+5=14 T（v8）=minT（v8） ，P（v6）+l68=min+，13+4=17 （13）全部 T 标号中，T（v7）最小，所以令 P（v7）=14，并记录路径（v5，v7） 。 （14）考察 v7， T（v8）=minT（v8） ，P（v7）+l78=min17，14+1=15 （15）因只有一个 T 标号 T（v8） ，令 P（v
6、8）=15，记录路径（v7，v8） ，计算结束。全部计算结果可知，v1 到 v8 之间的最短路为v1v2v5v7v8，长度是 15，同时得到 v1 点到其余各点的最短路（如图 2 所示实线部分） 。 图 2 二、图论在计算机方面的应用 例：如图 3 所示，是一个局域网的示意图，图中每个结点表示一台计算机，每一条边表示关联的两台计算机之间可以直接敷设网络线，边4上的数字表示该网络线的敷设距离，问怎样选择线路使敷设的网络线总长最短？ 图 3 解：这实质上是求该图的最小生成树，用避圈法如下：（1）图 3 中边（v1，v6）的权最小，开始时图 A 只包括结点 v2，v6 以及边（v2，v6） 。 （2
7、）在图 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.工科数学，52000（3）. 作者简介：徐敏（1978- ） ，女，江苏江阴人，研究生毕业，讲师，青海交通职业技术学院，研究方向：高等数学教学。
