2.11.7 二分图匹配

1. 图示
   观察依据

   左侧椭圆内包含一个蓝色字母G和四个蓝色顶点。

2. 声音
   观察依据

   教师将这两组顶点分别称为女孩和男孩，即G和B。

G

在此例中，左侧顶点集表示女孩一侧的顶点集合。

如图所示，它是一个包含四个顶点的有限集。

1. 图示
   观察依据

   右侧椭圆内包含一个橙色字母B和四个橙色顶点。

2. 声音
   观察依据

   教师将这两组顶点分别称为女孩和男孩，即G和B。

B

在此例中，右侧顶点集表示男孩一侧的顶点集合。

如图所示，它是一个包含四个顶点的有限集。

1. 声音
   观察依据

   教师指出，在二分图中，顶点被划分为左侧顶点和右侧顶点，且每个顶点非左即右。

left vertex / right vertex

这是二分图定义中的两类顶点；边仅允许出现在左侧顶点与右侧顶点之间。

适用于简单图的顶点划分。

1. 图示
   观察依据

   黑色线段连接G中的顶点与B中的顶点，底部标有“compatible”一词。

2. 声音
   观察依据

   教师指出，边表示女孩与男孩配对时的相容性约束。

edge

表示一种相容关系，允许来自两侧的两个顶点之间配对。

仅连接 G 与 B 中的顶点对。

1. 图示
   观察依据

   四条品红色边被高亮显示，底部文字显示‘一个匹配’。

2. 声音
   观察依据

   教师说：将每位女孩匹配到一位唯一的相容男孩，并正式补充道：我们需要一个从女孩集合到男孩集合的双射，且该双射必须沿边实现。

matching

一种沿边从 G 到 B 的配对方案；本例中，目标是为每位女孩分配一位唯一的男孩。

图中所示的例子是一个覆盖全部四个 G 顶点的匹配。

1. 图示
   观察依据

   左侧椭圆标记为 G，包含四个蓝色顶点。

2. 声音
   观察依据

   主讲人将左侧称为女孩。

G

二分图的左侧部分，代表女孩集合。

二分图中的一个有限顶点集。

1. 图示
   观察依据

   右侧椭圆标记为 B，包含四个橙色顶点。

2. 声音
   观察依据

   主讲人将右侧称为男孩。

B

二分图的右侧部分，代表男孩集合。

二分图中的一个有限顶点集。

1. 公式
   观察依据

   幻灯片在图的左侧写上 S，并随后定义瓶颈：一个女孩集合 S，其对应的男孩数量不足。

2. 声音
   观察依据

   主讲人说：“如果你在左侧有一个女孩集合 S。”

S

用于检验瓶颈的左侧顶点（女孩）的一个子集。

S 是 G 的子集。

1. 公式
   观察依据

   幻灯片在右侧写出了 $E(S)$，随后说明 $E(S)$ ∷∶ S 中至少与一名女生相邻的男生。

2. 声音
   观察依据

   主讲人称其为“S 在边关系下的像”，并解释为所有与 S 中至少一名女生相容的男生。

$E(S)$

S 在 B 中的邻域：即至少与 S 中一名女生相邻的男生组成的集合。

$E(S)$ 是 B 的子集。

1. 公式
   观察依据

   幻灯片显示 |S| = 3，随后指出 |S| > |$E(S)$|。

2. 声音
   观察依据

   主讲人说：“S 的大小大于 S 的像的大小。”

|S|

集合 S 的基数（即元素个数）。

一个非负整数。

1. 公式
   观察依据

   幻灯片显示 2 = |$E(S)$|，随后指出 |S| > |$E(S)$|。

2. 声音
   观察依据

   主讲人比较了 S 与 $E(S)$ 的大小。

|$E(S)$|

邻域集 $E(S)$ 的基数（即元素个数）。

一个非负整数。

1. 声音
   观察依据

   教师给出定义：二分图是一种图，其中存在一些顶点称为左顶点，另有一组与之不相交的顶点称为右顶点；每个顶点必属于左顶点或右顶点之一，且所有边都仅连接一个左顶点与一个右顶点。

2. 图示
   观察依据

   屏幕显示两个分离的椭圆，一个包含 G 顶点，另一个包含 B 顶点，随后仅绘制跨越两个椭圆之间的边。

视频将二分图定义为：其顶点集可划分为两个不相交的集合，通常称为左顶点和右顶点；每个顶点恰好属于其中一侧，且每条边都连接一个左顶点与一个右顶点。

