主要定理二分图的最大匹配算法二分图的带权重的最大匹配ppt课件.ppt
《主要定理二分图的最大匹配算法二分图的带权重的最大匹配ppt课件.ppt》由会员分享,可在线阅读,更多相关《主要定理二分图的最大匹配算法二分图的带权重的最大匹配ppt课件.ppt(83页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值第第6章章 图与网络分析图与网络分析6.7 最大匹配问题最大匹配问题2023/1/14资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值2023/1/14山东大学 软件学院2最大对集(匹配)问题二分图的对集,基本概念,主要定理二分图的对集,基本概念,主要定理二分图的最大匹配算法二分图的最大匹配算法二分图的带权重的最大匹配二分图的带权重的最大匹配分派问题及算法分派问题及算法资金是运动的价值,资金的价值
2、是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值2023/1/14山东大学 软件学院3基本概念资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值2023/1/14山东大学 软件学院4使用最大流算法求二分图上的最大匹配给定二分图给定二分图G=(V,U,E),构造流网络。,构造流网络。增加一个源点增加一个源点 s,从,从 s 到到 V 中每个顶点引一条有向边。中每个顶点引一条有向边。增加一个目标顶点增加一个目标顶点 t,从,从 U 中每个顶点向中每个顶点向 t 引一条有向边。引
3、一条有向边。E中的边均从中的边均从 V 指向指向 U。记得到的流网络为记得到的流网络为G=(V,E)。G中的每条边均为单位容中的每条边均为单位容量。量。计算计算G上从上从 s 到到 t 的最大流。的最大流。E 中的饱和边即构成中的饱和边即构成 G 上的一个最大匹配。上的一个最大匹配。资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值2023/1/14山东大学 软件学院5例子资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值2023/1/14山东大学
4、 软件学院6定理定理定理:记:记G上的最大流为上的最大流为f*,流值为,流值为|f*|。G上的最大匹配为上的最大匹配为M*。则。则|f*|=|M*|。证明证明:首先证:首先证|f*|M*|。给定最大匹配给定最大匹配M*,令,令G上上M*中的边的流值为中的边的流值为1,s到到M*匹匹配的配的V一侧点的各条边上流值为一侧点的各条边上流值为1,M*匹配的匹配的U一侧点到一侧点到t的的各条边上流值为各条边上流值为1,则构造了一个流值为,则构造了一个流值为|M*|的流的流f。因此,显然有因此,显然有|f*|M*|。再证再证|f*|M*|。设设f*为为G上的最大流。上的最大流。由整流定理,由整流定理,G上
5、每条边上的流值为整数。由于每条边的上每条边上的流值为整数。由于每条边的容量均为容量均为1,因此,因此G上每条边的流值不是上每条边的流值不是0就是就是1。资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值2023/1/14山东大学 软件学院7证明再由流守恒约束,再由流守恒约束,V中每个顶点最多有一条出去的边流值为中每个顶点最多有一条出去的边流值为1。同理,。同理,U中每个顶点最多有一条进来的边流值为中每个顶点最多有一条进来的边流值为1。记记M=e E|e上的流值上的流值 0,因此,因此M中的任何两条边均不中的任何两条边均不
6、共享顶点,即,共享顶点,即,M是一个匹配,且是一个匹配,且|f*|=|M|。因此,显然有因此,显然有|f*|M|。资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值2023/1/14山东大学 软件学院8基本概念资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值2023/1/14山东大学 软件学院9顶点覆盖资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值2023/1/14山东
7、大学 软件学院10定理6.8.1资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值2023/1/14山东大学 软件学院11证明资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值2023/1/14山东大学 软件学院12通过增广路求二分图上的最大匹配资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值2023/1/14山东大学 软件学院13二分图上最大匹配的标号算法资金是运动的价值
8、,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值2023/1/14山东大学 软件学院14二分图上最大匹配的标号算法资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值2023/1/14山东大学 软件学院15二分图上最大匹配的标号算法资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值2023/1/14山东大学 软件学院16例子12345678910资金是运动的价值,资金的价值是随时间变化而变化
9、的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值2023/1/14山东大学 软件学院17例子12345678910找到一条增广路找到一条增广路(1,7)。更新。更新M。1资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值2023/1/14山东大学 软件学院18例子12345678910找到一条增广路找到一条增广路(2,8)。更新。更新M。22资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值2023/1/14山东大学
10、软件学院19例子12345678910找到一条增广路找到一条增广路(3,10)。更新。更新M。3333资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值2023/1/14山东大学 软件学院20例子12345678910找到一条增广路找到一条增广路(4,10,3,9)。更新。更新M。41033资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值2023/1/14山东大学 软件学院21例子12345678910找不到增广路,结束。找不到增广路,结束。55
11、51087资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值2023/1/14山东大学 软件学院22例子12345678910红边红边为最大匹配,为最大匹配,蓝色顶点蓝色顶点为顶点覆盖。为顶点覆盖。5551087资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值2023/1/14山东大学 软件学院23时间复杂度分析资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值2023/1
12、/14山东大学 软件学院24解释从从S中未匹配的顶点开始,标号找中未匹配的顶点开始,标号找M-增广路的过程,实际上增广路的过程,实际上是一个从是一个从S中未匹配的顶点开始进行广度优先搜索的过程。中未匹配的顶点开始进行广度优先搜索的过程。该过程与标准的广度优先搜索不完全相同。该过程与标准的广度优先搜索不完全相同。设搜索树的根位于第设搜索树的根位于第1层。区别仅在于,在搜索过程中,奇层。区别仅在于,在搜索过程中,奇数层顶点(在数层顶点(在S一侧)按广度优先展开;偶数层顶点(在一侧)按广度优先展开;偶数层顶点(在T一侧)按一侧)按M中的(唯一一条)边顺延(而不是按广度优先展中的(唯一一条)边顺延(而
13、不是按广度优先展开)。开)。资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值2023/1/14山东大学 软件学院25解释资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值2023/1/14山东大学 软件学院26标号,找增广路v2v2u2u6v3v5v5u3u4u5v1资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值2023/1/14山东大学 软件学院27找增广路过程中形成
14、的搜索树虚线表示v5,u3相邻,但在对v5进行检查的过程中,u3已经标号,因此从v5不能对u3标号。资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值2023/1/14山东大学 软件学院28增广,得到一个更大的匹配资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值2023/1/14山东大学 软件学院29广度优先搜索的观点构造的辅助图从辅助图上入度为0的点v2开始的广度优先搜索资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推
15、移而增值,其增值的这部分资金就是原有资金的时间价值2023/1/14山东大学 软件学院30辅助图的构造顶点集顶点集=V。从从v1到到v2有一条有向边,当且仅当有一条有向边,当且仅当 v2是从是从v1开始的增广路上开始的增广路上下一个下一个V中的顶点。中的顶点。资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值2023/1/14山东大学 软件学院31Hall定理资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值2023/1/14山东大学 软件学院32
16、证明资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值2023/1/14山东大学 软件学院33证明资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值2023/1/14山东大学 软件学院34证明资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值2023/1/14山东大学 软件学院35Knig定理资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,
17、其增值的这部分资金就是原有资金的时间价值2023/1/14山东大学 软件学院36Knig定理资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值2023/1/14山东大学 软件学院37Knig定理资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值2023/1/14山东大学 软件学院38指派问题:二分图上带权重的最大匹配实例:二分图实例:二分图G=(S,T,E),边上定义有非负权重,边上定义有非负权重we。询问:图询问:图G上的一个匹配上的一个匹配M,
18、使得总权重,使得总权重e M we最大。最大。1291018工人任务资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值2023/1/14山东大学 软件学院39将指派问题归约到最小费用流问题1.先进行预处理。先进行预处理。通过增加权重为通过增加权重为0的边,可以假定的边,可以假定G是完全二分图。这是因是完全二分图。这是因为权重为为权重为0的边对最大权重匹配不产生影响。的边对最大权重匹配不产生影响。若若S一侧和一侧和T一侧的顶点数目不一样多,比如一侧的顶点数目不一样多,比如|S|=m 0的顶点的顶点i出发的出发的增广路。增广
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 主要 定理 二分 最大 匹配 算法 权重 ppt 课件
限制150内