高等教育图论方法建模.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2020/2/19,#,2024/11/18 周一,主要内容,匹配问题,旅行商问题,最小生成树问题,最大流问题,最小费用最大流问题,2024/11/18 周一,三、,最小生成树问题,Kruskal,算法构造最小生成树,2024/11/18 周一,三、,最小生成树问题,调用,leasttree_2,.m,的,m,函数文件,。,命令形式：,leasttree_2(a),功能：,a,是权矩阵，该矩阵中的主对角全部是,0,并且不包含重复的权；,返回树的节点和权值。,2024/11/18 周一,三、,最小生成树问题,例,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),2024/11/18 周一,三、,最小生成树问题,调用,mintreek,.m,的,m,函数文件,。,命令形式：,a,b=,mintreek,(n,w),功能：,w,是权矩阵，该矩阵中的主对角全部是,inf,；,n,是顶点数；,a,返回最小生成树的权的总长度,b,是返回其具体的节点。并最终返回最小生成树的图形。,2024/11/18 周一,三、,最小生成树问题,例,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),2024/11/18 周一,三、,最小生成树问题,调用,kruskal,.m,的,m,函数文件,。,命令形式：,out,len=,kruskal,(map),功能：,map,是输入矩阵，,map=,起点,1,终点,1,边长,1;,起点,2,终点,2,边长,2;.;,起点,n,终点,n,边长,n,out,输出边阵,:,起点 终点,;,len,输出最小生成树的总长度,;,并最终返回最小生成树的图形。,2024/11/18 周一,三、,最小生成树问题,例,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),2024/11/18 周一,三、,最小生成树问题,例,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),2024/11/18 周一,四、,匹配问题,例,指派问题,图的匹配,2024/11/18 周一,这个问题可以用图的语言描述。其中 表示,工人,表示工作，边 表示第,i,个人能,胜任第,j,项工作，这样就得到了一个二部图,G,，用点集,X,表示,，点集,Y,表示,二部,图,G=(X,Y,E),。上述的工作分配问题就是要在图,G,中找,一个边集,E,的子集，使得集中任何两条边没有公共端,点，最好的方案就是要使此边集的边数尽可能多，这,就是匹配问题。,四、,匹配问题,2024/11/18 周一,二分图的概念,二分图又称作二部图，是图论中的一种特殊模型。,设,G=(V,R),是一个无向图。如顶点集,V,可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属两个不同的子集。则称图,G,为二分图。,1,1,2,2,3,3,4,4,5,四、,匹配问题,2024/11/18 周一,最大匹配,给定一个二分图,G,，在,G,的一个子图,M,中，,M,的边集,E,中的任意两条边都不依附于同一个顶点，则称,M,是一个匹配。,选择这样的边数最大的子集称为图的,最大匹配问题,。,如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为,完全匹配,，也称作,完备匹配。,四、,匹配问题,2024/11/18 周一,匈牙利算法,求最大匹配的一种显而易见的算法是：先找出,全部匹配，然后保留匹配数最多的。但是这个,算法的复杂度为边数的指数级函数。,M,中任意一条边的端点,v,称为（关于,M,的）饱和,点，,G,中其他定点称为非饱和点。,若,P,是图,G,中一条连通,两个未匹配顶点的路径,，,并且属,M,的边和不属,M,的边,(,即已匹配和待匹配的,边,),在,P,上,交替出现,，则称,P,为相对于,M,的一条增,广路径。,四、,匹配问题,2024/11/18 周一,结论：,P,的路径长度必定为奇数，第一条边和最后一条边都不属于,M,。,M,为,G,的最大匹配当且仅当不存在相对于,M,的增广路径。,四、,匹配问题,2024/11/18 周一,四、,匹配问题,2024/11/18 周一,例,1,求二部图,G,中的最大匹配。,X1,Y1,Y2,Y3,Y4,X2,X3,X4,四、,匹配问题,2024/11/18 周一,M,x,S,B,N(s),P,x2y2,x3y3,x1,x1,y2,y2,饱和点,y2x2,x1,x2,y2,y1,y2,y4,y1,非饱和点,x1y2x2y1,x1y2,x2,y1,x3y3,x4,x4,y2,y3,y2,饱和,y2x1,x4,x1,y2,y2,y3,y3,饱和,y3x3,x4,x1,x3,y2,y3,y2,y3,N(s)=B,结束,四、,匹配问题,2024/11/18 周一,最大匹配,就是：,X1,Y1,Y2,Y3,Y4,X2,X3,X4,四、,匹配问题,2024/11/18 周一,四、,匹配问题,调用,pipei.m,的,m,函数文件。,格式：,e,total=pipei(d),功能：,d,是二部图矩阵,(0-1,矩阵,),。,e,输出匹配的路径；,total,最大匹配的边数。,=wi,j,成立,(wi,j,表示边的权,),，且对所有的边,(i,j)in M,都有,lxi+lyj=wi,j,成立，则,M,是图,G,的一个最佳匹配。,四、,匹配问题,2024/11/18 周一,KM,算法,对于任意的,G,和,M,，可行顶标都是存在的：,l(x)=maxw(x,y),l(y)=0,欲求完全二分图的最佳匹配，只要用匈牙利算法求其相等子图的完备匹配；问题是当标号之后的,G,l,无完备匹配时怎么办？,1957,年，,Kuhn,和,Munkras,给出了一个解决该问题的有效算法，用逐次修改可行顶标,l(v),的办法使对应的相等子图之最大匹配逐次增广，最后出现完备匹配。,四、,匹配问题,2024/11/18 周一,四、,匹配问题,例,2,考虑完全的,2,部图，其中,，,。边上的权如下矩阵。,2024/11/18 周一,修改方法如下：,先将一个未被匹配的顶点,u(u in x),做一次增广,路，记下哪些结点被访问那些结点没有被访问。求,出,d=minlxi+lyj-wi,j,其中,i,结点被访问，,j,结点没,有被访问。然后调整,lx,和,ly,：对于访问过的,x,顶点，,将它的可行标减去,d,，对于所有访问过的,y,顶点，将,它的可行标增加,d,。修改后的顶标仍是可行顶标，原,来的匹配,M,仍然存在，相等子图中至少出现了一条,不属于,M,的边，所以造成,M,的逐渐增广。,四、,匹配问题,2024/11/18 周一,KM,算法步骤,Kuhn,Munkras,算法流程：,(1),初始化可行顶标的值,(2),用匈牙利算法寻找完备匹配,(3),若未找到完备匹配则修改可行顶标的值,(4),重复,(2)(3),直到找到相等子图的完备匹配为止,四、,匹配问题,2024/11/18 周一,四、,匹配问题,调用,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),2024/11/18 周一,五、,旅行商问题,Euler,图和,Hamilton,图,2024/11/18 周一,五、,旅行商问题,Euler,图和,Hamilton,图,2024/11/18 周一,五、,旅行商问题,例,5,旅行商问题,网络流,2024/11/18 周一,五、,旅行商问题,2024/11/18 周一,五、,旅行商问题,调用,tsp,.m,的,m,函数文件,。,命令形式：,circle,sum=tsp(a,c1,c2),功能：,a,是输入的权矩阵，,c1,是开始的圈,c2,是改变的圈。,circle,输出经过的点,;,sum,输出最优的总长度。,2024/11/18 周一,五、,旅行商问题,2024/11/18 周一,五、,旅行商问题,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),2024/11/18 周一,六、,最大流问题,网络中的流,2024/11/18 周一,六、,最大流问题,例如,2024/11/18 周一,六、,最大流问题,网络中的流,2024/11/18 周一,六、,最大流问题,网络中的流,2024/11/18 周一,六、,最大流问题,最大流,2024/11/18 周一,六、,最大流问题,最大流的标号算法,调用,ford,.m,的,m,函数文件,。,命令形式：,f,wf,=,ford,(,C,n,),功能：,C,是输入的容量矩阵，,n,是总的顶点数。,f,输出最大流矩阵,;,wf,输出最大流量。,2024/11/18 周一,六、,最大流问题,例,4,求下图中的最大流。,2024/11/18 周一,六、,最大流问题,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),2024/11/18 周一,六、,最大流问题,最小费用最大流,2024/11/18 周一,六、,最大流问题,例如,2024/11/18 周一,六、,最大流问题,最小费用最大流,调用,m,ford,.m,的,m,函数文件,。,命令形式：,f,wf,zwf=mford(C,b,n),功能：,C,是输入的容量矩阵，,b,是弧上的单位流量的费用，,n,是顶点数。,f,输出最小费用最大流矩阵,;,wf,输出最小费用最大流量,;,Zwf,输出最小费用。,2024/11/18 周一,六、,最大流问题,例,5,求下图中的最小费用最大流。,2024/11/18 周一,六、,最大流问题,n=5;,C=0 15 16 0 0;0 0 0 13 14;0 11 0 17 0;0 0 0 0 8;0 0 0 0 0;,b=0 4 1 0 0;0 0 0 6 1;0 2 0 3 0;0 0 0 0 2;0 0 0 0 0;,f,wf,zwf=mford(C,b,n),