^-^
Ramsey 定理

这是一个简单的衡量任意图中团或独立集大小的版本:

对于任意 ,则 中存在大小至少为 的团或独立集.

Proof 构造如下算法:

即构造两个集合 初始化为空集, 逐一遍历图中的结点, 设候选节点的集合为 , 如果

  • , 则将 放到 中, 并删掉 中所有与 不相邻的结点(包括 );

  • , 则将 放到 中, 并删掉 中所有与 相邻的结点(包括 ).

当 时终止算法. 显然 是 的团, 是 的一个独立集.

当 时, 删掉的所有不与 相邻的结点的个数至多为 ; 时 删掉的所有与 相邻的结点的个数也至多为 , 因此每一轮执行候选节点数至多减少为原来的一半, 算法共至少需要 轮才能结束, 每一轮都有一个点进入 或者 ， 则此时有 ,则 , 这就是要证的.

TODO: 补充 Ramsey 定理更多的内容.

Ref: Introduction to the Theory of Computation.

2024-01-07 该篇文章被 Baoduo Xu 归为分类: 杂项

以上
©
Too Young Too Naive 本站由Hexo驱动｜使用Hexo-theme-A4主题