1. 该图是一个简单图

2. 顶点集被划分为两个互不相交的子集

3. 每条边的两个端点分别属于两侧

1. 声音
   观察依据

   讲师说明匹配问题时指出：每位女生愿意与某些男生配对，但并非所有男生；并用添加边的方式表示这种相容性。

2. 图示
   观察依据

   黑色边连接集合 G 与集合 B 中的部分顶点对，底部文字“compatible”表明这些边代表相容关系。

3. 字幕依据
   观察依据

   底部文字：为每位女生匹配一位唯一且相容的男生。

视频将匹配问题置于二分图框架下：左右两侧分别代表两类对象，边表示允许的配对关系，目标是为左侧每个对象分配一个右侧中不同且相容的对象。

1. 给定一个二分图

2. 边表示允许的配对关系

3. 目标是为左侧顶点建立一一对应的配对

1. 二分图的定义

1. 声音
   观察依据

   讲师正式指出：我们希望构造一个从女生集合到男生集合的双射，且该映射必须沿边进行。

2. 图示
   观察依据

   品红色高亮的边表明：每个 G 顶点恰好有一条被选中的边，且这些边的另一端点落在四个互不相同的 B 顶点上。

视频将所期望的匹配形式化为从集合 G 到集合 B 的一个双射，且该双射必须沿着图中的边进行。也就是说，每位女孩必须被分配给一位男孩，不能有两位女孩被分配给同一位男孩，且每一次这样的分配都必须对应图中一条已存在的相容边。

1. 该映射在集合 G 的所有元素上都有定义

2. 该映射的值域属于集合 B

3. 该映射是一个双射

4. 每一对像与原像之间必须由图中的一条边相连

1. 二分图的定义
2. 二分图匹配问题的设定

1. 图示
   观察依据

   一个二分图由两个椭圆组成，分别标记为 G 和 B，每个椭圆内含四个顶点，且椭圆之间画有若干条边。

2. 声音
   观察依据

   主讲人将左侧顶点描述为女孩，右侧顶点描述为男孩，并讨论哪些人整体上彼此相容。

视频中使用了一个二分图，左侧顶点为 G（女孩），右侧顶点为 B（男孩）；边表示某位女孩与某位男孩之间的相容关系；一个匹配是指利用边将左右两侧顶点进行配对，使得每个顶点至多被使用一次。

1. 该图是二分图，其两部分分别为 G 和 B。

2. 边表示 G 与 B 之间允许的配对关系。

1. 公式
   观察依据

   幻灯片上写出 $E(S)$，随后定义 $E(S)$ ::= 与 S 中至少一位女孩相邻的男孩集合。

2. 声音
   观察依据

   主讲人指出，$E(S)$ 是集合 S 在边关系下的像，即所有与 S 中一位或多位女孩相容的男孩组成的集合。

对于左侧顶点的一个子集 S，$E(S)$ 表示至少与 S 中一个顶点相邻的右侧顶点所构成的集合；在示例中，S 包含三位女孩，而 $E(S)$ 则包含这三位女孩共同喜欢的两位男孩。

1. S 是 G 的子集。

2. 邻接关系基于给定的二分图定义。

1. 用于匹配问题的二分图建模

1. 公式
   观察依据

   幻灯片显示 |S| > |$E(S)$|，随后文字说明：瓶颈——一组女孩集合 S，其可匹配的男孩数量不足。

2. 声音
   观察依据

   主讲人说：“瓶颈的定义是：若存在一个集合，其大小 |S| 大于该集合在右侧的像集大小 |$E(S)$|，则称该集合构成一个瓶颈。”

瓶颈是指左侧顶点的一个子集 S，其在右侧的邻域 $E(S)$ 的大小严格小于 S 自身的大小。直观地说，这些女孩没有足够多互不相同的、与之相容的男孩可供各自单独匹配。

1. S 是 G 的子集。

2. $E(S)$ 是 S 在 B 中的邻域。

1. 在边关系下某集合的邻域／像

1. 图示
   观察依据

   幻灯片标题为“霍尔定理”，正文内容：“反之，若不存在瓶颈，则存在匹配。这一点并不显然，我们将在下一环节讨论。”

该幻灯片呈现了霍尔定理在二部图匹配中的逆向结论，即：若不存在瓶颈，则必存在完美匹配。

1. 适用于二部图

2. 要求满足‘不存在瓶颈’这一条件

1. 声音
   观察依据

   讲师明确指出，边仅存在于左侧顶点与右侧顶点之间

