第10章 网络流与二分图.ppt

《第10章 网络流与二分图.ppt》由会员分享，可在线阅读，更多相关《第10章 网络流与二分图.ppt（53页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第10章章 网络流与二分图网络流与二分图第第12、13讲：黄丽韶讲：黄丽韶ly_12/25/2022目目 录录10.1 网络与流网络与流10.1.1 网络流基本概念网络流基本概念10.1.2 增广路算法增广路算法10.1.3 求最大流的标号法求最大流的标号法Ford-Fulkerson方法方法10.2 二分图匹配二分图匹配10.2.1 二分图与匹配二分图与匹配10.2.2 二分图最大匹配问题网络流算法二分图最大匹配问题网络流算法10.2.3 二分图最大匹配问题的匈牙利算法二分图最大匹配问题的匈牙利算法10.2.4 最小点覆盖与最小路径覆盖最小点覆盖与最小路径覆盖10.2.5 二分图最优匹配二

2、分图最优匹配12/25/2022问题引入问题引入 如下图，经济区域中城市如下图，经济区域中城市s和城市和城市t间的物流运输网络。记间的物流运输网络。记v1为为s，v9为为t，每一条有向边（每一条有向边（vi，vj）表示从表示从vi到到vj的运输的运输线，货物经这条运输线由线，货物经这条运输线由vi运送到运送到vj，线旁的数字表示线线旁的数字表示线的最大运输能力。货物经过网络从城市的最大运输能力。货物经过网络从城市s运送到城市运送到城市t。现要求制定一个运输方案，使从现要求制定一个运输方案，使从s运送到运送到t的货物最多。的货物最多。物流运输网络图物流运输网络图12/25/2022一种运输方案一

3、种运输方案 12/25/2022运输网络的特点运输网络的特点 （1）实际运输量不能为负。）实际运输量不能为负。（2）每条有向边上的实际运输量不能大于该边上的容量。）每条有向边上的实际运输量不能大于该边上的容量。（3）除了起点）除了起点s和终点和终点t外，对于其他顶点来说，所有指向外，对于其他顶点来说，所有指向vi的的线上的运输量的和，应该等于所有从线上的运输量的和，应该等于所有从vi出发的有向边上的运出发的有向边上的运输量的和。输量的和。12/25/202210.1 10.1 网络与流网络与流12/25/202210.1.1 10.1.1 网络流基本概念网络流基本概念 1网络网络 设设G是一个

4、简单有向图，是一个简单有向图，G=（V，E），），V=v1，v2，v3，vn。在。在V中指定一个顶点中指定一个顶点s，称为源（或称源点或发称为源（或称源点或发点），取另一个顶点点），取另一个顶点t，称为汇（或称汇点或收点）。对称为汇（或称汇点或收点）。对于有向图于有向图G的每一条有向边（的每一条有向边（vi，vj）E，对应的有一个对应的有一个值值cij0，称为该有向边上的容量。通常把这样的有向图称为该有向边上的容量。通常把这样的有向图G叫做一个网络，记为叫做一个网络，记为G=（V，E，C），），其中其中C是网络的是网络的容量函数。容量函数。2网络流网络流 网络上的流，是指定义在有向边集合网络上

5、的流，是指定义在有向边集合E上的一个函数上的一个函数F=fij：(vi，vj)E，并称并称fij为边为边(vi，vj)上的流量。上的流量。12/25/202210.1.1 10.1.1 网络流基本概念网络流基本概念3可行流可行流容量限制条件：对于每一条边（容量限制条件：对于每一条边（vi，vj）E，0fijcij。平衡条件：对于每个中间点平衡条件：对于每个中间点vi，vi的流出量的流出量=vi的流入量。的流入量。V(F)=可行流的流量可行流的流量 12/25/202210.1.1 10.1.1 网络流基本概念网络流基本概念4最大流最大流一个可行流一个可行流F=fij，使其流量使其流量V(F)达

