匹配和运输网络

16

1. 关于匹配的定理

让我们考虑一下定理的表述。有一个由$n$个年轻人组成的公司，每个人都是朋友，都拥有一间或多间两居室的公寓。我们感兴趣的问题是：在什么条件下，$n$每个年轻人可以从他的女朋友中选择一个新娘（所以，当然，两个年轻人不会同时选择一个两居室的女孩）。

尝试找出是否可以在图 1 中给出的两个示例$a$和$b$）中安排这样的匹配。这里是$n=6$；科比棋子和年轻人被描绘成点，并且从每个科比棋子上绘制箭头指向那些与它是朋友的年轻人。安排相亲意味着选择（例如用铅笔圈出）六个箭头，从六个不同的两居室公寓到所有六个不同的年轻人。

事实证明，例如 $a$ 这是可以做到的 )。在例子$b$）中，无论我们如何努力，我们都不能让所有的年轻人结婚。不难解释原因。事实上，四个年轻人 - 伊利亚 (Ilya)、科利亚 (Kolya)、马克 (Mark) 和尼基塔 (Nikita) - 自从第三个科比作品 - Belaya、Ve 起就只是朋友了

*) 第 18 页 (图 2) 给出了该问题的解决方案之一。还有其他解决方案。

图 1

16

17

只能有两种情况：
情况 1. 对于某些 $k$ ($1 \leq k < n$)，有一群 $k$ 男孩，他们与恰好 $k$ 女孩是朋友（全部）。

让我们用$IO_k$表示这些年轻人的集合，用$Д_k$表示他们女朋友的集合。对于男孩组$IO_k$，诱导句子已完成。与此同时，他们的新娘耗尽了整套$Д_k$（不均匀的$k$女孩）。让我们把这些男孩和女孩排除在外，用反证法证明剩下的$n - k$男孩满足定理的条件。

让我们从这$n - k$个年轻人中选出一个包含$r$个年轻人的公司。假设他们的朋友$s$的数量少于$r$。让我们回到正轨，将这些$r$年轻人与$IO_k$团体团结起来。新团体中有$r + k$个年轻人。由于集合$D_k$包含$IO_k$男孩的所有女朋友（可能还包括所显示公司的$r$男孩的其他一些女朋友），那么这些$k + r$男孩一开始就有$k + s$女朋友。根据初始条件$k + r \leq k + s$。因此，$r \leq s$。结果与提案$s < r$矛盾。这意味着在这种情况下定理是正确的。

情况2.任意一组$k$个男孩（$1 \leq k < n$）至少与$k + 1$个女孩是朋友。

在这种情况下，一切都很简单。我们让任何年轻人嫁给他的任何女朋友。让我们将这一对排除在考虑范围之外。让我们证明剩下的$n - 1$男孩满足定理的条件。让我们以任意一组 $k$ 年轻人 ($k \leq n - 1$) 为例。一开始他们至少有$k + 1$个女朋友。然后选中的年轻人的新娘到了，那么还剩下$k$个女孩。这完全证明了定理。

相信，你必须花费一些条件才能理解这个证明。但是，除了证明并不简单之外，它还有一个重要的缺点——它没有给出一种简单的方法来找出每个特定情况下是否满足匹配定理的条件，如果满足，那么如何选择新娘，你需要遍历所有非公平的年轻男性子集（并且有$2^6 - 1 = 63$）组，并为每个年轻男性子集检查他们是否有足够的女朋友。但即使我们这样做并确保原则上可以安排所有婚礼，我们也不会从这里收到任何关于谁与谁结婚的指示。确实，在这个例子中$a$，你无疑轻松地选择了所需的六对（甚至有几个可能的选项），但是当集合非常大时，随机选择只需要花费很多时间。为了将此类问题的解决委托给计算机，有一个明确且经济的选择规则尤其重要。

我们将构建一些算法*)，它不仅会重新证明婚介定理，而且还会提供一种快速的方法来安排必要的婚介，如果这是不可能的，则指示最大婚礼次数的选项。

3. 婚礼和法庭