2. 图示
   观察依据

   此后所画的所有黑色边均连接左侧椭圆内的顶点与右侧椭圆内的顶点

在二分图中，每条边的两个端点分别属于左侧顶点集与右侧顶点集

1. 该图是二分图

2. 顶点集已被划分为左侧顶点与右侧顶点

对所有边成立

1. 图示
   观察依据

   四条品红色高亮边，每条边来自一个G顶点，终点为四个互不相同的B顶点。

2. 声音
   观察依据

   讲师指出，存在一种匹配示例：每位女孩都恰好有一条高亮的品红色边，且这些边分别指向不同的男孩。

在当前这个二分图示例中，可以为每位女孩选择一条相容边，使得她们被匹配到互不相同的男孩。

1. 利用给定的黑色相容边集合

存在一组所选边满足全部条件。

1. 图示
   观察依据

   一条红色虚线标记了一条原先被使用的边，随后该边消失。

2. 声音
   观察依据

   讲师说，假设那条边缺失……最后一位女孩便无法再匹配到第二位男孩，而此前我们正是这样匹配的。

若将示例匹配中所用的那条边移除，则该特定匹配将不再可行。

1. 继续沿用之前给出的示例匹配

2. 被移除的边正是该匹配中实际使用的一条边

该结论对这条特定的边和这个特定的匹配成立

1. 公式
   观察依据

   幻灯片标题为‘瓶颈引理’，正文陈述为：若存在瓶颈，则显然无法实现匹配。

2. 声音
   观察依据

   主讲人说：“一旦存在瓶颈，就不可能完成匹配。这是显而易见的。”

若一个二分图存在瓶颈 S，则不存在完美匹配。

1. 存在左侧顶点的一个子集 S。

2. S 的元素个数大于 $E(S)$ 的元素个数。

对于左部的任意子集 S。

1. 公式
   观察依据

   幻灯片标题为“霍尔定理”，其陈述为：反之，若不存在瓶颈，则存在一个匹配。

2. 声音
   观察依据

   说话人说：“现在有一个相当深刻的定理：反之，若不存在瓶颈，则实际上存在一个匹配。这被称为霍尔定理。”

1. 幻灯片中使用了非正式说法“存在一个匹配”；在此语境下，它被呈现为保证匹配存在的逆向条件，但其确切的形式化范围（即所有女孩均被完美匹配）并未在屏幕上完全阐明。

反之，若不存在瓶颈，则存在一个匹配。

1. 不存在左部顶点的子集 S，使得 |S| > |$E(S)$|。

对左部的所有子集 S。

1. 动画
   观察依据

   首先出现两个互不相交的顶点集 G 和 B；接着添加黑色的相容边；最后高亮显示四条品红色的匹配边。

2. 声音
   观察依据

   讲师逐步讲解：二部图的结构、边如何表示相容性、为每位女孩分配一位唯一且相容的男孩这一目标，并给出一个匹配的具体示例。

1. 公式

   $$$$
   解释

   首先引入两个互不相交的顶点集 G 和 B。

   步骤依据

   这是视频开头所确立的二部图场景。

   视频直接表达
2. 公式

   $$$$
   解释

   接着在 G 和 B 之间添加若干条黑色边，代表允许的相容配对。

   步骤依据

   讲师说明边表示相容性约束。

   视频直接表达
3. 公式

   $$$$
   解释

   目标是为每位女孩分配一位唯一且相容的男孩。

   步骤依据

   底部文字与口头讲解共同阐明了问题的目标。

   视频直接表达
4. 公式

   $$$$
   解释

   最后高亮显示四条品红色边，构成一种配对：每个 G 中的顶点恰有一条向外的边，且所有终点均为互不相同的 B 中顶点。

   步骤依据

   教师将此称为一个匹配示例，并进一步正式指出：我们需要一个从女孩集合到男孩集合的双射，且该双射所对应的每一对必须沿着图中的边进行。

   视频直接表达

视频通过动画，将二分图的匹配思想、相容边以及沿边进行的双射，具象化为一个可视化的实例。

1. 动画
   观察依据

   一条红色虚线标记了原匹配中的一条边，随后该边被移除。

2. 声音
   观察依据

   教师说：假设那条边缺失……那么最后一位女孩便无法再与第二位男孩匹配……因此我们尝试寻找另一种匹配方式。

1. 本片段结束时，视频并未说明是否存在另一种匹配。

