离散数学在实际生活中的应用

离散数学在实际生活中的应用

袁威威

黑河学院 理学院，黑龙江 黑河 164300

摘  要：离散数学中图论在国内或是国外，发展都非常迅速，它在各个领域都有很强的影响。图论中的大多广为人知的研究也通过多种信息传播，备受各大领域关注。图论涉及到的研究内容面十分之广泛，能够影射到的应用方面也比较广泛。本文将讨论欧拉图、哈密尔顿图、最小生成树、二部图问题在实际生活中的应用。

关键词: 离散数学；欧拉图； 哈密尔顿图；最小生成树；二部图

图论模型是一种数学模型，起源于十七世纪的西方，由人们在实际生活中的思考而诞生。在现实世界的所有事物之中，当需要研究它们之间的关系时，可以把它们进行抽象简化，形成图论模型，进而方便人们研究和思考出更有利于生产生活的有效方法。在应用图论这个数学模型来处理实际问题的发展历程中，已经产生了很多图论模型，例如：欧拉图模型、哈密尔顿图模型、二部图模型、最小生成树模型等等。并且很多相应的图论模型的算法也在不断的发展。

1.欧拉图在实际生活中应用

18世纪，数学家从哥尼斯堡的“七桥问题”推导出欧拉图，问题的大概内容是：普鲁士有一条横跨哥尼斯堡的河流，这条河中间有两个由七座桥连接的岛屿。有一个问题是：是否有行人能从河岸或两个岛屿中找到这样的道路：连续不会重复的通过七座桥梁，最后回到起点。多年来，人们一直在研究这个问题，很多人尝尽了各种方法，最后都以失败告终。将欧拉图的理论及其算法应用到现实生活当中来，理论联系实际，将理论内容得以实践，进行实践的教学研究，欧拉图模型主要适用于遍历“边”，并回到起点，同时求出最短距离的实际问题，依据于欧拉图的中国邮路算法以及Fleury算法解决欧拉图在实际生活中果蔬配送问题，并应用其解决路线优化问题，力求改善现实生活中物流方面的运输效率以及路径的优化，为路线相关问题以及欧拉图的应用性提供参考，为社会物流发展提供数学支撑。欧拉图解在逻辑学教学中运用十分广泛，其目的是使抽象晦涩的逻辑推理变得更具体、更清晰、更形象，所以在科技发展十分迅速的现代，熟练的运用欧拉图的一些算法可以解决各种现实生活中路径及配送的相关实际问题。

2.最小生成树在实际生活中应用

离散数学中最小生成树在管道网的铺设布局中应用，在复杂地区的管道网建设中，具有明显的优势，减轻了工作量，从而大大提高工程效率，优化管道设计。欧拉图的逻辑性非常强，最小生成树的Prim算法和Kruskal算法解决管道、网络覆总里程最少，能得到整体的最优解，以最快的方式确定最小生成树，有效分析节点动态，及时设置最优管道，从而大大提高工程效率，优化管道设计。Kruskal算法不但在解决实际问题时比传统的Kruskal算法简单，而且求无向图的最小生成树的步骤易懂。大大的降低了复杂度。给定一个图求其最小生成树。在给定的图中找出度数为1的顶点，若存在把相关联的边删除，并作为最小生成树的一条边，如不存在，则在图中的环找到权最大的边删除，之后再验证新图中是否有度数为1的顶点，有删除，作为最小生成树的边，没有再删除图中的环找到权最大的边删除，直到找出最小生成树的条边为止。其中。

          图1                                               图2

3.哈密尔顿图在实际生活中应用

哈密尔顿图模型主要就“周游世界问题”的相关思想方法来讨论货运物流中的最优路线选择，得到相应算法，分析出最优路线。哈密尔顿图模型主要适用于遍历“点”类型的实际问题，并回到起点求出最短距离的实际问题。哈密尔顿图模型的算法思路主要是在实际问题中构造出相应的回路，再进行计算，直至得出最优解。但是对于哈密尔顿图模型的算法至今都没有有效或者说完美的，这并不影响我们可以应用它的知识，来解决相应的实际问题。对于哈密尔顿图模型的研究与应用，至今仍然是国际上的一个热门方向。因为其在实际生产中所具有的巨大意义以及其算法的不断更新换代。哈密尔顿图模型主要就“周游世界问题”的相关思想方法来讨论货运物流中的最优路线选择，得到相应算法，分析出最优路线。

图3

4.二部图在实际生活中应用

二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边(i，j)所关联的两个顶点i和j分别属于这两个不同的顶点集，则称图G为一个二分图。今有4个工人，A,B,C,D， 4项任务，E,F,G,H。已知工人A熟悉E，F，G；B熟悉F,G；C熟悉H；D熟悉G，H，问如何分配工人，才能使每个人都有任务，且每项任务都有人来完成？应用二部图解决A完成E，B完成F，C完成H，D完成G。

                                 图4

在许多实际应用中，有一类问题可以通过建立模型转换为二部图的匹配问题。应用Hall定理解决这类问题，二部图的匹配在“人员分配”、“婚配问题”、“教室排课”的问题上都有应用。还可以讲具体问题赋值，进行进一步讨论。

随着时代的发展，物流配送运输问题的日益增多。配送线路的选择是物流配送运输中最主要内容。由于配送的货运不仅送货点多、道路网复杂,而且运输网点分布不均匀。因此,如何应用数学方法求解路线优化问题是很多专家学者普遍探索的重要课题。

[参  考  文  献]

[1]耿素云，屈婉玲．离散数学[M]．北京：北京大学出版社,2002.

[2]李刚.离散数学[M]．上海：复旦大学出版社，2006.

1