图论在垃圾站选址中的应用
摘 要:最短路径问题是图论解决的典型实际问题之一,可用来解决厂区布局、
管路铺设、线路安装等实际问题。本文介绍了图论的起源和发展、最短
路径问题及其算法,并应用图论最短路径问题的分析方法,解决城市垃
圾站的选址问题。
关键词:最短路径;Floyd 算法;垃圾站
Abstract: The shortest path problem is typical of graph theory to solve practical
problems, can be used to solve the plant layout, pipe laying, line installation
and other practical issues. This article describes the origins and the
developments of the graph theory, shortest path problems and algorithms,
and apply the shortest path problem in graph theory analysis method to solve
the location problem of municipal garbage station.
Key Words: shortest path; Floyd algorithm; garbage station
1 引言
数学是一门古老的学科,它已经有了几千年的历史。然而,图论作为数学
的一个分支,却只有 200 多年的历史,但是其发展十分迅速。图论是以图为研
究对象,图形中我们用点表示对象,两点之间的连线表示对象之间的某种特定
的关系。事实上,任何一个包含了某种二元关系的系统都可以用图形来模拟,
而且它具有形象直观的特点,在图中点的位置和线的长短曲直无关紧要
[1]
。图
论的发展大力地推进了科学文明的进步,解决了很多实际应用问题。
2 图论的起源
1736 年是图论的历史元年。这一年,图论之父欧拉解决了哥斯尼堡城的七
桥问题,发表了图论的首篇论文。美丽的哥尼斯堡始建于 1308 年,是东普鲁氏
王朝的都市,城内的一条河的两条支流绕过一个岛,有七座桥横跨这两支流。
脚下的七座桥触发了人们的灵感,人们有一项消遣活动,就是试图将河上的每
座桥恰好走过一遍并回到原出发点,然而吸引了人们无数次的尝试却没人成功。
问题看起来不复杂,但谁也解决不了,说不出其所以然来。直到 1736 年,欧拉
解决了这一问题。他将这个问题转化为图论问题,即把每一块陆地用一个点来
评论6