1. 公式

   $$$$
   解释

   首先，固定一个此前已找到的匹配。

   步骤依据

   教师明确指出：我们在该匹配中使用了那条边。

   视频直接表达
2. 公式

   $$$$
   解释

   假设这条已被使用的边并不存在。

   步骤依据

   教师说：假设那条边缺失。

   视频直接表达
3. 公式

   $$$$
   解释

   因此，原先将最后一位女孩匹配给第二位男孩的这一步骤便不再可行。

   步骤依据

   教师直接指出：最后一位女孩如今无法再与第二位男孩匹配。

   视频直接表达
4. 公式

   $$$$
   解释

   因此，我们需要寻找另一个匹配。

   步骤依据

   教师接着说道：“我们来尝试寻找其他匹配。”

   视频直接表达

本段仅完成如下推理：移除这条边会破坏原有的匹配；但本段并未就此得出是否存在另一匹配的结论。

1. 图示
   观察依据

   三个左部顶点被方括号框出并标记为3；它们的关联边仅通向两个右部顶点，这两个顶点被方括号框出并标记为2。

2. 声音
   观察依据

   说话人解释道：三名女孩共同喜欢的男孩仅有两名，因此男孩数量不足以满足分配需求，并由此得出结论：匹配不可能实现。

1. 公式

   $$|S|=3$$
   解释

   左侧被高亮的子集 S 包含三名女孩。

   步骤依据

   直接从图中的括号标签3读取。

   视频直接表达
2. 公式

   $$|E(S)|=2$$
   解释

   那三位女生仅与右侧的两位男生相邻。

   步骤依据

   直接从图中的括号标签2及高亮显示的边读取。

   视频直接表达
3. 公式

   $$|S|>|E(S)|$$
   解释

   由于$3 > 2$，子集 S 构成一个瓶颈。

   步骤依据

   屏幕上显示的两个基数之间的比较。

   视频直接表达
4. 公式

   $$\text{no match is possible}$$
   解释

   因为三位女生需要三位互不相同的配对对象，但仅有两位相容的男生存在，因此无法构造覆盖全部女生的匹配。

   步骤依据

   说话者陈述的鸽巢原理式计数论证。

   视频直接表达

该例子展示了一个瓶颈，从而证明该图中不存在匹配。

1. 公式
   观察依据

   幻灯片将该例子推广至子集 S、S 的邻域 $E(S)$，以及条件 |S| > |$E(S)$|。

2. 声音
   观察依据

   说话者从具体例子过渡到瓶颈的一般定义。

1. 公式

   $$S \subseteq G$$
   解释

   任取左侧顶点的一个子集 S。

   步骤依据

   用语言表述为对前面高亮显示的‘三个女孩’示例的推广。

   视频直接表达
2. 公式

   $$E(S)$$
   解释

   观察集合 S 的邻域，即所有与 S 中至少一个顶点相邻的右侧顶点。

   步骤依据

   幻灯片中将其定义为与 S 中至少一个女孩相邻的男孩。

   视频直接表达
3. 公式

   $$|S|>|E(S)|$$
   解释

   若集合 S 的顶点数多于其邻域的顶点数，则称 S 为瓶颈。

   步骤依据

   这正是视频片段中所写、所讲的定义。

   视频直接表达

具体的3比2示例，是通用条件 |S| > |$E(S)$| 的一个实例。

1. 图示
   观察依据

   标题：相容的男生与女生——每侧各有四个顶点，随后画出两侧之间的边，并高亮显示一个匹配。

2. 声音
   观察依据

   教师围绕该图讲解二分图、相容边、匹配，以及移除某条边所产生的影响。

1. 图中每条黑边所连接的具体顶点编号并未以数字形式标出；其位置只能依据上下方位进行描述。

给定一个二分图，其中两组顶点各有四个，边表示相容关系，目标是为每个左侧顶点分配一个互不相同的右侧顶点。

1. 左侧集合 G 包含四个顶点

2. 右侧集合 B 包含四个顶点

3. 黑边表示允许的相容配对

4. 目标是为每个女生找到唯一相容的男生

从 G 到 B 寻找一个沿边匹配，并观察删除其中一条已用边所产生的影响。

1. 公式

   $$$$
   解释

   首先，构建二分图结构：两组互不相交的顶点。

   步骤依据

   视频开始时，两个椭圆分别代表 G 和 B。

   视频直接表达
