图论及其算法在数学建模中的应用

图论从诞生至今已近300年,但很多问题一直没有很好地解决.随着计算机科学的发展,图论又重新成为了人们研究讨论的热点,这里通过提出实际问题、将问题转化并建立模型的方式简单介绍图论及其算法在数学建模中的一些应用.主要有求最短路径的Dijkstra算法、Floyd算法,求最佳匹配的匈牙利算法、KM（Kuhn-Munkres）算法,求最小生成树的Kruskal算法、Prim算法,求网络最大流的Ford-Fulkerson标号算法,求解图的色数的禁忌搜索算法,求平图的DMP平面性算法,求最优邮路的Edmonds-Johnson算法,求解TSP问题的Christofides近似算法等.