6、到最大，并且满足：达到最大，并且满足：（vi，vj）E，0fijcij12/25/202210.1.1 10.1.1 网络流基本概念网络流基本概念5残流网络残流网络 边（边（vi，vj）E的残流容量为的残流容量为cij fij，表示通过该边能调整表示通过该边能调整的最大流容量。的最大流容量。给定网络给定网络G=（V，E，C），及），及G的一个可行流的一个可行流F fij。G的残流网络的残流网络G是通过下列方法得到的网络是通过下列方法得到的网络G=（V，E，C），），设（设（vi，vj）E：当当cij fij时，时，G中有对应的边（中有对应的边（vi，vj）E，边上的流量边上的流量是是cij=c

7、ijfij；当当fij 0时，时，G中还有一条边（中还有一条边（vj，vi）E，边（边（vj，vi）上上的流量是的流量是cij=fij。12/25/202210.1.2 10.1.2 增广路算法增广路算法1向前边与后向边向前边与后向边 对于网络对于网络G=（V，E，C），），若给一个可行流若给一个可行流F fij，则则把网络中使把网络中使fijcij 的有向边称为饱和边，使的有向边称为饱和边，使fij 的边称为非零流的边称为非零流边。边。若若P是网络中联结源点是网络中联结源点s和汇点和汇点t的一条路，定义路的方向是的一条路，定义路的方向是从从s 到到t，则路上的边被分成两类：一类是边的方向与路

8、的方向则路上的边被分成两类：一类是边的方向与路的方向一致，叫做向前边。向前边的全体记为一致，叫做向前边。向前边的全体记为P+。另一类边与路的另一类边与路的方向相反，叫做向后边。向后边的全体记为方向相反，叫做向后边。向后边的全体记为P-。12/25/2022原问题的算法设计原问题的算法设计2增广路增广路定义：设定义：设F是一个可行流，是一个可行流，P是从是从s到到t的一条路，若的一条路，若P满足满足下列条件：下列条件：（1）在）在P的所有向前边（的所有向前边（vi，vj）上，上，0fij cij，即，即P+中的中的每一条边是非饱和边。每一条边是非饱和边。（2）在）在P的所有向后边（的所有向后边（

9、vi，vj）上，上，0 fij cij，即，即P-中的中的每一条边是非零流边。每一条边是非零流边。12/25/20223 3增广路算法思想与增广路定理增广路算法思想与增广路定理 对一条增广路对一条增广路P，将可行流将可行流F改进成一个值更大的流改进成一个值更大的流F，基本基本思想：思想：（1）不属于增广路）不属于增广路P的边（的边（vi，vj）上的流量一概不变，即上的流量一概不变，即fij fij。（2）增广路增广路P上的所有边（上的所有边（vi，vj）上的流量按下述规则调整：上的流量按下述规则调整：在在P+中的向前边（中的向前边（vi，vj）上，上，fij fij+；在在P-中的向后边（中的

10、向后边（vi，vj）上，上，fij fij；12/25/2022实例实例-调整后的运送方案调整后的运送方案 12/25/2022增广路定理增广路定理 设设F是网络是网络G的一个流，如果不存在从的一个流，如果不存在从s到到t关于关于F的的增广路增广路P，那么那么F一定是最大流。一定是最大流。12/25/2022增广路方法求最大流的基本流程增广路方法求最大流的基本流程 12/25/2022残流网络残流网络 如果残流网络如果残流网络G中没有从中没有从s到到t的增广路，那么当前流为最的增广路，那么当前流为最大流；反之，如果当前流大流；反之，如果当前流G不为最大流，则不为最大流，则G一定有增广一定有增广

11、路。路。12/25/202210.1.3 10.1.3 求最大流的标号法求最大流的标号法Ford-FulkersonFord-Fulkerson方法方法从一个可行流出发（若网络中没有给定可行流从一个可行流出发（若网络中没有给定可行流F，则可以设则可以设F为平凡的零流），经过标号过程和调整过程，可以求出网为平凡的零流），经过标号过程和调整过程，可以求出网络中的最大流。络中的最大流。标号过程：网络中的顶点逐渐进行标号，顶点分为两类：标标号过程：网络中的顶点逐渐进行标号，顶点分为两类：标号顶点（已检查和未检查两种）；未标号顶点。每个标号顶号顶点（已检查和未检查两种）；未标号顶点。每个标号顶点点v的标