2. 公式

   $$$$
   解释

   然后在 G 和 B 之间添加若干条边，表示哪些配对是允许的。

   步骤依据

   讲师指出，我们可以借助添加边来指定相容性。

   视频直接表达
3. 公式

   $$$$
   解释

   高亮显示四条品红色边，构成一个匹配，使得每位女孩都对应一位不同的男孩。

   步骤依据

   讲师称此为一种匹配示例，并正式说明它是一个沿边的双射。

   视频直接表达
4. 公式

   $$$$
   解释

   接着用一条红色虚线标记其中一条已用边，并将其移除。

   步骤依据

   讲师假设该边原本就不存在，并让这条边消失。

   视频直接表达
5. 公式

   $$$$
   解释

   移除后，依赖于该边的配对不再可行，因此我们必须寻找另一个匹配。

   步骤依据

   讲师指出，最后这位女孩不能再与第二位男孩配对，随后表示：‘让我们尝试寻找其他匹配。’

   视频直接表达

本片段给出的答案是：原图存在一个显见的匹配；移除该匹配中的一条边会使该匹配失效，但本片段并未说明是否存在其他匹配。

我们可以通过检查每个 G 顶点是否恰好有一条高亮的品红色边，且这些边的端点均为互不相同的 B 顶点，来验证原始匹配；在删除边之后，我们可以检查原始匹配中对应的那条边是否已消失。

1. 图示
   观察依据

   标题为‘相容的男孩与女孩’的幻灯片，在左侧高亮显示三位女孩，在右侧显示两位男孩，并用黄色边连接。

2. 声音
   观察依据

   主讲人指出有三位女孩，而她们共同喜欢的男孩只有两位，因此男孩数量不足以满足所有女孩。

判断所展示的二分图能否存在一个匹配，覆盖左侧高亮显示的三位女孩。

1. 一个二分图，其左侧顶点集为 G，右侧顶点集为 B。

2. 一个高亮显示的、包含三位女孩的子集 S。

3. 她们共同的邻域 $E(S)$ 中仅包含两名男生。

判断这三位女生是否可能实现匹配。

1. 公式

   $$|S|=3$$
   解释

   高亮显示的左侧子集包含三位女生。

   步骤依据

   从图中括号标签3处读取。

   视频直接表达
2. 公式

   $$|E(S)|=2$$
   解释

   仅有两名男生与这三位女生中的至少一位相邻。

   步骤依据

   从图中括号标签2及高亮显示的边处读取。

   视频直接表达
3. 公式

   $$3>2$$
   解释

   女生人数超过了可用的相容男生人数。

   步骤依据

   屏幕上显示的数值比较。

   视频直接表达
4. 公式

   $$\text{No match is possible!}$$
   解释

   因此，这三位女生无法全部匹配到互不相同的男生。

   步骤依据

   讲话者陈述的计数/鸽巢原理论证。

   视频直接表达

这组高亮显示的三位女生无法实现匹配。

该结论直接源于 |S| > |$E(S)$|，讲话者将其识别为瓶颈条件。

1. 图示
   观察依据

   标题页显示《计算机科学中的数学》，麻省理工学院 $6.042J/18.062J$，《二分图匹配》。

2. 声音
   观察依据

   讲师指出，稳定匹配问题就是二分图匹配问题的一个例子。

1. 标题文字

2. 课程信息

3. 讲师的小窗口

1. 从标题页过渡到示例图示

1. 主题始终是二分图匹配

本节将此前关于稳定匹配的讨论置于更广泛的二分图匹配主题之下。

1. 图示
   观察依据

   两个椭圆分别标为 G 和 B，每个椭圆内含四个点。

2. 声音
   观察依据

   讲师解释顶点被划分为两组，并给出二分图的定义。

1. 左侧椭圆标注为 G

2. 右侧椭圆标注为 B

3. 四个蓝色顶点

4. 四个橙色顶点

1. 最初仅显示顶点集，随后开始准备添加跨集合的边

1. 两组顶点始终保持分离

2. 每组顶点明显包含四个顶点

屏幕将二分图的抽象定义具象化：两个互不相交的顶点集分别置于左侧和右侧。

1. 动画
   观察依据

   多条黑色线段连接左侧顶点与右侧顶点。

2. 字幕依据
   观察依据

   底部出现单词 compatible。

3. 声音
   观察依据

   讲师指出，边表示相容性约束。

1. 图中每条边的端点数字未作数值标注。

1. 黑色跨侧边

2. 文本相容

1. 从两个无边集合过渡到一个具有若干允许配对的二分图

