9.3 二部图中的匹配

数学学习 · 爱知数学讲义

18
本章目录 · 1 节

本章导读

【定义9.3.1:二部图的完备匹配】设 ,。匹配 若满足 ,即使 中每点均饱和,称从 到 的完备匹配。它必最大;最大匹配却可能仍不能饱和 。只有两部大小相等时,完备匹配才同时是饱和全部顶点的完美匹配。

abc1234
图9.3.1(a):三点部到四点部的完备匹配,实线为匹配边
abc1234
图9.3.1(b):另一种有完备匹配的二部图
abc1234
图9.3.1(c):最大匹配只有两边,不能饱和上方三个点

把上方三点依次记为 ,下方四点依次为 。图(a)邻集分别为 、、,实线给出 。图(b)邻集为 ,实线给出 。图(c)中 都只能邻接下方1点,故最多匹配其中一个; 可匹配下方另一点,所以最大值为2,而不是3。

【定理9.3.1:Hall定理】二部图存在从 到 的完备匹配,当且仅当对每个 都有

这称相异性条件。空集情形自动成立,教材按 表述。这里数的是不同邻点,而非把各点的度相加;邻集重合时不能重复计数。

必要性:完备匹配把 中各点匹配给互不相同的邻点,所以至少需要 个邻点。充分性:取最大匹配,若 尚未饱和,从 出发沿非匹配边由左向右,再沿匹配边由右向左,找出全部可达点;设左部可达集为 、右部为 ,包括 。

任何 中顶点都必须饱和,否则得到增广路径。它们的匹配伙伴均在 ;反过来每个 中点都是经其匹配边到达,故 。左侧可达点的全部邻点都在 中,因此 ,违反Hall条件。故不存在未饱和的左侧顶点,最大匹配就是完备匹配。

图(c)取 ,只有一个不同邻点,直接给出失败证据。图(a)、(b)则对全部非空左侧子集都满足条件。

【定理9.3.2:t条件】若存在正整数 ,使左部每点度至少为 ,右部每点度至多为 ,则存在左到右完备匹配。对任意 ,从 出发至少有 条边,这些边全部落在 ;每个右点至多承接 条,故

除以 ,得到Hall条件。这是充分条件而非必要条件。图(a)左部最小度2,右部最大度3,不可能同时有 、,却仍有已画出的完备匹配。图(b)可取 。

【例9.3.1:毕业生与部门分配】三名毕业生A、B、C与五个部门的双向意愿如下:A可去部门1、2、3;B可去2、4、5;C可去3、4、5。每部门最多接收一人,问能否让三人都去到双方同意的部门。

v1v2v3u1u2u3u4u5
图9.3.2:上方v1、v2、v3为A、B、C,下方u1至u5为部门

【解】建立上述二部图,三人各有3个邻点,任一部门至多有2个候选人,因此可取 ,也可取 ,均符合条件。完备匹配存在。例如A到1、B到2、C到3;或A到3、B到2、C到5。每个方案均选三个不同部门,不能让两人占同一岗位。图与意愿表的九条边逐项对应,不把单方面意愿加进来。

【例9.3.2:视频镜头检索的最大权匹配模型】镜头由连续的帧组成,视频检索可分片段、镜头和图像等层次。设查询镜头有帧 ,候选镜头有帧 ,由图像相似度得到 。构造带权完全二部图,每条 的权为 ,匹配的权为

【解】匹配保证每帧最多与对方一帧对应;最大化的是相似度总权,不能只先最大化边数而忽视具体权值。对库中各镜头求这个最大值,再选择分数最高者。因为此模型完整且权非负,总能把一个最优匹配扩展到饱和较小一部而不降低权,但总分可能大于1,并非已经归一化的概率。

原模型不强制帧的时间先后关系,也不消除镜头长度造成的总分差异。若实际检索要求保持时间顺序或比较不同长度镜头,需要另加顺序约束或约定归一化方式;不能误把这些性质当成现有公式已经保证。最大匹配与最大权匹配都有专门算法,本例的重点是明确顶点、权和目标函数的含义。