• 主题
高级搜索  >
历史搜索 清空历史
首页> 中文学位 >Stern-Lovász定理及在组合结构中的应用
【6h】

Stern-Lovász定理及在组合结构中的应用

代理获取
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

在组合数学和图论中，概率方法是一个强大有力的工具。概率方法的思想大致是这样的：如果要证明具备某些性质的某种结构存在，我们先定义一个此结构的概率空间，只要证明在这个空间中所需性质存在的概率大于0，就证明了这种结构的存在性。这种方法的特点在于，对于具有某种特性的研究对象的存在性，不用去具体构造研究对象，而是通过构造研究对象的一个适当的概率空间去证明。 概率方法虽然是一个强大的工具，但是利用它我们只能得到一个具有特定性质的某种组合结构存在与否的结论。而在很多的实际应用中，我们不仅需要知道具有特定性质的某种组合结构存在与否，更多的时候，我们还需要找到一个满足这种性质的一个结构，去进行计算或者处理。 Stern-Lovász 定理可以用来解决一些组合结构的存在性问题。与概率方法相比，通过Stern-Lovász 定理解决组合结构的存在问题更体现出构造性的特点。 在这篇文章中，我们首先给出了Stern-Lovász定理的一个简要证明。并且将这一定理利用于一些经典组合结构存在性的界的证明中，其中包括完美散列族（Perfect Hash Family）、分离散列族（Separate Hash Family）、分裂系统（SplittingSystem）和覆盖设计（Covering Design）。最后，我们对Stern-Lovász 定理得到的存在性的界和利用基本概率方法得到的界进行比较。 这些结果与概率方法得到的结果基本相同，但是从证明过程中表现出了构造性的特点。因此，一定的意义上，我们可以把Stern-Lovász定理看作讨论过的这几个组合结构的基本概率方法的去随机化算法。

著录项

相似文献

  • 中文文献
  • 外文文献
  • 专利
代理获取

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号