从开学以来一直忙到生理上呕吐，各个项目全都搁置了，现在觉得必须赶紧捡起来，至少把之前想过的有用的小定理记录下来。
这篇blog谈论为什么有完美匹配的二部图对于在线匹配算法是最难的。（特指对于绝大多数贪心算法）换句话说，在我们分析C.R.时，只需要关心这一类图。
，为左部离线点，为右部在线点，为边。
表示与相邻的点。
首先，把所有无边的右部点删掉，显然对算法的运行没有影响，对最大匹配数也没有影响。
现在，设的最大匹配数为，其中字典序最大的最大匹配实例为（如果仍有多个就任意选择一个）。设“最下面”的一条边为（在右部意义上），则可以把开始的右部点全部删掉。因为这对最大匹配数没有任何影响，而对于算法的运行只有糟糕的影响（没有后面的点帮忙找补了），因此这样的图是更困难的。新生成的图我们叫做。
考虑中不属于的“最上面”的，记为。我们把连出的边全部删除，新的图记作。我们现在证明比更困难。
首先，由于，因此最大匹配数不变。
考虑算法运行情况：
若算法在上运行时，没有匹配，则算法在两张图上的运行情况是一样的。
若算法在上运行时，匹配了，匹配对象记为。注意到，算法在到期间的运行情况在两张图上是一致的。在这个时刻，算法在上多得到一个匹配。在以后的时刻，相当于缺少了一个左部点，这会造成一个alternating path，所以会让算法在上至多少匹配匹配一条边。又由于已经在时确定性地多匹配了一条边。所以总体上，算法在两张图上要么表现相同，要么在上多匹配一条边。
综上，最大匹配数不变，算法匹配情况不会变好，因此比困难。
同样用alternating path证明，我们可以把不属于的全部左部点都删掉，新图也只会更困难。
按照上面的过程不断反复，我们就得到了这样一张图，它和拥有同样的最大匹配数，，且比更困难。该最大匹配对于也同时是完美匹配。
这样我们就表明了有完美匹配的二部图对于在线匹配算法是最难的。
对于可复用资源的问题，“把所有无边的右部点删掉”这一步骤不能做（因为时间是一个要素），无边点是要保留的，相当于空了一拍，其他一致。