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

第十二讲图与网络建模方法图与网络建模方法漳州师范学院数学建模课件2022/12/17第十二讲图与网络建模方法图与网络建模方法漳州师范学院数学建1

主要内容

匹配问题旅行商问题最小生成树问题最大流问题最小费用最大流问题2022/12/17主要内容匹配问题旅行商问题最小生成树问题最大流2

三、最小生成树问题Kruskal算法构造最小生成树2022/12/17三、最小生成树问题Kruskal算法构造最小生成树203

三、最小生成树问题调用leasttree_2.m的m函数文件。命令形式：leasttree_2(a)功能：a是权矩阵，该矩阵中的主对角全部是0,并且不包含重复的权；返回树的节点和权值。2022/12/17三、最小生成树问题调用leasttree_2.m的m函4

三、最小生成树问题

例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)2022/12/17三、最小生成树问题例12用Kruskal算法求右5

三、最小生成树问题调用mintreek.m的m函数文件。命令形式：[a,b]=mintreek(n,w)功能：w是权矩阵，该矩阵中的主对角全部是inf；n是顶点数；a返回最小生成树的权的总长度,b是返回其具体的节点。并最终返回最小生成树的图形。2022/12/17三、最小生成树问题调用mintreek.m的m函数文件6

三、最小生成树问题

例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)2022/12/17三、最小生成树问题例13用Kruskal算法求右7

三、最小生成树问题调用kruskal.m的m函数文件。命令形式：[out,len]=kruskal(map)功能：map是输入矩阵，map=[起点1终点1边长1;起点2终点2边长2;............;起点n终点n边长n]out—输出边阵:[起点终点];len—输出最小生成树的总长度;并最终返回最小生成树的图形。2022/12/17三、最小生成树问题调用kruskal.m的m函数文件。8

三、最小生成树问题

例14用Kruskal算法求右图的最小生成树。

<<a1=[1250;1360];a2=[2465;2540];a3=[3452;3745];a4=[4550;4630;4742];a5=[5670];map=[a1;a2;a3;a4;a5][out,len]=kruskal(map)2022/12/17三、最小生成树问题例14用Kruskal算法求右9

三、最小生成树问题

例15用Kruskal算法求右图的最小生成树。

<<a1=[1250;1360];a2=[2465;2540];a3=[3452;3745];a4=[4550;4630;4742];a5=[5670];map=[a1;a2;a3;a4;a5][out,len]=kruskal(map)2022/12/17三、最小生成树问题例15用Kruskal算法求右10

四、匹配问题例

指派问题

图的匹配2022/12/17四、匹配问题例指派问题图的匹配2022/12/111这个问题可以用图的语言描述。其中表示工人,表示工作，边表示第i个人能胜任第j项工作，这样就得到了一个二部图G，用点集X表示{}，点集Y表示{},二部图G=(X,Y,E)。上述的工作分配问题就是要在图G中找一个边集E的子集，使得集中任何两条边没有公共端点，最好的方案就是要使此边集的边数尽可能多，这就是匹配问题。

四、匹配问题2022/12/17这个问题可以用图的语言描述。其中12二分图的概念二分图又称作二部图，是图论中的一种特殊模型。设G=(V,{R})是一个无向图。如顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属两个不同的子集。则称图G为二分图。112233445

四、匹配问题2022/12/17二分图的概念二分图又称作二部图，是图论中的一种特殊模型。1113最大匹配给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。选择这样的边数最大的子集称为图的最大匹配问题。如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。

四、匹配问题2022/12/17最大匹配给定一个二分图G，在G的一个子图M中，M的边集{E}14匈牙利算法求最大匹配的一种显而易见的算法是：先找出全部匹配，然后保留匹配数最多的。但是这个算法的复杂度为边数的指数级函数。

M中任意一条边的端点v称为（关于M的）饱和点，G中其他定点称为非饱和点。若P是图G中一条连通两个未匹配顶点的路径，并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。

四、匹配问题2022/12/17匈牙利算法求最大匹配的一种显而易见的算法是：先找出四、15结论：P的路径长度必定为奇数，第一条边和最后一条边都不属于M。M为G的最大匹配当且仅当不存在相对于M的增广路径。

