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

From EtoneWiki
Jump to: navigation, search

Problem 1

一个set family blocking set 是这样一个集合 ,使每一个 member set 都有 。当 的时候, 就是一个图,而 blocking set 就是这个图的顶点覆盖(vertex cover)。因此,blocking set 就是顶点覆盖在超图(hypergraph)上的推广。我们知道最小定点覆盖(minimum vertex cover)问题是 NP-hard 问题,因此求最小 blocking set 也是难的。

证明:任何 , ,都存在一个不大于 的 blocking set。

Problem 2

一个图 支配集 (dominating set) 是一个顶点集合 ,使得每个顶点 要么属于 要么有邻居属于 。最小支配集 (minimum dominating set) 是 NP-hard问题。

证明:任何一个 个顶点的 -regular 图(每个顶点恰好有 个邻居),必然存在一个不大于 的支配集。

Problem 3

为一个图, 为一个整数。已知存在一个图 不包含 子图。

证明:对于 ,存在一个对 结点完全图)的 着色,没有单色(monocharomatic)的

注:令 的边集为 ,“对 的边的 着色",就是一个映射 。 即,每个边选择 种颜色之一进行着色,可以任意着色,无需考虑相邻的边是否同色。

Problem 4

一个图 的 independence number 中最大的独立集 (independent set) 的大小。证明Turán定理的对偶(dual)版本:

定理
如果图 个结点, 条边,,则

要求至少给出两个版本的证明:

  1. 用概率法证明。
  2. 用Turán定理直接证明。

Problem 5

我们称一个竞赛图 传递(transitive)的,如果存在一个 的全排列 使得 当且仅当 ,即该竞赛图 的边的方向符合传递性。

证明:对任何 ,存在 ,对任何的 个点的竞赛图,都存在一个 个点的子竞赛图满足传递性。