匹配

匹配选择若干条互不争用端点的边，每个顶点最多参与一次配对。直接添加一条边只会检测当前还有没有两个同时空闲的端点，这对应极大性；增广路允许先解除部分旧配对、再沿交替链重新安排，因而能发现被局部选择遮住的全局改进。

对称差翻转为何保持可行，可以逐点查看。增广路内部每个顶点失去一条旧匹配边，同时获得一条新匹配边；两个端点原本未饱和，各自只获得一条边。冲突没有增加，匹配规模却净增一。

在四点路径 $v_1{v}_2{v}_3{v}_4$ 中，单边集合 $\{v_2{v}_3\}$ 已经极大：剩余两条边都碰到它的端点。但它不是最大，路径

相对于该匹配交替且两端未饱和。翻转后得到 $\{v_1{v}_2,v_3{v}_4\}$，这是大小为二的完美匹配。

任取一个极大匹配 $M$，其规模至少为最大匹配的一半。设 $M^{\star }$ 最大；极大性保证 $M^{\star }$ 中每条边至少碰到一条 $M$ 边，否则还可直接加入。每条 $M$ 边只有两个端点，至多被两条 $M^{\star }$ 边这样归属，所以

四点路径的中间边达到这个界，说明“随便取极大匹配”只保证二分之一近似，不能冒充精确算法。

空集总是匹配。孤立点不妨碍普通匹配，却会阻止完美匹配。最大匹配可能有多个，$\nu (G)$ 只记录共同的最优大小；若边带收益，最大权匹配优化权重和，可能故意选择较少的边。

普通匹配要求每个顶点容量为一。任务可由多台相同机器承接时需要 $b$-matching；医院—住院医问题还包含容量与偏好顺序；指派问题通常要求二分、带权并饱和两侧。它们都从配对出发，却不是删几个形容词便可互换的同一问题。

增广路公理库增广路Augmenting path相对于当前匹配，边在未匹配与已匹配之间交替且两个端点均未匹配的路径。把最大性转化为可搜索的证书。二分图的交替搜索没有奇圈干扰，Hopcroft–Karp 算法公理库Hopcroft–Karp 算法Hopcroft-Karp algorithm按阶段同时增广一族顶点不交的最短增广路，以 O(E√V) 时间求二分图最大匹配。可按最短增广路分层并批量推进；一般图中的奇交替圈需要Edmonds blossom 算法公理库Edmonds blossom 算法Edmonds' blossom algorithm · Blossom algorithm通过识别并收缩奇交替环，在一般图中保持增广路存在性并求最大匹配的算法。收缩后再展开。

在二分图公理库二分图Bipartite graph顶点可分成两个独立侧、且每条边都跨越两侧的有限简单无向图。中，Hall 定理公理库Hall 婚配定理Hall's marriage theorem有限二分图存在饱和一侧的匹配，当且仅当每个该侧顶点子集的邻集至少同样大。刻画饱和指定一侧的匹配何时存在，Kőnig 定理公理库Kőnig 二分图定理Kőnig's theorem for bipartite graphs二分图中最大匹配大小等于最小顶点覆盖大小。给出

其中 $\tau (G)$ 是最小顶点覆盖公理库顶点覆盖Vertex cover与图中每条边至少一个端点相交、从而覆盖全部边的顶点子集。大小。一般图始终只有 $\nu (G)\le \tau (G)$；三角形以 $1<2$ 说明二分假设不可省略。

二分匹配的网络流归约公理库经由网络流的二分图匹配Bipartite matching via maximum flow把二分图匹配编码为单位容量流网络并由最大流恢复匹配。把每条可选配对设为单位容量弧，适合无权最大基数目标。匈牙利算法公理库匈牙利算法Hungarian algorithm通过对偶标号和增广结构求解赋权二分图完美匹配的算法。处理带成本的二分指派，并利用对偶势寻找最优完美匹配；它不能直接替代一般非二分图匹配。

匹配还为顶点覆盖给出下界，并为边覆盖、路径覆盖与拟阵交提供交换结构。把应用归约到匹配之前，应先确认端点容量、图是否二分、是否要求完美以及目标是基数还是权重。