12、号由两个部分（的标号由两个部分（u，d）组成：标号的第一部分组成：标号的第一部分u指指明它的标号是从哪一个顶点得到的，以便找出增广路；标号明它的标号是从哪一个顶点得到的，以便找出增广路；标号的第二部分的第二部分d是为确定增广路的调整量是为确定增广路的调整量用的。用的。12/25/2022标号步骤标号步骤 1.先将先将s标上（标上（0，+）标号（或称标记）标号（或称标记）2.取一个已标号而未检查的顶点取一个已标号而未检查的顶点vi，对一切与对一切与vi相连而未标相连而未标号顶点号顶点vj：（1）若在边（若在边（vi，vj）上，上，fij，则给则给vj标号为（标号为（vi，d(vj)），），这里这

13、里d(vj)Mind(vi)，fji。这时顶点这时顶点vj成为标号成为标号而未检查的顶点。而未检查的顶点。12/25/2022标号步骤标号步骤在在vi的全部相邻顶点都已标号后，的全部相邻顶点都已标号后，vi成为已检查过的顶点。成为已检查过的顶点。于是，重复上述步骤。一旦于是，重复上述步骤。一旦t被标上号，表明得到一条从被标上号，表明得到一条从s到到t的增广路的增广路P，转入调整过程。转入调整过程。若所有标号都是已检查过的，而标号过程无法进行时，则若所有标号都是已检查过的，而标号过程无法进行时，则算法结束，这时的可行流即为最大流。算法结束，这时的可行流即为最大流。12/25/2022调整过程调整

14、过程 采用采用“逆向追踪逆向追踪”的方法，从的方法，从t t开始，利用标号点的开始，利用标号点的第一个分量得到前趋顶点，逐条边地寻找，得到一条增第一个分量得到前趋顶点，逐条边地寻找，得到一条增广路广路P P，并以并以t t标号的第二个分量标号的第二个分量d d(t t)作为改进量作为改进量，改改进路径进路径P P上的流量。上的流量。12/25/202210.2 10.2 二分图匹配二分图匹配11.2.1 问题问题 一个公司有一个公司有 n 个工作空缺，每项工作需要具有一定个工作空缺，每项工作需要具有一定资格的人承担。今有资格的人承担。今有 m 个人申请这个人申请这 n 项工作。如果一个项工作。

15、如果一个工作空缺只能由一名满足该工作资格的人承担，那么在工作空缺只能由一名满足该工作资格的人承担，那么在这这m个申请人中能够承担工作的最大个数是多少？个申请人中能够承担工作的最大个数是多少？12/25/2022求职者关系图求职者关系图 申请者的集合为申请者的集合为X=x1，x2，xm，工作的集合为工作的集合为Y=y1，y2，yn。X与与Y关系图关系图12/25/202210.2.2 10.2.2 二分图与匹配二分图与匹配 二分图二分图G：所有的顶点分成两个集合所有的顶点分成两个集合X和和Y，其中其中X或或Y在在各自集合中的任意两个点都不相连，而在各自集合中的任意两个点都不相连，而在X和和Y中的

16、顶点可中的顶点可以构成边。以构成边。12/25/2022匹配概念匹配概念二二分分图图G的的匹匹配配M：边边集集 E的的子子集集M，具具有有性性质质：M中中没没有两条边有公共顶点。有两条边有公共顶点。最大匹配：就是在最大匹配：就是在G的所有匹配中具有最多边数的匹配。的所有匹配中具有最多边数的匹配。完美匹配：如果所有点都在匹配边上，称这个最大匹配完美匹配：如果所有点都在匹配边上，称这个最大匹配是完美匹配。是完美匹配。12/25/202210.2.3 二分图最大匹配问题网络流算法二分图最大匹配问题网络流算法 给定二分图给定二分图G=（X，E，Y）。）。构造与构造与G对应的网络对应的网络G*，构造方法

