图论方法建模mc2

更新时间：2023-08-28 03:42:01 阅读量：教育文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

图论方法建模1 2 3 4 军用物资的运送图的基本概念简易公路建设方案前线弹药供应

1 欧拉七桥问题18世纪在哥尼斯堡城(今俄罗斯加里宁格勒)有一条名叫普莱格尔(Pregel)的河流横经其中，河上有7 座桥，将河中的两个岛和河岸连结。北岸

中心岛

东区

城中的居民经常沿河过桥散步，于是提出了一个问题：能否一次走遍7座桥，而每座桥只许通过一次，最后仍回到起始地点?

南岸

1736年欧拉把这个问题的物理背景变换并简化为一种数学设计(称作图):即把每一块陆地用一个点来代替，将每一座桥用连接相应的两个点的一条线来代替，从而相当于得到一个图。欧拉证明了这个问题没有解，并指出欧几里得几何并不适用于这个问题，因为桥不涉及“大小”,也不能用“量化计算”来解决。

1 军用物资的运送孙子曰：“善用兵者，役不在籍，粮不三载，取用于国，因粮于敌，故军食可足也。”

游击队之歌我们都是神枪手，每一颗子弹消灭一个敌人，我们都是飞行军，哪怕那山高水又深。在密密的树林里，到处都安排同志们的宿营地，在高高的山岗上，有我们无数的好兄弟。没有吃，没有穿，自有那敌人送上前，没有枪，没有炮，敌人给我们造。我们生长在这里，每一寸土地都是我们自己的，无论谁要强占去，我们就和他拼到底！

19世纪初，拿破仑东征俄国。出发前，拿破仑认为只要抓住俄军主力打上几仗，战争很快就会结束，根本不会拖到冬天。因此命令军队带上了尽量多的随身军需用品，却并未重视大力加强军队的后勤补给。

在以往作战时法军经常就地取食，偏偏俄国人这次采取了坚壁清野的策略，法军只能依靠本土的补给。

拿破仑率领的60万大军，最终只有2万多人撤出俄国，死伤被俘50多万人，损失大炮1000多门，战马10万多匹。

1 军用物资的运送现代战争对后勤保障的依赖程度日渐提高。上世纪九十年代的海湾战争，截止1991年2月27 日沙漠风暴行动地面作战结束时为止，美军向海湾地区共运送了48.5万人，280万吨部队装备， 650万吨成品油料，82.5 万吨的后勤支援物资。

1 军用物资的运送

1 军用物资的运送如何及时地把人员、物资运送到指定地点？军用物资的种类繁多；军用物资往往是由各个不同的仓库运往各个不同的战场。

运输问题目标运费最少

如何实现？

路程最短时间最短路况最好最安全 ……

2 图的基本概念所谓的图，直观的讲就是在平面上n个点，把其中的一些点对用线连接起来，不考虑点的位置与曲线的曲直长短，这样形成的一个关系结构就是一个图。

定

义 1:有序二元组G=(V, E)称为图，其中： V={v1, v2, …, vn}表示顶点集，E={e1, e2, …, em} 表示边集。如果各条边都加上方向，则称为有向图，否则称为无向图。如果有的边有方向，有的边无方向，则称为混合图。如果图的每一条边都对应一个实数，则称该实数为对应边的权，称该图为赋权图。

3 简易公路建设方案某合同战术训练基地为保障即将进行的联合军事演习，准备在原有的1个油库的基础上，再设立7个固定的燃料补给点。

油库与补给点的位置如图所示，其中油库位于v1点，补给点位于v2, …, v8点。

v2 v7 v1

经过前期的测绘工作，如果在油库和补给点之间修建简易公路，由于地形不同，每段公路花费如图，每单位费用为1万元。请根据测绘结果，规划一个总造价最低的建设方案。

2 3 2

v35 1

84 2

v54

3 6

总造价最低

各补给点到油库的花费均达到最小

准备知识通路与路径在图G中，首尾相接的一串边称为通路，边和顶点都不重复的通路称为路径。