4.5 Matching in Bipartite Graphs 二部图中的匹配

本页译自 LibreTexts · Discrete Mathematics (Levin) 第 4.5 章。公式经 MathJax 渲染，自定义宏已注入。

Investigate! 探究！

Given a bipartite graph, a matching is a subset of the edges for which every vertex belongs to exactly one of the edges. Our goal in this activity is to discover some criterion for when a bipartite graph has a matching.

给定一张二部图，所谓匹配（matching）是边的一个子集，使得每个顶点恰好属于其中一条边。本次活动的目标是找出判断二部图何时存在匹配的一些准则。

Does the graph below contain a matching? If so, find one.

下面的图是否包含匹配？若包含，请找出一个。

$image-145.svg$

Not all bipartite graphs have matchings. Draw as many fundamentally different examples of bipartite graphs which do NOT have matchings. Your goal is to find all the possible obstructions to a graph having a perfect matching. Write down the necessary conditions for a graph to have a matching (that is, fill in the blank: If a graph has a matching, then ). Then ask yourself whether these conditions are sufficient (is it true that if , then the graph has a matching?).

并非所有二部图都有匹配。请尽量多地画出「本质上不同」的不存在匹配的二部图例子。你的目标是找出阻碍一个图拥有完美匹配的所有可能障碍。写出图存在匹配的必要条件（即填空：若图有匹配，则______）。然后再问自己：这些条件是否充分（是否「若______，则图有匹配」成立）？

We conclude with one more example of a graph theory problem to illustrate the variety and vastness of the subject.

最后我们再给出一个图论问题的例子，以说明这一学科的丰富多样与博大精深。

Suppose you have a bipartite graph $G\text{.}$ This will consist of two sets of vertices $A$ and $B$ with some edges connecting some vertices of $A$ to some vertices in $B$ (but of course, no edges between two vertices both in $A$ or both in $B$). A matching of $A$ is a subset of the edges for which each vertex of $A$ belongs to exactly one edge of the subset, and no vertex in $B$ belongs to more than one edge in the subset. In practice we will assume that $\|A\| = \|B\|$ (the two sets have the same number of vertices) so this says that every vertex in the graph belongs to exactly one edge in the matching.⁵Note: what we are calling a matching is sometimes called a perfect matching or complete matching. This is because in it interesting to look at non-perfect matchings as well. We will call those partial matchings.

设想你有一张二部图 $G\text{。}$ 它由两组顶点 $A$ 和 $B$ 构成，其中一些边把 $A$ 的某些顶点连到 $B$ 的某些顶点（当然，$A$ 内部或 $B$ 内部的两顶点之间不会有边）。$A$ 的匹配是边的一个子集，使得 $A$ 的每个顶点恰好属于子集中的一条边，且 $B$ 中没有顶点属于子集中的多于一条边。实际中我们通常假定 $\|A\| = \|B\|$（两组顶点数量相同），于是这意味着图中每个顶点都恰好属于匹配中的一条边。⁵注：我们所称的「匹配」有时也叫完美匹配或完全匹配。这是因为研究非完美匹配同样有意义，我们称那些为部分匹配。

Some context might make this easier to understand. Think of the vertices in $A$ as representing students in a class, and the vertices in $B$ as representing presentation topics. We put an edge from a vertex $a \in A$ to a vertex $b \in B$ if student $a$ would like to present on topic $b\text{.}$ Of course, some students would want to present on more than one topic, so their vertex would have degree greater than 1. As the teacher, you want to assign each student their own unique topic. Thus you want to find a matching of $A\text{:}$ you pick some subset of the edges so that each student gets matched up with exactly one topic, and no topic gets matched to two students.⁶The standard example for matchings used to be the marriage problem in which $A$ consisted of the men in the town, $B$ the women, and an edge represented a marriage that was agreeable to both parties. A matching then represented a way for the town elders to marry off everyone in the town, no polygamy allowed. We have chosen a more progressive context for the sake of political correctness.