通过箭头以某种方式连接的点系统称为有向图*）。在这种情况下，点称为图的顶点，线段称为图的线或边。有向图的示例已在讨论中 图 1 以及图 3 和 5 中显示。在图 1 的情况下，图的所有顶点的集合被分为两组 - 女孩和男孩 - 以便边从一组的点到另一组的点。在这样的情况下

*) 解决特定类型问题的操作序列。莫斯科人被许诺了一种算法，列宁格勒——一种算法。当前页面的第二页。

18

该图被称为简单图或二部图，到目前为止，我们所面临的问题——安全地安排最多数量的女孩和男孩的个人生活——是最大匹配问题。

匹配问题可以使用如下图来表示。选择每对男女就意味着选择图表的一条边。我们将数字 1 分配给图膜边缘中的每一对，将数字 0 分配给其他每一对。安排好所有婚礼后，我们得到一个函数，其定义域是图的所有边，值的集合是两个数字 0 和 1*)。我们如何用这个函数来陈述问题的所有其他条件？我们需要每个男孩都选择一个女孩，并且每个女孩都只能被一个男孩选择。换句话说，对于图中的每个顶点，描绘了一个女孩，离开它的所有边的函数值之和必须不大于1，而对于描绘一个男孩的每个顶点，进入它的所有边的函数值之和必须恰好等于1。

因此，我们的问题被表述为找到在图的边缘上定义的某个函数并满足一些不等式的问题**）。

该问题的一种解决方案（在示例 a) 的情况下）如 图 2 所示，其中选定的边是头。所需的函数具有以下形式：

安雅 - 科利亚、贝拉 - 伊利亚、维拉 ​​- 列瓦、达莎 - 奥西亚、扎娜 - 马克、齐娜 - 尼基塔、安雅 - 尼基塔、维拉 - 伊利亚、加利亚 - 科利亚、达莎 - 列瓦、达莎 - 马克、达莎 - 尼基塔、伊娃 - 列瓦、扎娜 - 列瓦

*) 参见 A. N. Kolmogorov 的文章“什么是函数”，第 1 期«Kvant»。
**) 请注意，等式 f=1 可以写成两个不等式的系统：f≥1 和 f≤1。

19

Naimporta 与婚姻主题的其余部分不同。通信系统本身使用图表来表示。例如，当监控一组复杂工作的实施时，各个中间阶段由图的顶点指定，箭头连接其中相互依赖的阶段（图3）。第 14 页上的图表（此状态的启动屏幕）显示了其各部分的连接方式；从它可以立即清楚地看出，例如，无论第 2 条是否清晰，都可以阅读第 3 条。当给出一个图时，经常会提出一些与寻找满足某些不等式的函数在数学上相关的问题。其中之一，我们考虑过平等问题。让我们提出另一个类似的问题（但不解决它）。

任务。围绕棋盘$8 \times 8$移动马，在给定的方格中开始和结束。

我们绘制一个具有 64 个顶点（棋盘的区域）的图 (图 4)，并将每个顶点的边（在本例中为直线段）与移动马可以到达的边连接起来。在我们开始解决问题之前，运动的方向对我们来说并不重要，我们可以绘制没有箭头的图的边（无向图）；或者，您可以在每条边上沿两个相反方向绘制一对箭头。

所需的函数应为每个中间顶点提供数字 2，为初始和最终顶点提供数字 1。

4. 网络和流媒体

现在我们将研究一些特殊类型的图 - 网络和此类图上的特殊类型的函数 - 流。让我们再看一下图表（参见第 14 页）。它有两个极端顶点——“输入”（1.匹配定理）和“输出”（问题）。具有输入和输出的有向图称为“传输族”或简称为“族”。 图 5, a 中显示了此类网络的示例。

给定网络上的帮助是图的边上的函数，它采用（在最简单的情况下）值0和1并满足以下条件：对于每个中间顶点（即不同于输入和输出），沿着进入该顶点的所有边的流值之和等于离开该顶点的所有边上的值之和。

名称“运输七”和“流量”可以计算如下。

让我们想象一个城市，它发展了一套街道（边缘）和交叉口（顶点）系统，并且每条街道上都有单向交通，并且只有一个进入城市的交通和一个离开城市的交通。

