组合数学 (Fall 2011)/Problem set 5

Problem 1

令 [math]\displaystyle{ G(U,V,E) }[/math] 为一个二分图。令 [math]\displaystyle{ \delta_U }[/math] 为 [math]\displaystyle{ U }[/math] 这一侧的最小度数，[math]\displaystyle{ \Delta_V }[/math] 为 [math]\displaystyle{ V }[/math] 这一侧的最大度数。证明：如果[math]\displaystyle{ \delta_U\ge \Delta_V }[/math]，则存在一个 [math]\displaystyle{ G }[/math] 的匹配（matching）使得 [math]\displaystyle{ U }[/math] 中所有的点都被匹配。

Problem 2

用Dilworth定理证明：对于任意n个不同的集合 [math]\displaystyle{ S_1,S_2,\ldots,S_n }[/math]，我们总能找到 [math]\displaystyle{ \mathcal{F}\subseteq \{S_1,S_2,\ldots,S_n\} }[/math] 使得 [math]\displaystyle{ |\mathcal{F}|\ge \lfloor\sqrt{n}\rfloor }[/math]；且对任意不同的 [math]\displaystyle{ A,B,C\in\mathcal{F} }[/math]，有 [math]\displaystyle{ A\cup B\neq C }[/math]。

Problem 3

令 [math]\displaystyle{ A }[/math] 为一个 0-1 矩阵。已知：

• [math]\displaystyle{ A }[/math] 中共有 [math]\displaystyle{ m }[/math] 个1；
• [math]\displaystyle{ A }[/math] 的每列有至多 [math]\displaystyle{ s }[/math] 个1；
• [math]\displaystyle{ A }[/math] 中没有 [math]\displaystyle{ r\times r }[/math] 的全1子矩阵。

用 König-Egerváry 定理证明：至少需要 [math]\displaystyle{ \frac{m}{sr} }[/math] 个全1子矩阵才能覆盖 [math]\displaystyle{ A }[/math] 中所有的1。

Problem 4

[math]\displaystyle{ G(U,V,E) }[/math] 为一个二分图，[math]\displaystyle{ M, M' }[/math] 是这个二分图的两个匹配。假设有 [math]\displaystyle{ S\subset U }[/math] 和 [math]\displaystyle{ T\subset V }[/math]，[math]\displaystyle{ S }[/math] 中所有的点都被 [math]\displaystyle{ M }[/math] 匹配，[math]\displaystyle{ T }[/math] 中所有的点都被 [math]\displaystyle{ M' }[/math] 匹配。证明：[math]\displaystyle{ G }[/math] 中存在一个匹配使得 [math]\displaystyle{ S\cup T }[/math] 中所有点都被匹配。