1. 这些边始终仅在集合 G 与集合 B 之间连接。

这些边定义了本题中哪些配对是被允许的。

1. 字幕依据
   观察依据

   底部文字首先显示‘将每位女孩匹配到一位唯一的相容男孩’，随后变为‘一个匹配’。

2. 动画
   观察依据

   四条品红色边被高亮显示，每条均从左侧的一个顶点出发，并终止于互不相同的右侧顶点。

3. 声音
   观察依据

   讲师正式表述为：我们希望构造一个从女孩集合到男孩集合的双射，且该双射须沿边进行。

1. 品红色高亮边

2. 文本描述一个匹配

1. 从所有相容的边中选出四条边构成一个匹配

1. 图 G 的每个顶点恰好关联一条被选中的边

2. 被选中边的 B 端点互不相同

该动画直接通过沿边追踪的方式，直观展示了匹配所体现的双射概念。

1. 字幕依据
   观察依据

   底部文字假设这条边缺失，该边以红色显示。

2. 动画
   观察依据

   一条红色虚线标记了原匹配中的一条边，随后该边消失。

3. 声音
   观察依据

   讲师指出，最后这位女生不再能与第二位男生配对……让我们尝试寻找其他配对方式。

1. 本片段结束时未展示任何新的匹配。

1. 红色虚线标记

2. 被移除的边

3. 剩余的黑色边和品红色边

1. 原匹配中使用的一条边被移除

2. 原匹配不再完备

1. 当前剩余的顶点集与剩余的边保持不变

本步骤采用反例式操作，以说明匹配对特定相容边的依赖性。

1. 动画
   观察依据

   黄色高亮显示所选的边和顶点；添加标有3和2的括号；字幕显示3个女孩且仅喜欢2个男孩；随后出现红色文字“无法匹配！”

1. 左侧椭圆G，包含四个蓝色顶点。

2. 右侧椭圆B，包含四个橙色顶点。

3. 三个被高亮的左侧顶点。

4. 两个被高亮的右侧顶点。

5. 被高亮顶点之间的黄色边。

6. 标有3和2的括号。

1. 所选的边和顶点被重新着色为黄色。

2. 左侧的一个括号标有3。

3. 右侧的一个括号标有2。

4. 出现文字说明：3个女孩且仅喜欢2个男孩。

5. 红色文字“无法匹配！”被添加。

1. 底层的二分图结构保持不变。

2. 左侧仍为 G，右侧仍为 B。

动画聚焦于一个包含三名女生的子集 S，并显示其邻域 $E(S)$ 仅包含两名男生，直观地演示了 |S| > |$E(S)$|。

1. 动画
   观察依据

   标签从数字括号变为符号化形式：左侧为 S，右侧为 $E(S)$，接着是 |S| = 3、2 = |$E(S)$|，最后是 |S| > |$E(S)$|。

1. 左侧的子集标签为 S。

2. 右侧的邻域标签为 $E(S)$。

3. 等式 |S| = 3 和 2 = |$E(S)$|。

4. 不等式 |S| > |$E(S)$|。

1. 数字标签被集合名称 S 和 $E(S)$ 所取代。

2. 具体的基数被写成等式。

3. 不等式 |S| > |$E(S)$| 被显著显示。

1. 仍引用同一高亮显示的子图。

2. 左右二分划分保持不变。

视觉序列将具体例子转化为瓶颈的一般定义。

1. 图示
   观察依据

   一张新幻灯片出现，标题为‘瓶颈引理’，其文字内容定义了瓶颈与 $E(S)$，随后明确陈述：‘若存在瓶颈，则不可能实现匹配。’

1. 标题：瓶颈引理。

2. 定义行：瓶颈——一个女孩集合 S，其对应男孩数量不足。

3. 定义行：$E(S)$ ::= 与 S 中至少一名女孩相邻的男孩集合。

4. 不等式 |S| > |$E(S)$|。

5. 陈述：若存在瓶颈，则不可能实现匹配，这是显然的。

1. 图示示例被替换为文字幻灯片。

2. 定义与引理陈述依次写出。

1. 术语 S、$E(S)$ 和瓶颈与上一张幻灯片保持一致。

讲座将该例子形式化为一个命名引理。

1. 图示
   观察依据

   一张标题为“霍尔定理”的幻灯片出现，其文字为：“反之，若不存在瓶颈，则存在匹配。这并不显然。下一环节讨论。”

1. 标题：霍尔定理。

2. 陈述：反之，若不存在瓶颈，则存在匹配。