17、如下：构造方法如下：（1）增加一个源点）增加一个源点s，一个汇点一个汇点t。（2）从）从s向向X的每个顶点引一条有向边，从的每个顶点引一条有向边，从Y的每个顶点向的每个顶点向t引一条有向边。引一条有向边。（3）将原图）将原图G的每条边改为从的每条边改为从X指向指向Y的有向边。的有向边。（4）置所有边的容量为）置所有边的容量为1。求网络求网络F的最大流。最大流值是对应于二分图的最大流。最大流值是对应于二分图G的最大匹的最大匹配边数。配边数。12/25/202210.2.4 二分图最大匹配问题的匈牙利算法二分图最大匹配问题的匈牙利算法 令令G=(X，E，Y)是一个二分图，其中是一个二分图，其中x=

18、x1，x2，xm，Y=y1，y2，yn。令。令M为为G的任意匹配。的任意匹配。S1：将：将X的所有不与的所有不与M的边关联的顶点标上（的边关联的顶点标上（*），并称所），并称所有的顶点为未扫描的。转到有的顶点为未扫描的。转到S2。S2：如果在上一步没有新的标记加到如果在上一步没有新的标记加到X的顶点上，那么停止，的顶点上，那么停止，否则，转否则，转S3。S3：当：当X中存在被标记但未被扫描的顶点时，选择一个被标中存在被标记但未被扫描的顶点时，选择一个被标记但未被扫描的记但未被扫描的X的顶点，比如的顶点，比如xi，用（用（xi）标记标记Y的所有的所有顶点，这些顶点被不属于顶点，这些顶点被不属于M

19、且尚未标记的边连到且尚未标记的边连到xi。现在顶点现在顶点xi是被扫描的。如果不存在被标记但未被扫描的顶是被扫描的。如果不存在被标记但未被扫描的顶点，那么转点，那么转S4。12/25/2022匈牙利算法（续）匈牙利算法（续）S4：如果在步骤如果在步骤S3没有新的标记被标记到没有新的标记被标记到Y的顶点上，那的顶点上，那么停止，否则，转么停止，否则，转S5。S5：当存在当存在y被标记但未被扫描的顶点时。选择被标记但未被扫描的顶点时。选择Y的一个的一个被标记但未被扫描的顶点，比如被标记但未被扫描的顶点，比如yj，用（用（yj）标记标记X的的顶点，这些顶点被属于顶点，这些顶点被属于M且尚未标记的边连

20、到且尚未标记的边连到yj。现在，现在，顶点顶点yj是被扫描的。是被扫描的。如果不存在被标记但未被扫描的顶点，那么转如果不存在被标记但未被扫描的顶点，那么转S2。然后进行匹配关系扩展。如果无法进行扩展，那么然后进行匹配关系扩展。如果无法进行扩展，那么M就是就是最大匹配，结束，否则转最大匹配，结束，否则转S1。12/25/2022匹配关系扩展过程匹配关系扩展过程 如果如果Y中所有被标记的顶点都是中所有被标记的顶点都是M的某条边的端点，那的某条边的端点，那么么M已是一个最大匹配，结束查找。如果已是一个最大匹配，结束查找。如果Y的顶点的顶点yj被标被标记，且没有一条以记，且没有一条以yj为端点的边是为

21、端点的边是M的匹配边，那么需要的匹配边，那么需要进行增广路径的扩展，即通过取反操作实现扩展。进行增广路径的扩展，即通过取反操作实现扩展。12/25/2022最大匹配与增广路调整举例最大匹配与增广路调整举例 12/25/2022第一轮操作第一轮操作 图图10-10 10-10 第一轮操作第一轮操作 12/25/2022第二轮操作第二轮操作图图10-11 10-11 第二轮操作第二轮操作12/25/2022第三轮操作第三轮操作图图10-12 10-12 第三轮操作第三轮操作12/25/2022关于增广路的三个结论关于增广路的三个结论 （1）P的路径长度必定为奇数，第一条边和最后一条边都不的路径长度

