匹配及相关术语

一个无向图 $G$ 的匹配 $M$ 是其边的任意集合，其中任意两条边都不共享端点。换句话说，匹配中的每条边唯一地将两个顶点配对或匹配。我们将匹配 $M$ 中边的数量称为匹配的大小。

如果一个顶点是匹配中某条边的端点，则称该顶点被 $M$ 匹配；否则称其为未匹配。下图展示了图中一些匹配的例子。

在上述第 2–3 页幻灯片中，我们看到的是同一张图的不同大小的匹配。一个图 $G$ 的最大匹配是指包含边数最多的匹配。一个图中可能存在多个最大匹配。

需要注意的是，最大匹配并不一定要求每个顶点都被匹配。例如，下图中突出显示的最大匹配就使得顶点 $v_6$ 未被匹配，但其余所有顶点都被匹配了。

即使图中顶点总数为偶数，也可能存在最大匹配无法匹配所有顶点的情况。例如，下图所示的图有四个顶点，但其最大匹配仍使顶点 $v_1$ 和 $v_2$ 未被匹配。

如果一个匹配中每个顶点都与另一个顶点配对，则称为完美匹配。完美匹配一定是最大匹配，但最大匹配（如上图所示）不一定是完美匹配。

二分图中的最大匹配

在二分图中寻找最大匹配，是一种自然的方式来建模许多需要将资源分配给任务的问题。

回忆一下，二分图是一种无向图，其顶点被划分为两个集合 $L$ 和 $R$，且每条边恰好有一个端点在 $L$，另一个端点在 $R$。

例如，假设某救援服务在某个区域内设有待命的救护车。集合 $L$ 中的每个顶点代表一辆这样的救护车，而集合 $R$ 代表一系列紧急事件。如果某辆救护车能在规定时间内抵达某个紧急事件，则两者之间存在一条边。