关于此题的现有题解

如题，个人感觉此题现有题解基本都有些小毛病，就是都没讲明白某些至关重要的点（文章 h1fqk2ny 除外）——

为什么答案总是 Yes？
既然每次都是随便找一组完全匹配，并将该组匹配删掉从而将题目从 $M$ 转化为 $M-1$ 的情况，那为什么随便删就一定是对的？

一般来说，证明上面这两点是要用到 Hall 定理 的。但是本人一看题解区，发现部分题解就是“自然而然”地得出了上面两条结论（或其中的第二条），全然忽略了证明过程。这可能会误导一些参考了题解而做出这道题的人，并使他们没能学到本题中我认为非常核心且关键的知识要点。

另外，97isd4ls 这篇题解通过论述「推广 Hall 定理」，成功对一年多以前刚学 Hall 定理的我起到了一定的误导作用。其实我并没有刻意针对谁的意思，我只是觉得，题解既然主要是给不会这道题的人看的，那么其内容的准确性就应该要尽量保证，这样题解才能算比较合格。

如有管理员看到了这篇帖子，可否考虑下撤回题解或者添加“管理组提示”，或者说明不对题解区进行改动的理由，我愿意听取您们的意见。

上述两点的参考证明：

由 Hall 定理 可知，存在左部点能完全匹配的方案，当且仅当对于左部点的任意子集 $S$ ，都有 $|S|\le |N(S)|$ ，其中 $N(S)$ 为 $S$ 的邻居集合（不为可重集）。

对于本题，若将 $N(S)$ 看作可重集，则有 $|N(S)|=M\cdot |S|$ 。但是我们需要的 $N(S)$ 是不重复的。观察到对于所有的右部点，它们每个在 $N(S)$ 中出现的次数至多为 $M$ ，于是将 $N(S)$ 去重后， $|N(S)|$ 的最小可能为 $\dfrac{M\cdot |S|}{M}=|S|$ 。

因此我们证明了在本题条件下 $|S|\le |N(S)|$ 永远成立，满足 Hall 定理所述结论。故答案总是 Yes，并且随便删一定是对的。

关于此题的现有题解

讨论操作

回复

相关推荐

关于此题的现有题解