[高等教育]图论方法建模课件.ppt

1、2022-8-9第十二讲 图与网络建模方法图与网络建模方法漳州师范学院数学建模课件2022-8-9 主要内容 匹配问题 旅行商问题 最小生成树问题 最大流问题 最小费用最大流问题2022-8-9 三、最小生成树问题Kruskal算法构造最小生成树2022-8-9 三、最小生成树问题调用leasttree_2.m的m函数文件。命令形式：leasttree_2(a)功能：a是权矩阵，该矩阵中的主对角全部是0,并且不包含重复的权；返回树的节点和权值。2022-8-9 三、最小生成树问题 例12 用Kruskal算法求右图的最小生成树。a(1,2)=50;a(1,3)=60;a(2,4)=65;a(2

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)2022-8-9 三、最小生成树问题调用mintreek.m的m函数文件。命令形式：a,b=mintreek(n,w)功能：w是权矩阵，该矩阵中的主对角全部是inf；n是顶点数；a返回最小生成树的权的总长度,b是返回其具体的节点。并最终返回最小生成树的图形。2022-8-9 三、最小生成树问题 例13 用Kruskal算法求右图的最小生成树。M=Inf;a1=M,50,60,M,M,M,M;a2=50,M,M,65,40,M,M;a3

3、=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;a7n=7;a,b=mintreek(n,w)2022-8-9 三、最小生成树问题调用kruskal.m的m函数文件。命令形式：out,len=kruskal(map)功能：map是输入矩阵，map=起点1 终点1 边长1;起点2 终点2 边长2;.;起点n 终点n 边长nout输出边阵:起点 终点;len输出最小生成树的总长度;并最终返回最小生成树的图形。20

4、22-8-9 三、最小生成树问题 例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;a5out,len=kruskal(map)2022-8-9 三、最小生成树问题 例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;a