3. 注：这并不显然。下一环节讨论。

1. 瓶颈引理幻灯片被替换为霍尔定理幻灯片。

2. 用绿色突出显示‘不存在瓶颈’和‘匹配’。

1. 瓶颈概念沿用自上一张幻灯片。

讲座将该逆命题作为霍尔定理引入，并将其证明延后。

1. 图示
   观察依据

   静态演示幻灯片，顶部左侧含一个小矩阵图示，标题为‘霍尔定理’，主体文字阐述瓶颈与匹配的关系。

1. 标题文字

2. 矩阵图示

3. 主体陈述文字

4. 主讲人视频画面

1. 幻灯片内容在整个2秒片段中保持静止。

该图示旨在详细讲解之前，先直观引入霍尔定理逆命题这一理论概念。

1. 声音
   观察依据

   讲师强调每位女孩必须对应唯一相容的男孩，并正式指出：我们需要一个从女孩集合到男孩集合的双射，且该双射必须沿图中的边实现。

2. 图示
   观察依据

   在高亮显示的匹配中，每位女孩恰好连接一条边，且不同女孩连接的男孩互不相同。

人们可能误以为只需为每位女孩任意指定一名男孩即可。

视频强调必须为每位女孩指定唯一相容的男孩，并在形式上要求存在一个从集合 G 到集合 B 的双射，且该双射必须沿图中的边实现。

1. 声音
   观察依据

   讲师明确指出：所有边仅存在于左侧顶点与右侧顶点之间。

2. 图示
   观察依据

   所有已画出的边均跨越两个椭圆之间；同一侧内部不出现任何边。

有人可能误以为二分图只需将顶点划分为两组，而边仍可任意连接。

视频中给出的定义要求每条边都必须恰好连接一个左侧顶点和一个右侧顶点。

1. 声音
   观察依据

   讲师仅说明原匹配中使用的那条边已不存在，最后一名女生不能再与第二名男生匹配，随后便说“让我们尝试寻找其他匹配”。

2. 图示
   观察依据

   本片段结束时并未展示任何新匹配的结果。

1. 本片段并未得出边被移除后匹配是否依然存在的结论。

有人可能误以为移除一条已被使用的边就意味着整个问题不再存在匹配。

在本片段中，视频仅证明了原匹配失效，并提示我们去寻找另一匹配；至于这样的匹配是否仍然存在，视频并未说明。

1. 公式
   观察依据

   霍尔定理幻灯片明确指出：‘并不显然’，接下来将讨论这一点。

2. 声音
   观察依据

   主讲人将显然的瓶颈引理与反向的一个相当深刻的定理进行了对比。

人们可能认为：如果瓶颈阻碍匹配，那么没有瓶颈的情形就自动同样容易证明。

视频明确将该逆命题标记为‘并不显然’，并指出它就是霍尔定理，将在接下来讨论。

1. 声音
   观察依据

   主讲人强调：三名女生共同喜欢的男生仅有两名，因此这些女生可分配的男生数量不足。

2. 图示
   观察依据

   被高亮显示的邻域中仅包含两名男生，尽管右侧整体拥有更多顶点。

人们可能认为匹配失败仅当整个右侧集合太小。

该例子表明：失败已出现在某个子集上——三名女生在其邻域中仅有两名相容的男生，因此阻碍发生在子集 S 的局部，而非整个 B 的全局。

1. 声音
   观察依据

   讲师说：“我们刚刚讨论的稳定匹配问题，就是二分图匹配问题的一个例子。”

视频将最近讨论的稳定匹配问题作为二分图匹配问题的一个实例来呈现，而该问题本身又建立在二分图结构之上。

1. 声音
   观察依据

   首先定义二分图，再将匹配问题解释为在此图上为每位男生找到唯一相容的女生。

理解匹配问题，首先要理解二分图中的左右顶点划分以及跨边的边限制。

1. 声音
   观察依据

   教师首先说‘为每位女孩匹配一位唯一的相容男孩’，然后正式表述为：我们希望构造一个从女孩集合到男孩集合的双射，且该双射必须沿边进行。

在此例中，为每位女孩分配一位唯一相容男孩的目标被形式化为一个沿边进行的双射。

1. 图示
   观察依据

   首先标出一个完备匹配，然后移除其中一条匹配边，并讨论其后果。

该示例图将‘沿边进行的双射’这一抽象定义具象化为四条可见的匹配边，并通过移除操作展示了其对边的依赖性。

