二分图最大匹配的必须边和可行边

以下考虑完备匹配（非完备匹配要用到网络流）

给定一张二分图，其最大匹配方案不一定是唯一的。若任何一个最大匹配方案的匹配边都包括\((x,y)\)，则称\((x,y)\)为二分图匹配的必须边。若\((x,y)\)至少属于一个最大匹配的方案，则称\((x,y)\)为二分图匹配的可行边

以下证明假设我们已经求出了一个最大匹配

在完备匹配时，一条边\((x,y)\)是必须边，必须同时满足以下两个条件：

1.在当前这个完备匹配的状态下，\((x,y)\)是匹配边

2.在当前这个完备匹配的状态下，去掉\((x,y)\)这条边之后，不能再找一条增广路，其起点是\(x\)，终点是\(y\)

第一个条件是显然的，如果不是匹配边怎么可能是必须边，主要是证明一下第二个条件

如果去掉\((x,y)\)后，还能再找到这么一条增广路，那么我们把这条增广路取反，显然匹配数加一，此时等于最大匹配，而且这个最大匹配不再包含\((x,y)\)这一条边，所以\((x,y)\)不是必须边。如果去掉\((x,y)\)后，不能找到这么一条增广路，我们不妨重新排序把\(x\)和\(y\)这两个点放在最后，并且认为前面在跑匈牙利算法的时候跑出来的匹配情况与最开始的完备匹配去掉\((x,y)\)后剩下的边的匹配情况相同（匈牙利算法是不看顺序的，而且只执行一遍，故这个换序不会影响结果），现在我们再考虑\(x\)和\(y\)这两个点（此时，现在的这个图与最开始的完备匹配的那个图的差距仅仅是少了\((x,y)\)这一条边），如果找不到\(x\)到\(y\)的增广路，那么\(x\)肯定匹配失败，故不再是最大匹配，所以\((x,y)\)是必须边

其实必须边我自己还发现了一种算法

在完备匹配时，一条边\((x,y)\)是可行边，则满足以下两个条件之一：

1.在当前这个完备匹配的状态下，\((x,y)\)是匹配边

2.在当前这个完备匹配的状态下，\((x,y)\)是非匹配边。设当前\(x\)与\(u\)匹配，\(y\)与\(v\)匹配，那么连接\((x,y)\)后，\(u\)和\(v\)失去匹配，必须找到一条从\(u\)到\(v\)的增广路，来保证最大匹配不变

第一个条件显然。第二个条件可以像证必须边的第二个条件一样证明，这个时候把\(u\)和\(v\)放到最后就可以了

如果我们把二分图中的非匹配边看作从左部到右部的有向边，把二分图中的匹配边看作从右部到左部的有向边，构成一张新的有向图，那么原图中从\(x\)到\(y\)有增广路等价于新图中存在从\(x\)到\(y\)的路径。这一个用充分必要性证明就可以了，比较简单

因此，必须边的判定条件是：\((x,y)\)是原图的匹配边，并且\(x\)和\(y\)两点在新图中属于不同的SCC

可行边的判定条件是：\((x,y)\)是原图的匹配边，或者\(x\)和\(y\)两点在新图中属于相同的SCC