Question

图论在数学建模中一般用于哪些类型的题

我问的是比如“最小路径”“工序问题”“网络流”“颜色分类”。。。这些。我想做一个归纳，那位大神能给我，越全越好，希望还能附上算法到哪里找。除此之外，能不能介绍一下关于图论用于数学建模比较有用或写的人性化一点的教材。万分感谢
还有想做一个“背景”归纳，如“赛程安排”“乘公交，看奥运” 。忘了问了，图论一般是用matlab还是其他软件

Answer 1

1 最短路问题（SPP－shortest path problem）
一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。
2 公路连接问题
某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？
3 指派问题（assignment problem）
一家公司经理准备安排 名员工去完成 项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作方案可以使总回报最大？
4 中国邮递员问题（CPP－chinese postman problem）
一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？由于这一问题是我国管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题。
5 旅行商问题（TSP－traveling salesman problem）
一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这一问题的研究历史十分悠久，通常称之为旅行商问题。
6 运输问题（transportation problem）
某种原材料有 个产地，现在需要将原材料从产地运往 个使用这些原材料的工厂。假定 个产地的产量和 家工厂的需要量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本最低？
7.最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法
8.计算赋权图中各对顶点之间最短路径，显然可以调用Dijkstra算法。具体方法是：每次以不同的顶点作为起点，用Dijkstra算法求出从该起点到其余顶点的最短路径，反复执行n次这样的操作，就可得到从每一个顶点到其它顶点的最短路径。这种算法的时间复杂度为O(n^3)。第二种解决这一问题的方法是由Floyd R W提出的算法，称之为Floyd算法。(可以解决第一个问题)
9.prim算法、Kruskal算法构造最小生成树（使所有点连通）
10.匈牙利算法、Kuhn-Munkres算法解决人员分配问题
11.Euler回路的Fleury算法（中国邮递员问题）
12.最大流的一种算法—标号法（用标号法寻求网络中最大流的基本思想是寻找可增广轨，使网络的流量得到增加，直到最大为止。）

我的计算机不好，用的是MATLAB，网上很多资料可以百度到。程序好直接百度对应算法搞成C的吧……
算法很多百度能到……

Answer 2

图论可用于解决“最短路问题”“指派问题”“中国邮递员问题”“旅行商问题”“运输问题”等问题。
对于“赛程安排”的问题建议看看02年全国大学生数模竞赛D题的优秀论文，“乘公交，看奥运”07年全国大学生数模竞赛的b题的优秀论文。看看优秀论文很有帮助！！
图论问题可以用MATLAB做，也可以用lingo将题作为规划问题解决。至于程序，我也是刚刚接触，有些问题也为看明白，我建议你看看相关的资料。
希望简陋的建议对你有帮助！！

Answer 3

excelorm或者lingo都不错。