图论方法建模

图论方法建模图论方法建模 1 欧拉七桥问题欧拉七桥问题2 图的基本概念图的基本概念3 简易公路建设方案简易公路建设方案4 前线弹药供应前线弹药供应1 11 欧拉七桥问题欧拉七桥问题18世纪在哥尼斯堡城（今俄罗斯加里宁格勒）有一条世纪在哥尼斯堡城（今俄罗斯加里宁格勒）有一条名叫普莱格尔（名叫普莱格尔（Pregel）的河流横经其中，河上有）的河流横经其中，河上有7座座桥，将河中的两个岛和河岸连结。桥，将河中的两个岛和河岸连结。城中的居民经常沿城中的居民经常沿河过桥散步，于是河过桥散步，于是提出了一个问题：提出了一个问题：能否一次走遍能否一次走遍7座座桥，而每座桥只许桥，而每座桥只许通过一次，最后仍通过一次，最后仍回到起始地点回到起始地点?北岸北岸南岸南岸中心岛中心岛东区东区2 21736年欧拉把这个问题的物理背景变换并简化为一种年欧拉把这个问题的物理背景变换并简化为一种数学设计（称作数学设计（称作图图）：即把每一块陆地用一个点来代）：即把每一块陆地用一个点来代替，将每一座桥用连接相应的两个点的一条线来代替，替，将每一座桥用连接相应的两个点的一条线来代替，从而相当于得到一个图。欧拉证明了这个问题没有解，从而相当于得到一个图。欧拉证明了这个问题没有解，并指出欧几里得几何并不适用于这个问题，因为桥不并指出欧几里得几何并不适用于这个问题，因为桥不涉及涉及“大小大小”，也不能用，也不能用“量化计算量化计算”来解决。来解决。3 32 图的基本概念图的基本概念定义定义 1：有序二元组：有序二元组G=(V,E)称为图，其中：称为图，其中：V=v1,v2,vn表示顶点集，表示顶点集，E=e1,e2,em表示边集。表示边集。所谓的图，直观的讲就是在平面上所谓的图，直观的讲就是在平面上n个点，把其个点，把其中的一些点对用线连接起来，不考虑点的位置与曲线中的一些点对用线连接起来，不考虑点的位置与曲线的曲直长短，这样形成的一个关系结构就是一个图。的曲直长短，这样形成的一个关系结构就是一个图。如果各条边都加上方向，则称为如果各条边都加上方向，则称为有向图有向图，否则称为，否则称为无向图无向图。如果有的边有方向，有的边无方向，则称。如果有的边有方向，有的边无方向，则称为混合图。如果图的每一条边都对应一个实数，则为混合图。如果图的每一条边都对应一个实数，则称该实数为对应边的权，称该图为称该实数为对应边的权，称该图为赋权图赋权图。4 43 简易公路建设方案简易公路建设方案现代战争对后勤保障的依赖程度日渐提高。现代战争对后勤保障的依赖程度日渐提高。上世纪九十年代的海湾上世纪九十年代的海湾战争，截止战争，截止1991年年2月月27日沙漠风暴行动地面作日沙漠风暴行动地面作战结束时为止，美军向战结束时为止，美军向海湾地区共运送了海湾地区共运送了48.5万万人，人，280万吨部队装备，万吨部队装备，650万吨成品油料，万吨成品油料，82.5万吨的后勤支援物资。万吨的后勤支援物资。5 5某合同战术训练基地为保障即将进行的联合军事演习，某合同战术训练基地为保障即将进行的联合军事演习，准备在原有的准备在原有的1个油库的基础上，再设立个油库的基础上，再设立7个固定的燃个固定的燃料补给点。料补给点。3 简易公路建设方案简易公路建设方案6 6v1v7v6v2v8v5v3v4油库与补给点的位置如图所示，其中油库位于油库与补给点的位置如图所示，其中油库位于v1点，点，补给点位于补给点位于v2,v8点。点。7 7经过前期的测绘工作，如果在油库和补给点之间修建经过前期的测绘工作，如果在油库和补给点之间修建简易公路，由于地形不同，每段公路花费如图，每单简易公路，由于地形不同，每段公路花费如图，每单位费用为位费用为1万元。请根据测绘结果，规划一个总造价万元。请根据测绘结果，规划一个总造价最低的建设方案。最低的建设方案。v1v7v6v2v8v5v3v425734326436174182总造价最低总造价最低各补给点到油库的各补给点到油库的花费均达到最小花费均达到最小？8 8通路与路径通路与路径在图在图G中，首尾相接的一串边称为中，首尾相接的一串边称为通路通路，边和顶点都，边和顶点都不重复的通路称为不重复的通路称为路径路径。v1v2v3v4e1e2e3e4e5通路：通路：W=v1e1v2e2v3e5v1e4v4路径：路径：P=v1e1v2e2v3e3v4准备知识准备知识9 9定义定义 2：设：设P(u,v)是赋权图是赋权图G中中u到到v的路径，的路径，则：则：（1）为路径为路径P的权；的权；（2）从）从u到到v的具有最小权的路的具有最小权的路P*(u,v)，称为，称为u到到v的的最短路最短路。固定起点的最短路问题固定起点的最短路问题每对顶点之间的最短路问题每对顶点之间的最短路问题1010邻接矩阵邻接矩阵对赋权图对赋权图G，其邻接矩阵，其邻接矩阵A=(aij)vv，其中：，其中：v1v2v3v4752131111v1v7v6v2v8v5v3v4257343264361741821212寻找最短路的方寻找最短路的方法很多，最适合法很多，最适合这一问题的是这一问题的是Dijkstra算法。算法。定义定义d(vj)为从为从v1到到vj的当前的当前“距离距离”Dijkstra算法的过程就是不断更新算法的过程就是不断更新d(vj)，最终使得所有，最终使得所有d(vj)达到最小。达到最小。v1v7v6v2v8v5v3v425734326436174182定义定义d(vj)为从为从v1到到vj的当前的当前“距离距离”1313d(vj)v1 v2 v3 v4 v5 v6 v7 v80 1 2 7 4 8 v1v7v6v2v8v5v3v425734326436174182 2 4 7 4 8 1414d(vj)v1 v2 v3 v4 v5 v6 v7 v8 2 4 7 4 8 3 7 4 8 v1v7v6v2v8v5v3v4257343264361741821515d(vj)v1 v2 v3 v4 v5 v6 v7 v8 3 7 4 8 v1v7v6v2v8v5v3v425734326436174182 6 4 8 91616d(vj)v1 v2 v3 v4 v5 v6 v7 v8 6 4 8 9 6 6 9v1v7v6v2v8v5v3v4257343264361741821717d(vj)v1 v2 v3 v4 v5 v6 v7 v8 6 6 9 6 9 9v1v7v6v2v8v5v3v4257343264361741821818v1v7 6v6 4 4v2 1 1v8 9v5 6v3 2 2 v4 32243611简易公路建设方案简易公路建设方案1919Dijkstra算法算法算法步骤算法步骤W表示图表示图G的带权邻接矩阵，的带权邻接矩阵，d(vj)表示表示从从v1到到vj的只允许经过已选出顶点的最的只允许经过已选出顶点的最短路的权。短路的权。（1）令）令d(vj)=w1j,S=v1,R=VS=v2,vn（2）在）在R中寻找一个顶点中寻找一个顶点vk，使得，使得置置S=Svk，R=VS。若。若R=，终终止算法。止算法。（3）修正）修正d(vj)，对，对R中的每个中的每个vj，令，令转回（转回（2）20204 前线弹药供应前线弹药供应与我国有陆地边境的某国近来局势紧张，为应对可能与我国有陆地边境的某国近来局势紧张，为应对可能发生的局部冲突，某装甲师奉命开赴前线。发生的局部冲突，某装甲师奉命开赴前线。该师下属代号为该师下属代号为T的某团，装的某团，装备有先进的备有先进的PLZ-05式自行榴弹式自行榴弹炮。该团进驻阵地后，发现临炮。该团进驻阵地后，发现临时设立的弹药补给点没有储备时设立的弹药补给点没有储备155mm榴弹炮，距离最近的储榴弹炮，距离最近的储备有该型炮弹的仓库是后方的备有该型炮弹的仓库是后方的S仓库。团指挥官命令作战参仓库。团指挥官命令作战参谋立即着手规划运输线路，要谋立即着手规划运输线路，要求在求在3天之内完成至少天之内完成至少20个基个基数的弹药储备。数的弹药储备。2121对地图进行简化，阵地记为对地图进行简化，阵地记为vt，仓库记为，仓库记为vs，各道路节点，各道路节点记为记为v1，v2，v5。道路。道路看做是连接各点的边，道路看做是连接各点的边，道路每天的通过能力（容量）记每天的通过能力（容量）记为边的权值为边的权值cij。在最后确定。在最后确定的方案中，每条道路的实际的方案中，每条道路的实际流量记为流量记为xij。v1v2v3v5v4vsvt43642522341675网络最大流问题网络最大流问题：在规定期限内尽可能多地运送物资。：在规定期限内尽可能多地运送物资。综合地图和侦察连汇报的情况，作战参谋发现，综合地图和侦察连汇报的情况，作战参谋发现，T团团距离仓库距离仓库S路程较远，道路情况复杂，有二级公路，路程较远，道路情况复杂，有二级公路，也有临时铺设的简易公路。由于前线实行交通管制，也有临时铺设的简易公路。由于前线实行交通管制，这些道路全部为单向通行。这些道路全部为单向通行。2222道路通过能力（容量）记为边的权值道路通过能力（容量）记为边的权值cij，每条道路的，每条道路的实际流量记为实际流量记为xij。v1v2v3v5v4vsvt436425223416752323标号算法标号算法给定初始可行流给定初始可行流 xij（零流），逐渐增大流量，当不能（零流），逐渐增大流量，当不能增加流量时停止，得到的就是最大流。增加流量时停止，得到的就是最大流。v1v2v3v5v4vsvt43642522341675000000000000002424第一次修改第一次修改从从 vs 到到 vt 找到一条路，使得这条路上所有找到一条路，使得这条路上所有cij 0。修改。修改对应对应 xij 的使流量达到最大。的使流量达到最大。v1v2v3v5v4vsvt43642522341675000000000000002012222525第二次修改第二次修改从从 vs 到到 vt 找到一条路，使得这条路上所有找到一条路，使得这条路上所有cij 0。修改。修改对应对应 xij 的使流量达到最大。的使流量达到最大。v1v2v3v5v4vsvt23642502141675000202000000202022222626第三次修改第三次修改从从 vs 到到 vt 找到一条路，使得这条路上所有找到一条路，使得这条路上所有cij 0。修改。修改对应对应 xij 的使流量达到最大。的使流量达到最大。v1v2v3v5v4vsvt23620502121675202202000200204032242727第四次修改第四次修改从从 vs 到到 vt 找到一条路，使得这条路上所有找到一条路，使得这条路上所有cij 0。修改。修改对应对应 xij 的使流量达到最大。的使流量达到最大。v1v2v3v5v4vsvt23420502101673202222002400203403312828由由c4t=c5t=0，可知不可能再有所有，可知不可能再有所有cij 0 的路存在，的路存在，算法结束。算法结束。v1v2v3v5v4vsvt23320402001673202232002400312929v1v2v3v5v4vsvt232040003222322431流量最大的运输方案如图所示，每天的运送能力是流量最大的运输方案如图所示，每天的运送能力是7，可以满足，可以满足3天储备天储备20个基数的要求。个基数的要求。3030思考思考最优方案是唯一的吗？最优方案是唯一的吗？如果条件允许，可以选择一条道路进行拓宽，如果条件允许，可以选择一条道路进行拓宽，应选择哪一条，拓宽多少？应选择哪一条，拓宽多少？v1v2v3v5v4vsvt436425223416753131