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

1、第十二讲 图与网络建模方法图与网络建模方法漳州师范学院数学建模课件2022/7/23 主要内容 匹配问题 旅行商问题 最小生成树问题 最大流问题 最小费用最大流问题2022/7/23 三、最小生成树问题Kruskal算法构造最小生成树2022/7/23 三、最小生成树问题调用leasttree_2.m的m函数文件。命令形式： leasttree_2(a)功能：a是权矩阵，该矩阵中的主对角全部是0,并且不包含重复的权；返回树的节点和权值。2022/7/23 三、最小生成树问题 例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/7/23 三、最小生成树问题调用mintreek.m的m函数文件。命令形式： a,b=mintreek (n,w)功能：w是权矩阵，该矩阵中的主对角全部是inf；n是顶点数；a返回最小生成树的权的总长度,b是返回其具体的节点。并最终返回最小生成树的图形。2022/7/23 三、最小生成树问题 例13 用Kruskal算法求右图的最小生成树。 M=Inf;a1=M,50,60,M,M,M,M;a2=50,M,M,65,40

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

4、小生成树的图形。2022/7/23 三、最小生成树问题 例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/7/23 三、最小生成树问题 例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

5、 6 70;map=a1;a2;a3;a4;a5out,len=kruskal(map)2022/7/23 四、匹配问题例 指派问题 图的匹配2022/7/23这个问题可以用图的语言描述。其中 表示工人, 表示工作，边 表示第i个人能胜任第j项工作，这样就得到了一个二部图G，用点集X表示 ，点集Y表示 ,二部图G=(X,Y,E)。上述的工作分配问题就是要在图G中找一个边集E的子集，使得集中任何两条边没有公共端点，最好的方案就是要使此边集的边数尽可能多，这就是匹配问题。 四、匹配问题2022/7/23二分图的概念二分图又称作二部图，是图论中的一种特殊模型。设G=(V,R)是一个无向图。如顶点集V

6、可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属两个不同的子集。则称图G为二分图。112233445 四、匹配问题2022/7/23最大匹配给定一个二分图G，在G的一个子图M中，M的边集E中的任意两条边都不依附于同一个顶点，则称M是一个匹配。选择这样的边数最大的子集称为图的最大匹配问题。如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。 四、匹配问题2022/7/23匈牙利算法求最大匹配的一种显而易见的算法是：先找出全部匹配，然后保留匹配数最多的。但是这个算法的复杂度为边数的指数级函数。 M中任意一条边的端点v称为（关于M的）饱和点，G中其

7、他定点称为非饱和点。若P是图G中一条连通两个未匹配顶点的路径，并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。 四、匹配问题2022/7/23结论：P的路径长度必定为奇数，第一条边和最后一条边都不属于M。M为G的最大匹配当且仅当不存在相对于M的增广路径。 四、匹配问题2022/7/23 四、匹配问题2022/7/23例1 求二部图G中的最大匹配。X1Y1Y2Y3Y4X2X3X4 四、匹配问题2022/7/23 M x S B N(s)Px2y2,x3y3x1x1y2y2饱和点y2x2x1,x2y2y1,y2,y4y1非饱和点x1y2x2y1x1y

8、2,x2,y1,x3y3x4x4y2,y3y2饱和y2x1x4,x1y2y2,y3y3饱和y3x3x4,x1,x3y2,y3y2,y3N(s)=B结束 四、匹配问题2022/7/23最大匹配就是：X1Y1Y2Y3Y4X2X3X4 四、匹配问题2022/7/23 四、匹配问题调用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/7/23KM算法对于

9、任意的G和M，可行顶标都是存在的：l(x) = maxw(x,y)l(y) = 0欲求完全二分图的最佳匹配，只要用匈牙利算法求其相等子图的完备匹配；问题是当标号之后的Gl无完备匹配时怎么办？1957年，Kuhn和Munkras给出了一个解决该问题的有效算法，用逐次修改可行顶标l(v)的办法使对应的相等子图之最大匹配逐次增广，最后出现完备匹配。 四、匹配问题2022/7/23 四、匹配问题例2 考虑完全的2部图，其中 ， 。边上的权如下矩阵。2022/7/23修改方法如下：先将一个未被匹配的顶点u(u in x)做一次增广路，记下哪些结点被访问那些结点没有被访问。求出d=minlxi+lyj-w

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

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

12、是开始的圈,c2是改变的圈。circle输出经过的点;sum输出最优的总长度。2022/7/23 五、旅行商问题2022/7/23 五、旅行商问题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/7/23 六、最大流问题

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