数学建模图论方法专题教学幻灯片讲义.pptVIP

数学建模;内容;图论的基本概念;D;问题2:哈密顿圈(环球旅行游戏) 十二面体的20个顶点代表世界上20个城市,能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点?;问题3:四色问题 对任何一张地图进行着色,两个共同边界的国家染不同的颜色,则只需要四种颜色就够了.;问题4:关键路径问题 一项工程任务,大到建造一座大坝,一座体育中心,小至组装一台机床,一架电视机,都要包括许多工序,这些工序相互约束,只有在某些工序完成之后,一个工序才能开始,即它们之间存在完成的先后次序关系,一般认为这些关系是预知的,而且也能够完成每个工序所需要的时间. 这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目,影响工程进度的要害工序是哪几个?;1.定义;2.常用术语;用图论思想求解 例1 一摆渡人欲将一只狼,一头羊,一蓝菜从河西渡过河到河东,由于船小,一次只能带一物过河,并且,狼与羊,羊与菜不能独处,给出渡河办法.;A=;1.固定起点的最短路;;算法步骤：; TO MATLAB(road1); 1;2.每对顶点之间的最短路;算法的基本思想;算法原理—— 求距离矩阵的方法;算法原理—— 求路径矩阵的方法;i ;算法步骤;;插入点 v1，得：;插入点 v3，得：;插入点 v4，得：;插入点 v6，得：;故从v5到v2的最短路为8 ;插入点 v2，得：;3.最 短 路 的 应 用;; 选址问题--中心问题;S(v1)=10, S(v2)=7, S(v3)=6, S(v4)=8.5, S(v5)=7, S(v6)=7, S(v7)=8.5; 选址问题--重心问题;三.行遍性问题 ; 7; e3;e3;中国邮递员问题-定义;中国邮递员问题-算法; v7; 若G不是欧拉图，则G的任何一个巡回经过某些边必定多于一次．;v7;情形２　G有２n个奇次顶点（n;（３）求出G1的最小权理想匹配M，得到奇次顶点的最佳配对．;例求右图所示投递区的一条最佳邮递路线．;哈 密 尔 顿 图;推销员问题-定义;定义　在加权图G=(V,E)中， （１）权最小的哈密尔顿圈称为最佳H圈． （２）经过每个顶点至少一次的权最小的闭通路称为最佳推销员回路．;定理１　在加权图G=(V,E)中，若对任意x,y,z ;推销员问题近似算法：二边逐次修正法：;例　对以下完备图，用二边逐次修正法求较优H圈．;返回;三. 网络流问题 ;Vs;可行流是指满足如下条件的流:;可行流总是存在的.; 给定容量网络G=(V,A,E)，若点集V被剖分为两个非空集合V1和V2,使vs∈V1,vt ∈V2,则把弧集(V1,V2)称为割集。割集不是唯一的。; 割集(V1,V2)中所有起点在V1,终点在V2的边的容量的和称为割集容量。;Vs;对最大流问题有下列定理：;求最大流的标号法;算法(标号法):;3.重复2直至收点t被标号或不存在可标号的点。若t被 标号，则转4；若t不能被标号且不存在可以标号的点，则停止，输出fv.;(s+,∞);(s+,∞);实例;; 成; 成;最小费用流问题;最小费用流问题的一般提法