川流不息的汽车在城市中穿行，交通组织得很好，任何一个路口都没有堵车。在所考虑的最简单的情况下，我们假设人流流过的所有街道都受到相同的负载（具有相同的容量，通常将其视为一个）。

在更一般的情况下，每条边都被分配一个正整数 - 权重或容量。 （在我们的例子中

21

街道通行能力是指单位时间内可以通过街道“横截面”的汽车数量。）

通常不说“流是在网络上定义的”，而是说“流通过网络传递”。显然，流在中间顶点没有留下任何东西，因此给出口带来的碰撞次数与通过入口的碰撞次数相同。沿着离开输入的所有边缘的通量值之和等于沿着所有到达输出的边缘的值之和，称为通量值。

图 5,6 显示网络图 5,a 上的流量。该流的值等于1的网络边被描述为头。流量值为3。

很容易说，为了让大小为 n 的流通过网络，必须满足以下必要条件：如果任意 k 个边与网络断开，其中 k<n，则可以沿着剩余的边从输入传递到输出。

值得注意的是（正如在匹配定理中一样）这个必要条件被证明是充分的。

许多实际经济问题都需要找到最大流量，即可以通过给定网络的最高可能值的流量。

现在我们将讨论能够构建最大流的算法的描述。

5. 算法
   福特-法克森

让我们有一个传输网络（图 5,a）。我们的任务是为其构建最大流量。

让这个网络上有一些初始流（在极端情况下为零，即每条边上的值都等于零）。

我们将从非零通量 (图 5,6) 开始。该流所沿的边缘（它们由头部形成）将被称为饱和的，其余的（黄色）是自由的。检查我们的流量是否无法在不接触已占用的流量的情况下增加（您无法通过仅沿着自由箭头移动将输入连接到输出）。

我们现在将执行一些操作，这将导致两种可能的结果：要么显示如何增加此流量，要么发现现有流量最大。

让我们开始在顶部放置“加号”和“减号”框。让我们用平扣标记从入口沿自由边可以到达的所有顶点。进一步的放置过程将是任意的：从已经放置的顶点开始，我们将把那些可以沿着自由边到达的顶点放平，在一分钟内 - 所有那些可以从它沿着饱和弧返回的顶点（以与箭头相反的方向）。不要因为放置过程微不足道这一事实而感到困惑 - 通常同一个顶点可以同时放置加号和分钟。

让我们用这种方式标记所有可能的顶点（图 5,6 上没有未放置的顶点；但在其他情况下它们可能会出现！）。

可能有两种情况：1）我们设法放置输出（当然，带有加号）； 2）不可能建造更多的房屋，但出口仍未完成。

1. 结果发现m被放到了输出中。 （这发生在图 5,6。）让我们恢复我们设法放置输出的顺序*），也就是说，我们通过沿着预期顶点的路径将输出与输入连接起来（该路径在某些情况下可以是

*）实际（在具有大量顶点的图中）放置使零件变得更加复杂，以便存储有关顶点放置顺序的信息。

22

与箭头方向相反的方向）。

图 5.6 处的这条路径用红线突出显示。

现在我们将执行以下操作：在选定的红色路径中，我们将使自由箭头饱和，反之亦然（图 5,8），即我们将更改红线上的流，以便它在其每个边缘上采用值 1 和 0 以及 0 和 1*）。很容易看出，新函数又是一个流，即在中间顶点，传入和传出饱和箭头的数量再次相同 - 不违反平衡。与此同时，脸的流量增加了一个单位。

所以在第一种情况下我们可以增加流量。如果这个操作可以再次进行，我们将尽可能长时间地重复。

2. 输出未标记 (图 5,2)。我们的方法无法增加流量。但这还不能得出它是最大值的结论。有可能我们增加的方法不好，我们可以通过其他方式增加流量。让我们证明事实并非如此，即我们将证明现有流量是最大的。让我们考虑所有未放置顶点的​​集合。根据条件，该集合包括输出。让我们数一下通向该组的箭头的数量，即左端已放置但右端未放置的箭头。显然，任何流量的大小都不会大于这个数字。同时，对于我们的流程，所有这些箭头都是饱和的，因为否则右端可以放置平坦。另外，来自未放置顶点集合（即左端未放置而右端已放置的箭头）的所有箭头都是自由的，否则左端可能会在一分钟内放置。这意味着原始流的大小等于离开的箭头数量