借助一个背景或许更易理解。把 $A$ 中的顶点看作班上学生，$B$ 中的顶点看作展示题目。若学生 $a$ 想在题目 $b$ 上做展示，就从顶点 $a \in A$ 向顶点 $b \in B$ 连一条边。当然，有些学生想做的题目不止一个，因此他们对应顶点的度会大于 1。作为老师，你希望给每个学生分配一个专属题目。于是你要找 $A$ 的一个匹配：选出边的某个子集，使每个学生恰好匹配到一个题目，且没有题目被匹配给两名学生。⁶匹配的标准例子曾是婚配问题：$A$ 由镇上男子组成，$B$ 由女子组成，一条边表示一桩双方都同意的婚姻。匹配则代表镇上长老让全镇人人成婚（不允许一夫多妻）的一种安排。出于政治正确的考虑，我们选用了更进步的背景。

The question is: when does a bipartite graph contain a matching of $A\text{?}$ To begin to answer this question, consider what could prevent the graph from containing a matching. This will not necessarily tell us a condition when the graph does have a matching, but at least it is a start.

问题是：二部图何时包含 $A$ 的匹配？要着手回答，先考虑是什么阻碍了图拥有匹配。这未必能直接告诉我们图「确有」匹配的条件，但至少是一个起点。

One way $G$ could not have a matching is if there is a vertex in $A$ not adjacent to any vertex in $B$ (so having degree 0). What else? What if two students both like the same one topic, and no others? Then after assigning that one topic to the first student, there is nothing left for the second student to like, so it is very much as if the second student has degree 0. Or what if three students like only two topics between them. Again, after assigning one student a topic, we reduce this down to the previous case of two students liking only one topic. We can continue this way with more and more students.

$G$ 没有匹配的一种情形是：$A$ 中存在一个顶点不与 $B$ 的任何顶点相邻（即度为 0）。还有别的情形吗？倘若两名学生都只喜欢同一个题目、别无他选呢？那么把该题分配给第一名学生后，第二名学生便无题可选，这几乎等同于第二名学生度为 0。或者，三名学生合起来只喜欢两个题目呢？同样，给其中一名学生分配题目后，问题就退化到前面「两名学生只喜欢一个题目」的情形。依此类推，学生越多越是如此。

It should be clear at this point that if there is every a group of $n$ students who as a group like $n-1$ or fewer topics, then no matching is possible. This is true for any value of $n\text{,}$ and any group of $n$ students.

至此应当清楚：如果存在一组 $n$ 名学生，他们合起来只喜欢 $n-1$ 个或更少的题目，那么就不可能有匹配。对任意 $n$ 的取值、任意一组 $n$ 名学生，这都成立。

To make this more graph-theoretic, say you have a set $S \subseteq A$ of vertices. Define $N(S)$ to be the set of all the neighbors of vertices in $S\text{.}$ That is, $N(S)$ contains all the vertices (in $B$) which are adjacent to at least one of the vertices in $S\text{.}$ (In the student/topic graph, $N(S)$ is the set of topics liked by the students of $S\text{.}$) Our discussion above can be summarized as follows:

为了使论述更具图论色彩，设你有顶点集合 $S \subseteq A$。定义 $N(S)$ 为 $S$ 中顶点的所有邻点组成的集合。也就是说，$N(S)$ 包含 $B$ 中所有与 $S$ 中至少一个顶点相邻的顶点。（在学生/题目图中，$N(S)$ 就是 $S$ 中的学生所喜欢的题目的集合。）上面的讨论可归纳如下：

Matching Condition

匹配条件

If a bipartite graph $G = \{A, B\}$ has a matching of $A\text{,}$ then

若二部图 $G = \{A, B\}$ 有 $A$ 的匹配，则

$$ \|N(S)\| \ge \|S\| $$

for all $S \subseteq A\text{.}$

对一切 $S \subseteq A$ 都成立。

Is the converse true? Suppose $G$ satisfies the matching condition $\|N(S)\| \ge \|S\|$ for all $S \subseteq A$ (every set of vertices has at least as many neighbors than vertices in the set). Does that mean that there is a matching? Surprisingly, yes. The obvious necessary condition is also sufficient.⁷This happens often in graph theory. If you can avoid the obvious counterexamples, you often get what you want. This is a theorem first proved by Philip Hall in 1935.⁸There is also an infinite version of the theorem which was proved by Marshal Hall, Jr. The name is a coincidence though as the two Halls are not related.