1. 公式
   观察依据

   $E(S)$ 是在二分图结构引入之后定义的。

2. 声音
   观察依据

   主讲人借助图中的邻接关系来定义 $E(S)$。

邻域 $E(S)$ 是利用二分图的边来定义的。

1. 公式
   观察依据

   瓶颈的定义写作 |S| > |$E(S)$|，前提是 $E(S)$ 已被定义。

2. 声音
   观察依据

   主讲人通过比较集合 S 的大小与 S 的像的大小来定义瓶颈。

瓶颈是通过比较 |S| 与 |$E(S)$| 来定义的，因此邻域概念必须先于瓶颈定义出现。

1. 图示
   观察依据

   该示例展示了 |S|=3 且 |$E(S)$|=2，随后幻灯片将其推广为 |S|>|$E(S)$|。

2. 声音
   观察依据

   主讲人指出，该示例是所谓瓶颈的一种具体情形。

三位女孩/两位男孩的图示是通用瓶颈条件的一个具体实例。

1. 公式
   观察依据

   ‘瓶颈引理’幻灯片重述了瓶颈定义，然后断言：若存在瓶颈，则不可能实现匹配。

2. 声音
   观察依据

   主讲人直接从瓶颈的定义推导出该引理。

该引理以瓶颈为表述基础，且依赖于定义 |S| > |$E(S)$|。

1. 公式
   观察依据

   ‘霍尔定理’幻灯片开头写道：反之，若不存在瓶颈，则存在匹配。

2. 声音
   观察依据

   主讲人明确称此为前述观察结论的逆命题。

霍尔定理被表述为瓶颈引理的逆命题：不存在瓶颈保证存在匹配，而存在瓶颈则排除匹配的可能性。

1. 声音
   观察依据

   教师在此片段中给出了二分图的定义。

1. 二分图的定义

1. 字幕依据
   观察依据

   底部文字：为每位女孩匹配一位唯一的相容男孩。

2. 声音
   观察依据

   教师解释了匹配目标，并将其形式化为一个双射。

1. 二分图匹配问题的设定
2. 匹配的数学形式化：沿边定义的双射

1. 声音
   观察依据

   教师说：正式地，我们希望构造一个从女孩集合到男孩集合的双射，且该双射必须沿边进行。

1. 匹配的数学形式化：沿边定义的双射

1. 动画
   观察依据

   一条红色虚线标记了一条已被使用的边，随后该边被移除。

2. 声音
   观察依据

   讲师指出，最后一名女生此时无法再与第二名男生配对。

1. 本片段并未就移除边后是否仍存在另一组匹配给出最终结论。

1. 相容的男生与女生示例
2. 移除一条已使用的边会使原始匹配失效

1. 图示
   观察依据

   品红色高亮的边展示了一组具体的匹配。

1. 相容的男生与女生示例
2. 匹配的数学形式化：沿边定义的双射

1. 公式
   观察依据

   幻灯片定义 $E(S)$ ::= 与 S 中至少一名女生相邻的男生集合。

2. 声音
   观察依据

   主讲人将 $E(S)$ 解释为集合 S 在边关系下的像。

1. 在边关系下某集合的邻域／像

1. 公式
   观察依据

   幻灯片指出：瓶颈是指一组女生 S，其邻接男生数量不足，并显示 |S| > |$E(S)$|。

2. 声音
   观察依据

   主讲人口头给出了该定义。

1. 瓶颈

1. 图示
   观察依据

   示例突出了三名女生和仅两名与之相邻的男生。

2. 声音
   观察依据

   主讲人指出男生人数不足以分配给所有女生，并由此得出不存在匹配的结论。

1. ‘相容的男孩与女孩’瓶颈示例
2. 瓶颈引理

1. 公式
   观察依据

   幻灯片标题为‘瓶颈引理’，其陈述为：若存在瓶颈，则匹配不可能存在——这显然成立。

2. 声音
   观察依据

   主讲人朗读了该引理。

1. 瓶颈引理

1. 公式
   观察依据

   幻灯片标题为霍尔定理，其陈述指出：反之，若不存在瓶颈，则存在一个匹配。

2. 声音
   观察依据

   主讲人将此称为霍尔定理，并指出它并不显然。

1. 霍尔定理（视频片段中所陈述的逆向方向）

1. 图示
   观察依据

   幻灯片上的文字明确指出：“反之，若图中不存在瓶颈，则存在匹配。”

1. 霍尔定理的逆命题