5、2;a3;a4;a5out,len=kruskal(map)2022-8-9 四、匹配问题例 指派问题 图的匹配2022-8-9这个问题可以用图的语言描述。其中 表示工人,表示工作，边 表示第i个人能胜任第j项工作，这样就得到了一个二部图G，用点集X表示 ，点集Y表示 ,二部图G=(X,Y,E)。上述的工作分配问题就是要在图G中找一个边集E的子集，使得集中任何两条边没有公共端点，最好的方案就是要使此边集的边数尽可能多，这就是匹配问题。四、匹配问题nxxx,21nxxx,21nyyy,21),(jiyxnxxx,21nyyy,212022-8-9二分图的概念 二分图又称作二部图，是图论中的一种特

6、殊模型。设G=(V,R)是一个无向图。如顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属两个不同的子集。则称图G为二分图。112233445 四、匹配问题2022-8-9最大匹配 给定一个二分图G，在G的一个子图M中，M的边集E中的任意两条边都不依附于同一个顶点，则称M是一个匹配。选择这样的边数最大的子集称为图的最最大匹配问题大匹配问题。如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全完全匹配匹配，也称作完备匹配。完备匹配。四、匹配问题2022-8-9匈牙利算法 求最大匹配的一种显而易见的算法是：先找出全部匹配，然后保留匹配数最多的。但是这个算法的复杂

7、度为边数的指数级函数。M中任意一条边的端点v称为（关于M的）饱和点，G中其他定点称为非饱和点。若P是图G中一条连通两个未匹配顶点的路径，并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。四、匹配问题2022-8-9 结论：P的路径长度必定为奇数，第一条边和最后一条边都不属于M。M为G的最大匹配当且仅当不存在相对于M的增广路径。四、匹配问题2022-8-9）转（置中有一边饱和点，故是由于转置可扩路的到求一条从）；否则作：饱和点转（为若择一点则停止；否则，任意选）若（置非饱和点中寻找一个）在（）；否则转（中的每一个顶点，结束饱和）若（中的一个初始匹配）

8、任意取（基本步骤：4,)6()2(),(,6)5(;)(,)(4;,3321yBBuSSyuMMyPEMMPMyxMyBSNyBSNBxSxMXXMMG 四、匹配问题2022-8-9例1 求二部图G中的最大匹配。X1Y1Y2Y3Y4X2X3X4 四、匹配问题2022-8-9 M x S B N(s)Px2y2,x3y3 x1x1y2y2饱和点y2x2x1,x2y2y1,y2,y4y1非饱和点x1y2x2y1x1y2,x2,y1,x3y3x4x4y2,y3y2饱和y2x1x4,x1y2y2,y3y3饱和y3x3x4,x1,x3y2,y3y2,y3N(s)=B结束BSNy)(Myu 四、匹配问题2

9、022-8-9 最大匹配就是：X1Y1Y2Y3Y4X2X3X4 四、匹配问题2022-8-9 四、匹配问题调用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的一个最佳匹配。四、匹配问题2022-8-9KM算法 对于任意的G和M，可行顶标都是存在的：l(x)=maxw(x,y)l(y)=0 欲求完全二分图的最佳匹配，只要用匈牙利算法求其相等子图的完备匹配；问题是当标号之后的Gl无完备匹

10、配时怎么办？1957年，Kuhn和Munkras给出了一个解决该问题的有效算法，用逐次修改可行顶标l(v)的办法使对应的相等子图之最大匹配逐次增广，最后出现完备匹配。四、匹配问题2022-8-9 四、匹配问题例2 考虑完全的2部图，其中 ，。边上的权如下矩阵。,521xxxX,521yyyY3312100110014422202214553W0)()(3)(,1)(,4)(,2)(,5)(5154321ylylxlxlxlxlxl2022-8-9 修改方法如下：先将一个未被匹配的顶点u(u in x)做一次增广路，记下哪些结点被访问那些结点没有被访问。求出d=minlxi+lyj-wi,j其中

11、i结点被访问，j结点没有被访问。然后调整lx和ly：对于访问过的x顶点，将它的可行标减去d，对于所有访问过的y顶点，将它的可行标增加d。修改后的顶标仍是可行顶标，原来的匹配M仍然存在，相等子图中至少出现了一条不属于M的边，所以造成M的逐渐增广。四、匹配问题2022-8-9KM算法步骤 KuhnMunkras算法流程：(1)初始化可行顶标的值(2)用匈牙利算法寻找完备匹配(3)若未找到完备匹配则修改可行顶标的值(4)重复(2)(3)直到找到相等子图的完备匹配为止 四、匹配问题2022-8-9 四、匹配问题调用km.m的m函数文件。命令形式：M,MaxZjpp=km(A,n)功能：A是输入二部图的

12、权矩阵，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)2022-8-9 五、旅行商问题Euler图和Hamilton图2022-8-9 五、旅行商问题Euler图和Hamilton图2022-8-9 五、旅行商问题例5 旅行商问题 网络流2022-8-9 五、旅行商问题2022-8-9 五、旅行商问题调用tsp.m的m函数文件。命令形式：circle,sum=tsp(a,c1,c2)功能：a是输入的权矩阵，c1是开始的圈,c2是改变的圈。c

13、ircle输出经过的点;sum输出最优的总长度。2022-8-9 五、旅行商问题2022-8-9 五、旅行商问题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)2022-8-9 六、最大流问题网络中的流 2022-8-9 六、最

14、大流问题例如 2022-8-9 六、最大流问题网络中的流 2022-8-9 六、最大流问题网络中的流 2022-8-9 六、最大流问题最大流 2022-8-9 六、最大流问题最大流的标号算法调用ford.m的m函数文件。命令形式：f,wf=ford(C,n)功能：C是输入的容量矩阵，n是总的顶点数。f输出最大流矩阵;wf输出最大流量。2022-8-9 六、最大流问题例4 求下图中的最大流。2022-8-9 六、最大流问题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

15、 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)2022-8-9 六、最大流问题最小费用最大流2022-8-9 六、最大流问题例如 2022-8-9 六、最大流问题最小费用最大流调用mford.m的m函数文件。命令形式：f,wf,zwf=mford(C,b,n)功能：C是输入的容量矩阵，b是弧上的单位流量的费用，n是顶点数。f输出最小费用最大流矩阵;wf输出最小费用最大流量;Zwf输出最小费用。2022-8-9 六、最大流问题例5 求下图中的最小费用最大流。2022-8-9 六、最大流问题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)