二分图匹配多胞形

第一条证明把图的二分结构变成全幺模性公理库全幺模矩阵与整数顶点Totally unimodular matrix · Total unimodularity · TU用所有方形子式的 0、±1 性质控制逆矩阵分母，证明整数右端的线性约束产生整数顶点。。右侧系统的点边关联矩阵每列有两个一。把 $U$ 侧对应的行乘 $-1$，每列就有一个负一、一个正一，成为有向关联矩阵。加入非负性的单位行仍是 TU，整数右端因而给出整数极点。每个整数可行向量只能取 $0$ 或 $1$，度上界又保证这些一互不共享端点，恰是匹配。

还有一个更能看见分数如何移动的证明。只保留 $0<x_e<1$ 的分数边，形成一个子图。若含环，二分性使环为偶环；沿环交替加减一个小的 $\epsilon$，每个图结点接收到的一加一减抵消。反向扰动也合法，原点就是两个不同可行点的中点，因而不是极点。

若分数子图没有环，就在某棵非空树中取一条叶到叶路径，沿路径交替加减。内部结点仍抵消，端点只接触一条分数边；那里不可能另有值为一的边，所以度约束有正松弛。取足够小的 $\epsilon$，正反扰动都不违反非负性或端点上界。无论遇到环还是树，只要有分数边，就存在这种可行移动方向。

四环上的一半不是新顶点 ​

四环的边按循环次序记为 $e_0,e_1,e_2,e_3$。向量

使每个图结点的度和都是一。但它有分解

括号内两向量分别是两个完美匹配。它们甚至给出整条可行线段 $(t,1-t,t,1-t)$，$0\le t\le 1$；只有线段两端是这条方向上的极点，中点不是。分数可行性与分数极点不能混为一谈。

三角形为何没有同样自由度 ​

在三角形上，每边一半也使三个度约束取等号。但假设扰动量分别为 $d_0,d_1,d_2$，保持三条等式要求

沿圈交替一轮后符号碰撞，只能得到 $d_0=d_1=d_2=0$。相应三阶关联矩阵行列式为二，三条等式唯一确定一半向量，所以它确实是度约束松弛的分数极点。

从四环加一条对角线也会出现同样问题：让新三角形的三条边各取一半，其余边取零，便得到一个不能由匹配凸组合表示的分数极点。二分性不是为了方便给图涂两种颜色，而是排除了这类奇圈锁死的局部结构。

任意边权和对偶价格 ​

给边权 $c_e$，允许匹配为空，最大权匹配可以写成上述多胞形上的 LP。其对偶公理库线性规划对偶Linear programming duality · LP duality从线性约束生成对偶界，并以弱对偶、强对偶和互补松弛连接两侧最优解。为

对四边权矩阵 $\left(\begin{array}{cc}5& 4\\ 4& 1\end{array}\right)$，交叉匹配总权重八；顶点价格 $(4,3)$ 与 $(1,0)$ 总和也是八，并逐边覆盖边权，给出完整最优证书。所有边权均为一时，这个对偶再联系到二分图的顶点覆盖，但一般整数边权下，价格可能大于一，不能直接把它当成一个普通零一覆盖集合。

二分图匹配的流归约公理库经由网络流的二分图匹配Bipartite matching via maximum flow用单位容量流求二分图匹配，并从终态搜索同时提取 Hall 障碍、等值割和最小顶点覆盖。给出构造某个最大匹配的算法；本页的凸包等式解释为什么任意线性边权目标都没有松弛损失，并刻画了全部分数可行向量，而不只是一条增广路的效果。Kőnig 定理公理库Kőnig 二分图定理Kőnig's theorem for bipartite graphs二分图中最大匹配大小等于最小顶点覆盖大小。是基数目标下的一种组合最小—最大结论，不能代替完整凸包证明。

本定理也是一般匹配多胞形定理公理库一般匹配多胞形的奇集约束Edmonds matching polytope · Odd-set inequalities · Blossom inequalities用全部奇数顶点集的内部边上界补齐一般图匹配凸包，并通过紧奇割的收缩与配对展开解释整数性机制。的二分图特例。对任意奇数顶点集 $S$，其左右两侧中较小一侧至多有 $(|S|-1)/2$ 个点；每条内部边恰接触这一侧一次，将这些点的度上界相加便得到奇集不等式。因此在二分图上，那些额外的奇集约束已由度约束蕴含。

对完美匹配，左右两侧大小不等会使等式系统不可行；大小相等也还需足够的连边。若存在某些禁止配对，直接删掉相应边或固定变量为零，仍保留上述结构。若额外加入资源预算、两条不相邻边不能同时出现等约束，新多胞形可能出现分数顶点；“原来是二分匹配”不保证任意扩充模型仍整数。

在完全二分图上，完美匹配向量排列成矩阵就是置换矩阵。Birkhoff–von Neumann 分解公理库双随机矩阵的 Birkhoff–von Neumann 分解Birkhoff–von Neumann theorem · Doubly stochastic matrix decomposition在正支撑图中反复寻找完美匹配并扣除最小边权，把任意双随机矩阵精确拆成置换矩阵的凸组合。会把任意双随机矩阵实际拆成若干这样的匹配，给出比存在性更具体的排班实现。