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

From EtoneWiki
Jump to: navigation, search

Problem 1

为一个二分图。令 这一侧的最小度数, 这一侧的最大度数。证明:如果,则存在一个 的匹配(matching)使得 中所有的点都被匹配。

Problem 2

用Dilworth定理证明:对于任意n个不同的集合 ,我们总能找到 使得 ;且对任意不同的 ,有

Problem 3

为一个 0-1 矩阵。已知:

  • 中共有 个1;
  • 的每行和每列有至多 个1;
  • 中没有 的全1子矩阵。

用 König-Egerváry 定理证明:至少需要 个全1子矩阵才能覆盖 中所有的1。

Problem 4

为一个二分图, 是这个二分图的两个匹配。假设有 中所有的点都被 匹配, 中所有的点都被 匹配。证明: 中存在一个匹配使得 中所有点都被匹配。