四、匹配问题2022/12/17结论：四、匹配问题2022/12/1616

四、匹配问题2022/12/17四、匹配问题2022/12/1617例1求二部图G中的最大匹配。X1Y1Y2Y3Y4X2X3X4

四、匹配问题2022/12/17例1求二部图G中的最大匹配。X1Y1Y2Y3Y4X2X318

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结束

四、匹配问题2022/12/17MxSBN(s)P{x2y2,x3y3}19最大匹配就是：X1Y1Y2Y3Y4X2X3X4

四、匹配问题2022/12/17X1Y1Y2Y3Y4X2X3X4四、匹配问题2022/20

四、匹配问题调用pipei.m的m函数文件。格式：[e,total]=pipei(d)功能：d是二部图矩阵(0-1矩阵)。e—输出匹配的路径；total—最大匹配的边数。<<d=[0100;1101;0110;0110][e,total]=pipei(d)2022/12/17四、匹配问题调用pipei.m的m函数文件。格式：[e21最佳匹配如果边上带权，找出权和最大的匹配叫做求最佳匹配。实际模型：某公司有职员x1,x2,…,xn,他们去做工作y1,y2,…,yn,每个职员做各项工作的效益未必一致，需要制定一个分工方案，使得人尽其才，让公司获得的总效益最大。数学模型：G是加权完全二分图，求总权值最大的完备匹配。

四、匹配问题2022/12/17最佳匹配如果边上带权，找出权和最大的匹配叫做求最佳匹配。22KM算法穷举的效率－n！，我们需要更加优秀的算法。定理：设M是一个带权完全二分图G的一个完备匹配，给每个顶点一个可行顶标(第i个x顶点的可行标用lx[i]表示，第j个y顶点的可行标用ly[j]表示)，如果对所有的边(i,j)inG,都有lx[i]+ly[j]>=w[i,j]成立(w[i,j]表示边的权)，且对所有的边(i,j)inM,都有lx[i]+ly[j]=w[i,j]成立，则M是图G的一个最佳匹配。

四、匹配问题2022/12/17KM算法穷举的效率－n！，我们需要更加优秀的算法。四、23KM算法对于任意的G和M，可行顶标都是存在的：l(x)=maxw(x,y)l(y)=0欲求完全二分图的最佳匹配，只要用匈牙利算法求其相等子图的完备匹配；问题是当标号之后的Gl无完备匹配时怎么办？1957年，Kuhn和Munkras给出了一个解决该问题的有效算法，用逐次修改可行顶标l(v)的办法使对应的相等子图之最大匹配逐次增广，最后出现完备匹配。

四、匹配问题2022/12/17KM算法对于任意的G和M，可行顶标都是存在的：四、匹配24

四、匹配问题例2

考虑完全的2部图，其中，。边上的权如下矩阵。2022/12/17四、匹配问题例2考虑完全的2部图，其中25修改方法如下：先将一个未被匹配的顶点u(uin{x})做一次增广路，记下哪些结点被访问那些结点没有被访问。求出d=min{lx[i]+ly[j]-w[i,j]}其中i结点被访问，j结点没有被访问。然后调整lx和ly：对于访问过的x顶点，将它的可行标减去d，对于所有访问过的y顶点，将它的可行标增加d。修改后的顶标仍是可行顶标，原来的匹配M仍然存在，相等子图中至少出现了一条不属于M的边，所以造成M的逐渐增广。

四、匹配问题2022/12/17修改方法如下：四、匹配问题2022/12/1626KM算法步骤Kuhn－Munkras算法流程：(1)初始化可行顶标的值(2)用匈牙利算法寻找完备匹配(3)若未找到完备匹配则修改可行顶标的值(4)重复(2)(3)直到找到相等子图的完备匹配为止

四、匹配问题2022/12/17KM算法步骤四、匹配问题2022/12/1627

四、匹配问题调用km.m的m函数文件。命令形式：[M,MaxZjpp]=km(A,n)功能：A是输入二部图的权矩阵，n是匹配点。M—输出匹配矩阵;MaxZjpp—输出最优匹配的总长度。<<A=[35541;22022;24410;01100;12133];[M,MaxZjpp]=km(A,5)2022/12/17四、匹配问题调用km.m的m函数文件。命令形式：[M28

五、旅行商问题Euler图和Hamilton图2022/12/17五、旅行商问题Euler图和Hamilton图202229

五、旅行商问题Euler图和Hamilton图2022/12/17五、旅行商问题Euler图和Hamilton图202230

五、旅行商问题例5

旅行商问题

网络流2022/12/17五、旅行商问题例5旅行商问题网络流2022/131

五、旅行商问题2022/12/17五、旅行商问题2022/12/1632

五、旅行商问题调用tsp.m的m函数文件。命令形式：[circle,sum]=tsp(a,c1,c2)功能：a是输入的权矩阵，c1是开始的圈,c2是改变的圈。circle—输出经过的点;sum—输出最优的总长度。2022/12/17五、旅行商问题调用tsp.m的m函数文件。命令形式：33

五、旅行商问题2022/12/17五、旅行商问题2022/12/1634

五、旅行商问题<<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=[51:46];c2=[561:4];[circle,sum]=tsp(a,c1,c2)2022/12/17五、旅行商问题<<a(1,2)=56;a(1,3)=335

六、最大流问题网络中的流

2022/12/17六、最大流问题网络中的流2022/12/1636

六、最大流问题例如

2022/12/17六、最大流问题例如2022/12/1637

六、最大流问题网络中的流

2022/12/17六、最大流问题网络中的流2022/12/1638

六、最大流问题网络中的流

2022/12/17六、最大流问题网络中的流2022/12/1639

六、最大流问题最大流

2022/12/17六、最大流问题最大流2022/12/1640

六、最大流问题最大流的标号算法调用ford.m的m函数文件。命令形式：[f,wf]=ford(C,n)功能：C是输入的容量矩阵，n是总的顶点数。f—输出最大流矩阵;wf—输出最大流量。2022/12/17六、最大流问题最大流的标号算法调用ford.m的m函数41

六、最大流问题例4

求下图中的最大流。2022/12/17六、最大流问题例4求下图中的最大流。2022/142

六、最大流问题<<n=8;c1=[05430000;00005300];c2=[00000320;00000020];c3=[00000004;00000003];c4=[00000005;00000000];C=[c1;c2;c3;c4];[f,wf]=ford(C,n)2022/12/17六、最大流问题<<n=8;c1=[0543043

六、最大流问题最小费用最大流2022/12/17六、最大流问题最小费用最大流2022/12/1644

六、最大流问题例如

2022/12/17六、最大流问题例如2022/12/1645

六、最大流问题最小费用最大流调用mford.m的m函数文件。命令形式：[f,wf,zwf]=mford(C,b,n)功能：C是输入的容量矩阵，b是弧上的单位流量的费用，n是顶点数。f—输出最小费用最大流矩阵;wf—输出最小费用最大流量;Zwf—输出最小费用。2022/12/17六、最大流问题最小费用最大流调用mford.m的m函数46

六、最大流问题例5

求下图中的最小费用最大流。2022/12/17六、最大流问题例5求下图中的最小费用最大流。2047

六、最大流问题<<n=5;C=[0151600;0001314;0110170;00008;00000];b=[04100;00061;02030;00002;00000];[f,wf,zwf]=mford(C,b,n)2022/12/17六、最大流问题<<n=5;2022/12/1648第十二讲图与网络建模方法图与网络建模方法漳州师范学院数学建模课件2022/12/17第十二讲图与网络建模方法图与网络建模方法漳州师范学院数学建49

主要内容

匹配问题旅行商问题最小生成树问题最大流问题最小费用最大流问题2022/12/17主要内容匹配问题旅行商问题最小生成树问题最大流50

三、最小生成树问题Kruskal算法构造最小生成树2022/12/17三、最小生成树问题Kruskal算法构造最小生成树2051

三、最小生成树问题调用leasttree_2.m的m函数文件。命令形式：leasttree_2(a)功能：a是权矩阵，该矩阵中的主对角全部是0,并且不包含重复的权；返回树的节点和权值。2022/12/17三、最小生成树问题调用leasttree_2.m的m函52

三、最小生成树问题

例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)2022/12/17三、最小生成树问题例12用Kruskal算法求右53

三、最小生成树问题调用mintreek.m的m函数文件。命令形式：[a,b]=mintreek(n,w)功能：w是权矩阵，该矩阵中的主对角全部是inf；n是顶点数；a返回最小生成树的权的总长度,b是返回其具体的节点。并最终返回最小生成树的图形。2022/12/17三、最小生成树问题调用mintreek.m的m函数文件54

三、最小生成树问题

例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)2022/12/17三、最小生成树问题例13用Kruskal算法求右55

三、最小生成树问题调用kruskal.m的m函数文件。命令形式：[out,len]=kruskal(map)功能：map是输入矩阵，map=[起点1终点1边长1;起点2终点2边长2;............;起点n终点n边长n]out—输出边阵:[起点终点];len—输出最小生成树的总长度;并最终返回最小生成树的图形。2022/12/17三、最小生成树问题调用kruskal.m的m函数文件。56

三、最小生成树问题

例14用Kruskal算法求右图的最小生成树。

<<a1=[1250;1360];a2=[2465;2540];a3=[3452;3745];a4=[4550;4630;4742];a5=[5670];map=[a1;a2;a3;a4;a5][out,len]=kruskal(map)2022/12/17三、最小生成树问题例14用Kruskal算法求右57

三、最小生成树问题

例15用Kruskal算法求右图的最小生成树。

<<a1=[1250;1360];a2=[2465;2540];a3=[3452;3745];a4=[4550;4630;4742];a5=[5670];map=[a1;a2;a3;a4;a5][out,len]=kruskal(map)2022/12/17三、最小生成树问题例15用Kruskal算法求右58

四、匹配问题例

指派问题

图的匹配2022/12/17四、匹配问题例指派问题图的匹配2022/12/159这个问题可以用图的语言描述。其中表示工人,表示工作，边表示第i个人能胜任第j项工作，这样就得到了一个二部图G，用点集X表示{}，点集Y表示{},二部图G=(X,Y,E)。上述的工作分配问题就是要在图G中找一个边集E的子集，使得集中任何两条边没有公共端点，最好的方案就是要使此边集的边数尽可能多，这就是匹配问题。

四、匹配问题2022/12/17这个问题可以用图的语言描述。其中60二分图的概念二分图又称作二部图，是图论中的一种特殊模型。设G=(V,{R})是一个无向图。如顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属两个不同的子集。则称图G为二分图。112233445

四、匹配问题2022/12/17二分图的概念二分图又称作二部图，是图论中的一种特殊模型。1161最大匹配给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。选择这样的边数最大的子集称为图的最大匹配问题。如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。

四、匹配问题2022/12/17最大匹配给定一个二分图G，在G的一个子图M中，M的边集{E}62匈牙利算法求最大匹配的一种显而易见的算法是：先找出全部匹配，然后保留匹配数最多的。但是这个算法的复杂度为边数的指数级函数。

M中任意一条边的端点v称为（关于M的）饱和点，G中其他定点称为非饱和点。若P是图G中一条连通两个未匹配顶点的路径，并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。

四、匹配问题2022/12/17匈牙利算法求最大匹配的一种显而易见的算法是：先找出四、63结论：P的路径长度必定为奇数，第一条边和最后一条边都不属于M。M为G的最大匹配当且仅当不存在相对于M的增广路径。

四、匹配问题2022/12/17结论：四、匹配问题2022/12/1664

四、匹配问题2022/12/17四、匹配问题2022/12/1665例1求二部图G中的最大匹配。X1Y1Y2Y3Y4X2X3X4

四、匹配问题2022/12/17例1求二部图G中的最大匹配。X1Y1Y2Y3Y4X2X366

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结束

四、匹配问题2022/12/17MxSBN(s)P{x2y2,x3y3}67最大匹配就是：X1Y1Y2Y3Y4X2X3X4

四、匹配问题2022/12/17X1Y1Y2Y3Y4X2X3X4四、匹配问题2022/68

四、匹配问题调用pipei.m的m函数文件。格式：[e,total]=pipei(d)功能：d是二部图矩阵(0-1矩阵)。e—输出匹配的路径；total—最大匹配的边数。<<d=[0100;1101;0110;0110][e,total]=pipei(d)2022/12/17四、匹配问题调用pipei.m的m函数文件。格式：[e69最佳匹配如果边上带权，找出权和最大的匹配叫做求最佳匹配。实际模型：某公司有职员x1,x2,…,xn,他们去做工作y1,y2,…,yn,每个职员做各项工作的效益未必一致，需要制定一个分工方案，使得人尽其才，让公司获得的总效益最大。数学模型：G是加权完全二分图，求总权值最大的完备匹配。

四、匹配问题2022/12/17最佳匹配如果边上带权，找出权和最大的匹配叫做求最佳匹配。70KM算法穷举的效率－n！，我们需要更加优秀的算法。定理：设M是一个带权完全二分图G的一个完备匹配，给每个顶点一个可行顶标(第i个x顶点的可行标用lx[i]表示，第j个y顶点的可行标用ly[j]表示)，如果对所有的边(i,j)inG,都有lx[i]+ly[j]>=w[i,j]成立(w[i,j]表示边的权)，且对所有的边(i,j)inM,都有lx[i]+ly[j]=w[i,j]成立，则M是图G的一个最佳匹配。

四、匹配问题2022/12/17KM算法穷举的效率－n！，我们需要更加优秀的算法。四、71KM算法对于任意的G和M，可行顶标都是存在的：l(x)=maxw(x,y)l(y)=0欲求完全二分图的最佳匹配，只要用匈牙利算法求其相等子图的完备匹配；问题是当标号之后的Gl无完备匹配时怎么办？1957年，Kuhn和Munkras给出了一个解决该问题的有效算法，用逐次修改可行顶标l(v)的办法使对应的相等子图之最大匹配逐次增广，最后出现完备匹配。

四、匹配问题2022/12/17KM算法对于任意的G和M，可行顶标都是存在的：四、匹配72

四、匹配问题例2

考虑完全的2部图，其中，。边上的权如下矩阵。2022/12/17四、匹配问题例2考虑完全的2部图，其中73修改方法如下：先将一个未被匹配的顶点u(uin{x})做一次增广路，记下哪些结点被访问那些结点没有被访问。求出d=min{lx[i]+ly[j]-w[i,j]}其中i结点被访问，j结点没有被访问。然后调整lx和ly：对于访问过的x顶点，将它的可行标减去d，对于所有访问过的y顶点，将它的可行标增加d。修改后的顶标仍是可行顶标，原来的匹配M仍然存在，相等子图中至少出现了一条不属于M的边，所以造成M的逐渐增广。

四、匹配问题2022/12/17修改方法如下：四、匹配问题2022/12/1674KM算法步骤Kuhn－Munkras算法流程：(1)初始化可行顶标的值(2)用匈牙利算法寻找完备匹配(3)若未找到完备匹配则修改可行顶标的值(4)重复(2)(3)直到找到相等子图的完备匹配为止

四、匹配问题2022/12/17KM算法步骤四、匹配问题2022/12/1675

四、匹配问题调用km.m的m函数文件。命令形式：[M,MaxZjpp]=km(A,n)功能：A是输入二部图的权矩阵，n是匹配点。M—输出匹配矩阵;MaxZjpp—输出最优匹配的总长度。<<A=[35541;22022;24410;01100;12133];[M,MaxZjpp]=km(A,5)2022/12/17四、匹配问题调用km.m的m函数文件。命令形式：[M76

五、旅行商问题Euler图和Hamilton图2022/12/17五、旅行商问题Euler图和Hamilton图202277

五、旅行商问题Euler图和Hamilton图2022/12/17五、旅行商问题Euler图和Hamilton图202278

五、旅行商问题例5

旅行商问题

网络流2022/12/17五、旅行商问题例5旅行商问题网络流2022/179

五、旅行商问题2022/12/17五、旅行商问题2022/12/1680

五、旅行商问题调用tsp.m的m函数文件。命令形式：[circle,sum]=tsp(a,c1,c2)功能：a是输入的权矩阵，c1是开始的圈,c2是改变的圈。circle—输出经过的点;sum—输出最优的总长度。2022/12/17五、旅行商问题调用tsp.m的m函数文件。命令形式：81

五、旅行商问题2022/12/17五、旅行商问题2022/12/1682

五、旅行商问题<<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,: