[高等教育]图论方法建模.ppt_第1页
[高等教育]图论方法建模.ppt_第2页
[高等教育]图论方法建模.ppt_第3页
[高等教育]图论方法建模.ppt_第4页
[高等教育]图论方法建模.ppt_第5页
已阅读5页,还剩43页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

2019/4/20,第十二讲 图与网络建模方法,图与网络建模方法,漳州师范学院数学建模课件,2019/4/20,主要内容,匹配问题,旅行商问题,最小生成树问题,最大流问题,最小费用最大流问题,2019/4/20,三、最小生成树问题,Kruskal算法构造最小生成树,2019/4/20,三、最小生成树问题,调用leasttree_2.m的m函数文件。,命令形式: leasttree_2(a),功能:a是权矩阵,该矩阵中的主对角全部是0,并且不包含重复的权; 返回树的节点和权值。,2019/4/20,三、最小生成树问题,例12 用Kruskal算法求右图的最小生成树。,a(1,2)=50; a(1,3)=60; a(2,4)=65; a(2,5)=40; a(3,4)=52;a(3,7)=45; a(4,5)=50; a(4,6)=30;a(4,7)=42; a(5,6)=70; leasttree_2(a),2019/4/20,三、最小生成树问题,调用mintreek.m的m函数文件。,命令形式: a,b=mintreek (n,w),功能:w是权矩阵,该矩阵中的主对角全部是inf;n是顶点数; a返回最小生成树的权的总长度,b是返回其具体的节点。并最终返回最小生成树的图形。,2019/4/20,三、最小生成树问题,例13 用Kruskal算法求右图的最小生成树。,M=Inf;a1=M,50,60,M,M,M,M; a2=50,M,M,65,40,M,M; a3=60,M,M,52,M,M,45; a4=M,65,52,M,50,30,42; a5=M,40,M,50,M,70,M; a6=M,M,M,30,70,M,M; a7=M,M,45,42,M,M,M; w=a1;a2;a3;a4;a5;a6;a7 n=7;a,b=mintreek(n,w),2019/4/20,三、最小生成树问题,调用kruskal.m的m函数文件。,命令形式: out,len=kruskal (map),功能:map是输入矩阵,,map=起点1 终点1 边长1;起点2 终点2 边长2;起点n 终点n 边长n,out输出边阵:起点 终点; len输出最小生成树的总长度; 并最终返回最小生成树的图形。,2019/4/20,三、最小生成树问题,例14 用Kruskal算法求右图的最小生成树。,a1=1 2 50;1 3 60; a2=2 4 65;2 5 40; a3=3 4 52;3 7 45; a4=4 5 50;4 6 30;4 7 42; a5=5 6 70; map=a1;a2;a3;a4;a5 out,len=kruskal(map),2019/4/20,三、最小生成树问题,例15 用Kruskal算法求右图的最小生成树。,a1=1 2 50;1 3 60; a2=2 4 65;2 5 40; a3=3 4 52;3 7 45; a4=4 5 50;4 6 30;4 7 42; a5=5 6 70; map=a1;a2;a3;a4;a5 out,len=kruskal(map),2019/4/20,四、匹配问题,例 指派问题,图的匹配,2019/4/20,这个问题可以用图的语言描述。其中 表示 工人, 表示工作,边 表示第i个人能 胜任第j项工作,这样就得到了一个二部图G,用点集 X表示 ,点集Y表示 ,二部 图G=(X,Y,E)。上述的工作分配问题就是要在图G中找 一个边集E的子集,使得集中任何两条边没有公共端 点,最好的方案就是要使此边集的边数尽可能多,这 就是匹配问题。,四、匹配问题,2019/4/20,二分图的概念,二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,R)是一个无向图。如顶点集V可分割为两个互不相交的子集,并且图中每条边依附的两个顶点都分属两个不同的子集。则称图G为二分图。,四、匹配问题,2019/4/20,最大匹配,给定一个二分图G,在G的一个子图M中,M的边集E中的任意两条边都不依附于同一个顶点,则称M是一个匹配。 选择这样的边数最大的子集称为图的最大匹配问题。 如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完全匹配,也称作完备匹配。,四、匹配问题,2019/4/20,匈牙利算法,求最大匹配的一种显而易见的算法是:先找出 全部匹配,然后保留匹配数最多的。但是这个 算法的复杂度为边数的指数级函数。 M中任意一条边的端点v称为(关于M的)饱和 点,G中其他定点称为非饱和点。 若P是图G中一条连通两个未匹配顶点的路径, 并且属M的边和不属M的边(即已匹配和待匹配的 边)在P上交替出现,则称P为相对于M的一条增 广路径。,四、匹配问题,2019/4/20,结论: P的路径长度必定为奇数,第一条边和最后一条边都不属于M。 M为G的最大匹配当且仅当不存在相对于M的增广路径。,四、匹配问题,2019/4/20,四、匹配问题,2019/4/20,例1 求二部图G中的最大匹配。,X1,Y1,Y2,Y3,Y4,X2,X3,X4,四、匹配问题,2019/4/20,四、匹配问题,2019/4/20,最大匹配就是:,X1,Y1,Y2,Y3,Y4,X2,X3,X4,四、匹配问题,2019/4/20,四、匹配问题,调用pipei.m的m函数文件。,格式:e,total=pipei(d) 功能:d是二部图矩阵(0-1矩阵)。,e输出匹配的路径; total最大匹配的边数。,d=0 1 0 0;1 1 0 1;0 1 1 0;0 1 1 0 e,total=pipei(d),2019/4/20,最佳匹配,如果边上带权,找出权和最大的匹配叫做求最佳匹配。 实际模型:某公司有职员x1,x2,xn,他们去做工作y1,y2,yn,每个职员做各项工作的效益未必一致,需要制定一个分工方案,使得人尽其才,让公司获得的总效益最大。 数学模型:G是加权完全二分图,求总权值最大的完备匹配。,四、匹配问题,2019/4/20,KM算法,穷举的效率n!,我们需要更加优秀的算法。 定理:设M是一个带权完全二分图G的一个完 备匹配,给每个顶点一个可行顶标(第i个x顶点的 可行标用lxi表示,第j个y顶点的可行标用lyj表 示),如果对所有的边(i,j) in G,都有lxi+lyj=wi,j 成立(wi,j表示边的权),且对所有的边(i,j) in M,都有 lxi+lyj=wi,j成立,则M是图G的一个最佳匹配。,四、匹配问题,2019/4/20,KM算法,对于任意的G和M,可行顶标都是存在的: l(x) = maxw(x,y) l(y) = 0 欲求完全二分图的最佳匹配,只要用匈牙利算法求其相等子图的完备匹配;问题是当标号之后的Gl无完备匹配时怎么办?1957年,Kuhn和Munkras给出了一个解决该问题的有效算法,用逐次修改可行顶标l(v)的办法使对应的相等子图之最大匹配逐次增广,最后出现完备匹配。,四、匹配问题,2019/4/20,四、匹配问题,例2 考虑完全的2部图,其中 , 。边上的权如下矩阵。,2019/4/20,修改方法如下: 先将一个未被匹配的顶点u(u in x)做一次增广 路,记下哪些结点被访问那些结点没有被访问。求 出d=minlxi+lyj-wi,j其中i结点被访问,j结点没 有被访问。然后调整lx和ly:对于访问过的x顶点, 将它的可行标减去d,对于所有访问过的y顶点,将 它的可行标增加d。修改后的顶标仍是可行顶标,原 来的匹配M仍然存在,相等子图中至少出现了一条 不属于M的边,所以造成M的逐渐增广。,四、匹配问题,2019/4/20,KM算法步骤,KuhnMunkras算法流程: (1)初始化可行顶标的值 (2)用匈牙利算法寻找完备匹配 (3)若未找到完备匹配则修改可行顶标的值 (4)重复(2)(3)直到找到相等子图的完备匹配为止,四、匹配问题,2019/4/20,四、匹配问题,调用km.m的m函数文件。,命令形式: M,MaxZjpp=km(A,n),功能:A是输入二部图的权矩阵,n是匹配点。,M输出匹配矩阵; MaxZjpp输出最优匹配的总长度。,A=3 5 5 4 1;2 2 0 2 2;2 4 4 1 0;0 1 1 0 0;1 2 1 3 3; M,MaxZjpp=km(A,5),2019/4/20,五、旅行商问题,Euler图和Hamilton图,2019/4/20,五、旅行商问题,Euler图和Hamilton图,2019/4/20,五、旅行商问题,例5 旅行商问题,网络流,2019/4/20,五、旅行商问题,2019/4/20,五、旅行商问题,调用tsp.m的m函数文件。,命令形式: circle,sum=tsp(a,c1,c2),功能:a是输入的权矩阵,c1是开始的圈,c2是改变的圈。,circle输出经过的点; sum输出最优的总长度。,2019/4/20,五、旅行商问题,2019/4/20,五、旅行商问题,a(1,2)=56;a(1,3)=35;a(1,4)=21;a(1,5)=51;a(1,6)=60; a(2,3)=21;a(2,4)=57;a(2,5)=78;a(2,6)=70; a(3,4)=36;a(3,5)=68;a(3,6)=68; a(4,5)=51;a(4,6)=61; a(5,6)=13; a(6,:)=0; a=a+a; c1=5 1:4 6; c2=5 6 1:4; circle,sum=tsp(a,c1,c2),2019/4/20,六、最大流问题,网络中的流,2019/4/20,六、最大流问题,例如,2019/4/20,六、最大流问题,网络中的流,2019/4/20,六、最大流问题,网络中的流,2019/4/20,六、最大流问题,最大流,2019/4/20,六、最大流问题,最大流的标号算法,调用ford.m的m函数文件。,命令形式: f,wf=ford(C,n),功能:C是输入的容量矩阵,n是总的顶点数。,f输出最大流矩阵; wf输出最大流量。,2019/4/20,六、最大流问题,例4 求下图中的最大流。,2019/4/20,六、最大流问题,n=8;c1=0 5 4 3 0 0 0 0;0 0 0 0 5 3 0 0; c2=0 0 0 0 0 3 2 0;0 0 0 0 0 0 2 0; c3=0 0 0 0 0 0 0 4; 0 0 0 0 0 0 0 3; c4= 0 0 0 0 0 0 0 5;0 0 0 0 0 0 0 0; C=c1;c2;c3;c4; f,wf=ford(C,n),2019/4/20,六、最大流问题,最小费用最大流,2019/4/20,六、最大流问题,例如,2019/4/20,六、最大流问题,最小费用最大流,调用mford.m的m函数文件。,命令形式: f,wf,zwf=mford(C,b,n),功能:C是输入的容量矩阵,b是弧上的单位流量的费用

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论