6. 盖尔定理
   关于饱和度

使用 Ford-Falkerson 算法，我们现在将制定并证明传输网络理论的中心定理。该公式会使用一些自然的经济学术语，但你会感觉到它与匹配定理有多么接近。

让我们拥有一个运输网络。考虑任意一组任意顶点$A$（即既不包含输入也不包含输出）。让我们将这个集合 $A$ 的容量定义为指向 $A$ 的箭头数量。我们来表示这个数字

23

通过$c(A)$。让我们通过集合$A$的总要求来定义从$A$直接通向出口的边的数量。我们用 $d(A)$ 来表示这个数字。

让我们研究下面的问题：在什么条件下存在一种使所有输出边饱和的流，即通向输出的所有边上的值都等于1的流。显然，这样的流量应该是最大的。

盖尔定理。对于任何数量，都存在一个使所有输出弧饱和的流量；对于任何集合$A$，其总需求不超过容量是必要且充分的：

$$d(A) \leq c(A).$$

证明。与牵线搭桥定理一样，必然性几乎是轮回。事实上，如果我们可以构造一个沿着所有通向出口的边经过的流，那么对于任何集合$A$，它也只沿着从$A$通向出口的边经过。同时，通向集合$A$的流的数量不能大于通向$A$的边的数量，即数量$c(A)$。但这一流量必须沿着通向出口的所有边缘完全离开 $A$，也许还沿着其他一些边缘。由此可知$d(A) \leq c(A)$。

充分性。让我们的网络流量最大化。让我们证明它沿着所有输出弧。让我们使用 Ford-Folkerson 方法来标记顶点并考虑未标记的顶点集。让我们从该集合中删除输出。我们用 $A^*$ 表示结果集。通向出口的肋可以有两种类型。

首先，这些也是末端位于 $A$ 的边，即是标记的顶点。它们将是饱和的，因为根据构建流的方法，所有左端被放置但右端未被放置的边都是饱和的。

其次，这些是导致退出集合的边缘。由于$A$与出口一起构成所有未标记顶点的集合，因此所有通向$A$的$c(A)$边都将饱和，而所有从$A$通向出口的不直接的边将是空闲的。

*）集合$A$可能会被证明是空的——我们的推理仍然是正确的。但在这种情况下，盖尔定理的有效性立即可见。为什么？

这意味着进入$A$的整个价值流$c(A)$必须直接从$A$退出到出口。但从$A$开始只有$d(A)$通向出口，并且我们知道$d(A) \leq c(A)$。因此，所有这些边都是饱和的且$d(A) = c(A)$。

您可能注意到盖尔定理的条件与婚礼定理的条件相对应。尝试根据盖尔定理自己推导出该定理。为此，您需要根据男孩和女孩之间的熟人二部图创建一个跨空间网络，将输入与所有女孩连接起来，将输出与所有男孩连接起来（然后可以方便地为连接女孩与男孩的每个箭头分配权重$N$，其中$N$大于男孩的数量）。

现在对我们来说更重要的不是我们获得了匹配定理的另一个证明，而是我们有一个简单的构造最大流的算法。

对于配对问题，算法很自然地制定了如下流程：对于每个不是新娘的女孩，将她所有的朋友放在平地上，然后在一分钟内将这些朋友的新娘放在平地上，然后将这些新娘的其余朋友放在平地上，等等；如果发现有一个空的年轻人，那么可以通过沿着从空的女孩到空的年轻人的标记所绘制的链条（如图5.6处的红线）进行替换来增加婚礼的数量。

为所有年轻人安排婚礼无非是构建一个充满所有出口弧线的流程；如果情况并非如此，那么 Ford-Folkerson 算法为解决有限数学中的许多难题提供了最大可能的新有趣算法。