逆命题成立吗？假设 $G$ 对所有 $S \subseteq A$ 都满足匹配条件 $\|N(S)\| \ge \|S\|$（即每个顶点集的邻点数不少于该集合的顶点数）。这是否意味着存在匹配？出人意料地，答案是肯定的。这个明显的必要条件同时也是充分的。⁷这在图论中屡见不鲜：若能避开那些显而易见的反例，往往就能得到想要的结论。这是菲利普·霍尔（Philip Hall）于 1935 年首次证明的定理。⁸该定理还有一个无限版本，由小马歇尔·霍尔（Marshal Hall, Jr.）证明。两人同姓只是巧合，彼此并无亲缘关系。

Theorem 4.5.1 Hall's Marriage Theorem

定理 4.5.1 霍尔婚配定理

Let $G$ be a bipartite graph with sets $A$ and $B\text{.}$ Then $G$ has a matching of $A$ if and only if

设 $G$ 为具有顶点集 $A$ 与 $B$ 的二部图。则 $G$ 存在 $A$ 的匹配，当且仅当

$$ \|N(S)\| \ge \|S\| $$

for all $S \subseteq A\text{.}$

对一切 $S \subseteq A$ 都成立。

There are quite a few different proofs of this theorem – a quick internet search will get you started.

这个定理有相当多种不同的证明——上网稍加搜索便能找到入门资料。

In addition to its application to marriage and student presentation topics, matchings have applications all over the place. We conclude with one such example.

除了婚配与学生选题，匹配在方方面面都有应用。我们以一个例子收尾。

Example 1

示例 1

Suppose you deal 52 regular playing cards into 13 piles of 4 cards each. Prove that you can always select one card from each pile to get one of each of the 13 card values Ace, 2, 3, …, 10, Jack, Queen, and King.

假设你把 52 张普通扑克牌发成 13 堆、每堆 4 张。证明：你总能从每堆各选一张牌，使得选出的 13 张牌恰好涵盖 13 种牌面：A、2、3、…、10、J、Q、K。

Solution

解答

Doing this directly would be difficult, but we can use the matching condition to help. Construct a graph $G$ with 13 vertices in the set $A\text{,}$ each representing one of the 13 card values, and 13 vertices in the set $B\text{,}$ each representing one of the 13 piles. Draw an edge between a vertex $a \in A$ to a vertex $b \in B$ if a card with value $a$ is in the pile $b\text{.}$ Notice that we are just looking for a matching of $A\text{;}$ each value needs to be found in the piles exactly once.

直接去做颇有难度，但我们可以借助匹配条件。构造图 $G$，令集合 $A$ 含 13 个顶点，各代表一种牌面；集合 $B$ 含 13 个顶点，各代表一堆牌。若牌面为 $a$ 的牌出现在堆 $b$ 中，就在顶点 $a \in A$ 与顶点 $b \in B$ 之间连一条边。注意，我们其实就是在寻找 $A$ 的一个匹配：每种牌面都需在堆中恰好出现一次。

We will have a matching if the matching condition holds. Given any set of card values (a set $S \subseteq A$) we must show that $\|N(S)\| \ge \|S\|\text{.}$ That is, the number of piles that contain those values is at least the number of different values. But what if it wasn't? Say $\|S\| = k\text{.}$ If $\|N(S)\| < k\text{,}$ then we would have fewer than $4k$ different cards in those piles (since each pile contains 4 cards). But there are $4k$ cards with the $k$ different values, so at least one of these cards must be in another pile, a contradiction. Thus the matching condition holds, so there is a matching, as required.

若匹配条件成立，我们就有匹配。给定任意一组牌面（即集合 $S \subseteq A$），须证 $\|N(S)\| \ge \|S\|$。也就是说，包含这些牌面的堆数不少于不同牌面的种数。但若不然呢？设 $\|S\| = k$。若 $\|N(S)\| < k$，则这些堆中不同牌的张数少于 $4k$（因每堆含 4 张牌）。然而具这 $k$ 种牌面的牌共有 $4k$ 张，故其中至少一张必在另一堆中，矛盾。于是匹配条件成立，从而存在匹配，证毕。