易混 2021 年吉林预赛 · P007015
把分配或配对问题转成匹配之后，还须辨认图的类型，不能见到“匹配”就直接套同一个定理。容量任务可拆成名额形成二部图；一般点对图则需要适合一般图的增广论证。
前题从任意一组比赛涉及的球队核霍尔邻域条件；后题由坏伙伴数转成好边最小度数，假设最大匹配留下两个点，再沿已有匹配边证明可以增广。
培玉 · 一试
2024 年北京预赛
F4解答题组合计数综合
有 个球队参加比赛，球队之间的比赛计划已经安排好了，但是每场比赛的主场、客场还没有分配。每个球队都上报了自己能够接受的客场比赛的最大次数。最终组委会发现这些次数之和恰好是比赛的总场次，并且任意挑出若干支球队，它们能够接受的客场次数之和都大于或等于它们之间的比赛总场次。问组委会能否安排好主客场使得每支球队都满意，并证明结论。
作答
这是解答题，请在纸上写出完整过程。写完后对照解答给自己评分。
解析
提示
先独立尝试，再展开工具说明与想法来源。
思路
霍尔匹配定理：二部图左侧每个子集的邻点数至少等于该子集大小，就存在覆盖左侧的匹配；可用不断寻找交替增广路径证明。这里名额容量是非负整数。
想法从哪来：先把一场比赛理解成一个必须交给两队之一承担的“客场任务”。若直接逐场指定，容易早早用光某队名额而误以为无解；给每一个名额单独编号，问题就成了任务与名额能否一一配上。题目对球队子集的限制看似只管内部比赛，而匹配定理要管任意比赛子集：把这些比赛所有端点球队收集起来，内部比赛总数只会更多，便能把题设的不等式搬过来。零容量球队不贡献名额，也不影响这一步。配完之后，总容量恰等于比赛数，才进一步说明没有空余名额，而非只证明各队未超额。
把每场比赛分配给一个“客场名额”。题设对子集的条件正好转化为二部图匹配所需的霍尔条件。
解答
答案是肯定的。设第 支球队可接受的客场次数为 。建立二部图：左侧每个顶点代表一场比赛；右侧为第 队建立 个互不相同的客场名额；一场比赛与其两支参赛队的全部名额相连。
任取左侧若干场比赛组成集合 ，设这些比赛涉及的球队集合为 。每场属于 的比赛都发生在 内部，故
而右端正是 的邻点名额数。因此该二部图满足霍尔条件，存在覆盖所有比赛顶点的匹配。
把每场比赛匹配到的球队指定为客队。这样每个名额至多使用一次，所以每队客场次数不超过 。又因
左右两侧顶点总数相等，匹配事实上也用尽全部名额，每队恰有 场客场比赛，因而所有球队都满意。
复核
若同两队有多场比赛，也只是在左侧出现多个比赛顶点，霍尔论证仍成立；空球队集合与单队集合的条件自动满足。
方法总结
“每个任务从两个承担者中选一人，并受容量限制”是典型的容量匹配模型；把容量拆成名额后，子集内任务数条件就是霍尔条件。
为什么评为 F4（会透露解法方向）
须将一场比赛对应到可选客队名额，把球队子集条件转换成任意比赛子集的霍尔条件，再解释匹配满足容量。
联系 · 1 条
已记下，谢谢！