摘 要：图论已经诞生二百多年，从18世纪欧拉研究哥尼斯堡七桥问题开始，图论得到了广泛而深刻的发展，其发展从方方面面促进了社会进步，而社会进步也促进图论自身的发展.本文介绍了图论的起源与发展以及影响社会进步的几种应用，包括最短路问题、哈密顿回路问题、旅行商问题、中国邮路问题，并对每种应用都给出了相应的算法以及例题，包括Dijkstra算法、最邻近法、Fleury算法、奇偶点图上作业法.

 

 

关键词：图论，影响，最短路径，算法

 

目录

 

1  引言 4

2  图论的起源与发展 4

2.1  图论的起源 4

2.2  图论的发展 5

3  图论影响社会进步的几种应用 6

3.1  最短路问题 6

3.2  哈密顿回路问题 8

3.2.1  旅行商问题 9

3.2.2  中国邮路问题 11

4  图论对未来社会的影响 13

结论 15

参考文献 16

致谢 17