匹配

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

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

在四点路径 $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)$ 只记录共同的最优大小。若边带收益，最大权与最大基数不再相同：给四点路径的中间边权重 $10$、两条外边各权重 $4$，最大权匹配只选中间边，权重为 $10$；最大基数匹配选两条外边，权重只有 $8$。因此“先最大化边数，再最大化权重”也是另一个目标，必须另行说明。

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

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

另一条代数路线是Tutte矩阵理路Tutte矩阵Tutte matrix · 图匹配的Tutte矩阵以反对称边变量矩阵编码一般图完美匹配，证明随机行列式判定，并用隔离权与二进阶主子式提取可验真匹配。：为每条无向边放入一个反对称变量，形式行列式非零当且仅当存在完美匹配；随机代入后的非零值给存在性证据。配合隔离引理理路隔离引理Isolation lemma · Isolating lemma · MVV isolation lemma给固定集合族的元素独立赋小整数权，以元素阈值和并集界保证唯一最小解，并区分隔离存在性与求解能力。及整数二幂代入，可由删两端点的主子式筛出实际边集，再逐端点验真；随机失败不等于确定不存在，也没有替代本页的一般最大匹配目标。

在二分图理路二分图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用单位容量流求二分图匹配，并从终态搜索同时提取 Hall 障碍、等值割和最小顶点覆盖。把每条可选配对设为单位容量弧，适合无权最大基数目标。匈牙利算法理路匈牙利算法Hungarian algorithm通过对偶标号和增广结构求解赋权二分图完美匹配的算法。处理带成本的二分指派，并利用对偶势寻找最优完美匹配；它不能直接替代一般非二分图匹配。

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