22、必定为奇数，第一条边和最后一条边都不属于属于M。（2）P经过取反操作可以得到一个更大的匹配经过取反操作可以得到一个更大的匹配M。（3）M为为G的最大匹配当且仅当不存在相对于的最大匹配当且仅当不存在相对于M的增广路径。的增广路径。12/25/2022匈牙利算法算法框架匈牙利算法算法框架void hungary()/匈牙利算法过程匈牙利算法过程 for(i=1;i=n;i+)if(DFS(i)/如果从如果从i的对应项出发有可增广路的对应项出发有可增广路 匹配数匹配数+;/那么匹配数加那么匹配数加1 输出匹配数输出匹配数;12/25/2022搜索过程搜索过程 bool DFS(int k)/寻找从寻

23、找从k出发的增广路出发的增广路 while(j与与k邻接邻接)if(j不在增广路上不在增广路上)把把j加入增广路加入增广路;if(j没有被标记的边连到没有被标记的边连到k 或者与或者与j相连的顶点相连的顶点x出发有可增广路出发有可增广路)则修改则修改j的对应项为的对应项为k，返回返回true;如果从如果从k的对应项出发没有可增广路，那么返回的对应项出发没有可增广路，那么返回false;12/25/202210.2.4 最小点覆盖与最小路径覆盖最小点覆盖与最小路径覆盖几个概念几个概念1)点覆盖点覆盖定义定义1：给定图给定图G（V，E），），V 是是V的一个子集。若的一个子集。若对于对于G的任何边

24、的任何边e，有顶点有顶点vV，使得使得v与与e相关联，则相关联，则称称v覆盖覆盖e，并称并称V 为为G的点覆盖集或简称点覆盖。的点覆盖集或简称点覆盖。设设V 是是G的点覆盖，若的点覆盖，若V 的任何真子集都不是的任何真子集都不是G的点覆盖，的点覆盖，则称则称V 是极小点覆盖。是极小点覆盖。G中顶点个数最少的点覆盖称为中顶点个数最少的点覆盖称为G的最小点覆盖，其顶点个数称为点覆盖数。的最小点覆盖，其顶点个数称为点覆盖数。12/25/2022几个概念几个概念2)边覆盖边覆盖 定义定义2：给定图：给定图G（V，E），），E 是是E的一个非空子集。的一个非空子集。若对于若对于G的任何顶点的任何顶点v，

25、都有边都有边eE，使得使得e与与v相关联，相关联，则称则称e覆盖覆盖v，并称并称E 为为G的边覆盖集或简称边覆盖。设的边覆盖集或简称边覆盖。设E 是是G的边覆盖，若的边覆盖，若E 的任何真子集都不是的任何真子集都不是G的边覆盖，的边覆盖，则称则称E 是极小边覆盖。是极小边覆盖。G中边数最少的边覆盖称为中边数最少的边覆盖称为G的的最小边覆盖，其顶点个数称为边覆盖数。最小边覆盖，其顶点个数称为边覆盖数。12/25/2022几个概念几个概念3)独立集独立集定定义义3 给给定定图图G（V，E），V 是是V的的一一个个非非空空子子集集。若若V 的的任任何何两两个个顶顶点点u，v都都不不是是同同一一条条边

26、边的的两两个个端端点点，则则称称V 是是G的的一一个个空空子子图图。设设V 是是G的的空空子子图图，若若V 任任意意增增加加一一个个G中中不不在在V 中中的的点点后后都都不不是是空空子子图图，则则称称V 是是G的的独独立立集集。G中中所所含含顶顶点点数数最最多多的的独独立集立集V 称为称为G的最大独立集。的最大独立集。12/25/2022几个概念几个概念4)支配集支配集定义定义4 设设G=（V，E）是无向简单图，是无向简单图，S是是V的一个非空子的一个非空子集。若对于不在集。若对于不在S中的中的G的点的点u，u与与S里至少一个顶点里至少一个顶点v相相关联，则称关联，则称S是图是图G的支配集。设

27、的支配集。设S是图是图G的支配集，若的支配集，若S的任何真子集都不是的任何真子集都不是G的支配集，则称的支配集，则称S为图为图G的极小支配的极小支配集。集。G中含顶点数最少的支配集中含顶点数最少的支配集S，称为称为G的最小支配集，的最小支配集，其顶点个数其顶点个数|S|称为图称为图G的支配数。的支配数。12/25/2022举例举例-无向简单图最小支配集无向简单图最小支配集 图图11-13 无向简单图最小支配集无向简单图最小支配集 12/25/2022几个概念几个概念5)最大团最大团定定义义5 给给定定图图G（V，E），V 是是V的的一一个个子子集集。若若V 的的任任意意两两个个顶顶点点都都相相

28、邻邻，则则称称V 是是G的的一一个个完完全全子子图图。若若V 不不包包含含在在G的的更更大大的的完完全全子子图图中中，则则称称V 是是G的的一一个个团团。G中中所所含含顶顶点点数数最最多多的的团团称称为为G的的最大团。最大团。6)补图补图定定义义6 对对于于任任一一无无向向图图G=（V，E），其其补补图图G*=(V，E*)定义为：定义为：(u，v)E*，当且仅当，当且仅当，(u，v)E。12/25/2022几个概念几个概念7)路径覆盖路径覆盖定义定义7 在一个有向图在一个有向图G中，如果在图中，如果在图G中有一些路经，中有一些路经，使之覆盖了图使之覆盖了图G中的所有顶点，且任何一个顶点有且中的

29、所有顶点，且任何一个顶点有且只有一条路径与之关联，那么这些路径称为只有一条路径与之关联，那么这些路径称为G的一个的一个路径覆盖。最小路径覆盖就是找出最小条数的路径，路径覆盖。最小路径覆盖就是找出最小条数的路径，使之成为使之成为G的一个路径覆盖。的一个路径覆盖。12/25/2022有用的结论有用的结论（1）团与独立集的关系。）团与独立集的关系。设设G*为无向图为无向图G的补图。的补图。U是是G的完全子图，当且仅当，的完全子图，当且仅当，U是是G*的空子的空子图；图；U是是G的团，当且仅当，的团，当且仅当，U是是G*的独立集；的独立集；U是是G的最大团，当且的最大团，当且仅当，仅当，U是是G*的最

30、大独立集。的最大独立集。（2）独立集与点覆盖的关系。）独立集与点覆盖的关系。设无向图设无向图G（V，E）中无孤立点。中无孤立点。U是是G的独立集，当且仅当，的独立集，当且仅当，VU 是是G的极小点覆盖；的极小点覆盖；U是是G的最大独立集，当且仅当，的最大独立集，当且仅当，VU 是是G的最小的最小点覆盖。点覆盖。12/25/2022有用的结论有用的结论（3）独立集合和支配集的关系。）独立集合和支配集的关系。设设G是无孤立顶点的图，则是无孤立顶点的图，则G的极大独立集必为极小支配集，其逆的极大独立集必为极小支配集，其逆不真。不真。（4）二分图的最大独立集与最小边覆盖的关系。）二分图的最大独立集与最

31、小边覆盖的关系。如果如果G（V，E）是连通的二分图，那么是连通的二分图，那么G的最大独立集点数的最大独立集点数D等等于于G的最小边覆盖的最小边覆盖EC数，即数，即D=EC。（5）二分图的最大独立集与最大匹配的关系。二分图的最大独立集与最大匹配的关系。二分图二分图G的最大独立集点数的最大独立集点数D等于等于G的顶点数的顶点数|V|减去减去G的最大匹配数的最大匹配数m，即，即D+m=|V|。12/25/2022有用的结论有用的结论（6）二分图的最大匹配数与最小边覆盖的关系。）二分图的最大匹配数与最小边覆盖的关系。如果如果G（V，E）是连通的二分图，那么是连通的二分图，那么G的最大匹配数的最大匹配数

32、m与与G的最的最小边覆盖数小边覆盖数EC之和等于之和等于G的顶点集，的顶点集，m+EC=|V|。（7）二分图的最大匹配与最小点覆盖的关系二分图的最大匹配与最小点覆盖的关系Knig定理：一个二分图定理：一个二分图G中的最大匹配数中的最大匹配数m等于等于G的最小点覆盖数的最小点覆盖数C，即，即m=C。（8）无圈有向图的路径覆盖与二分图匹配的关系。无圈有向图的路径覆盖与二分图匹配的关系。构建与构建与G对应的一个二分图对应的一个二分图G*。G的最小路径覆盖数的最小路径覆盖数V G的最大匹配数的最大匹配数m。12/25/2022举例举例-无圈有向图与对应的二分图无圈有向图与对应的二分图 12/25/20

33、2210.2.5 二分图最优匹配二分图最优匹配 给定一个二分图给定一个二分图 G，其中边（其中边（x，y）有权有权w(x，y)，现在现在要找一个从要找一个从X到到Y具有最大权和的匹配具有最大权和的匹配M，这就是二分图最这就是二分图最优匹配问题。优匹配问题。12/25/2022二分图最优匹配问题的数学描述二分图最优匹配问题的数学描述 记记X=x1，x2，xn，Y=y1，y2，yn。该问题该问题可表为可表为 给定给定 nn矩阵矩阵W，求求 1，2，3，n的一个排列的一个排列 使得使得极大。极大。图示：图示：12/25/2022等同子图等同子图 G中一个可行的顶点标记函数是中一个可行的顶点标记函数是

34、X Y上的实值函数上的实值函数L，使使得对所有得对所有x X，y Y，有有 L(x)+L(y)w(x，y)。如如L可行，记可行，记EL=(x,y)|(x,y)E(G)，L(x)+L(y)=w(x,y)，以，以EL为边集的的生成子图称为为边集的的生成子图称为L的等同子图，记作的等同子图，记作GL。定理：若定理：若L是是G的可行标记，的可行标记，M是是GL的从的从X到到Y的完全匹的完全匹配，则配，则M是是X到到Y的最优匹配。的最优匹配。12/25/2022 Kuhn-Munkres算法流程算法流程（1）对二分图）对二分图 G 进行任意可行顶点标号进行任意可行顶点标号 L。（2）确定对应于确定对应于

35、 L 的等同子图的等同子图 GL 的无权边集的无权边集EL。（3）寻找等同子图寻找等同子图 GL 中的一个任意的初始化匹配中的一个任意的初始化匹配 M。（4）使用使用Kuhn-Munkres算法（即匈牙利方法）产生最优算法（即匈牙利方法）产生最优匹配。匹配。12/25/2022Kuhn-Munkres算法算法（1）选定初始可行顶点标号）选定初始可行顶点标号L，确定确定GL，在，在G中选取一个中选取一个匹配匹配M。（2）若）若X中顶点皆被中顶点皆被M匹配，则停止，匹配，则停止，M即为即为G的最优匹配；的最优匹配；否则，取否则，取GL中未被匹配的中未被匹配的X顶点顶点u，令，令S=u，T=。以以下

36、记下记 是是GL中的相邻顶点集。中的相邻顶点集。（3）若）若 T，转（转（4）；若）；若 =T，取取12/25/2022Kuhn-Munkres算法算法-续续再记再记 ，。（4）选）选 中一顶点中一顶点y，若，若y已被已被M的边关联，设的边关联，设X中中的的z与与y构成匹配边，则记构成匹配边，则记 S=S z，T=T y。转（转（3）；否则，取）；否则，取GL中中X到到Y的一个的一个M可增广路可增广路Path(u,y)，令令M=(M-E(Path)(E(Path)-M)，转（转（2）。这里，）。这里，E(Path)是路径是路径Path上的边组成的集合。上的边组成的集合。工作分配工作分配 12/25/2022