学位论文 > 优秀研究生学位论文题录展示

概率方法在超图二染色问题中的应用

作　者: 董超
导　师: 邓大萌
学　校: 上海交通大学
专　业: 应用数学
关键词: 概率方法 超图染色 平衡染色 上下界
分类号: O157.5
类　型: 硕士论文
年　份: 2011年
下　载: 17次
引　用: 0次
阅　读: 论文下载
 

内容摘要


概率方法的主要思路是构造研究对象的一个适当的概率空间,继而指出不具备所要求性质的对象发生的概率之和小于1,那么具备所要求性质的对象发生的概率就大于0,因此这样的组合对象是存在的。Paul Erd?s较早地将概率方法应用于超图的二染色中,其问题可概括为对n一致超图H的顶点进行任意的二染色,顶点被染成红色或蓝色的概率均为1/2,定义性质B为总有一些边被染成同色,m ( n )表示n一致超图H具有性质B的最小边数,最后对m ( n )的上下界给出估计。在此基础上我们进一步讨论了超图的平衡染色问题,对n一致超图H进行任意的二染色,总有一些边的染色是不平衡的为性质Bb , mb ( n )表示n一致超图H具有性质Bb的最小边数,利用概率方法我们对mb ( n )的上下界给出估计。

全文目录


摘要  5-6
ABSTRACT  6-8
第一章 绪论  8-13
  1.1 概率基本方法简介  8-10
  1.2 概率方法在Ramsey 数中的应用  10-12
  1.3 概率方法在竞赛图中的应用  12-13
第二章 二染色问题  13-19
  2.1 二染色问题简介  13-14
  2.2 对于具有性质B的超图F中m(n)的下界估计  14
  2.3 对于具有性质B的超图F中m(n)的上界估计  14-18
  2.4 本章小结  18-19
第三章 平衡染色问题  19-29
  3.1 平衡染色问题简介  19-20
  3.2 对于具有性质Bb的超图F中mb(n)的下界估计  20-21
  3.3 对于具有性质Bb的超图F中mb(n)的上界估计  21-28
  3.4 本章小结  28-29
第四章 重染色问题  29-36
  4.1 重染色问题简介  29-30
  4.2 重染色方法（具有性质B的超图F中对于m(n)下界的改进）  30-35
  4.3 本章小结  35-36
第五章 讨论与总结  36-38
  5.1 全文总结  36-37
  5.2 问题讨论  37-38
参考文献  38-41
致谢  41

相似论文

  1. 无人机视觉着陆引导中的位姿估计问题研究,V249.32
  2. 带上下界均衡问题解的存在性、稳定性分析及其算法,O177
  3. 一类紧致黎曼流形的特征值问题研究,O186.12
  4. 关于几类图的分数色数,O157.5
  5. 工件可拒绝的在线排序问题的两个模型,O223
  6. 部分机器分批的平行机在线排序,O223
  7. 微阵列比较基因组杂交技术在诊断和产前诊断不平衡染色体畸变中的应用,R714.55
  8. 一类连分数的线性型下界研究和几类代理签名方案设计,TN918.1
  9. 连分数对数的线性型下界与基于身份的签名的研究,TN918.1
  10. 布尔函数的代数免疫度和扩展代数免疫度,TN918.1
  11. 带进位反馈移位寄存器的相关问题,TN918.1
  12. 链组约束下的平行机排序问题,O223
  13. 链组约束下的平行机在线排序,O223
  14. 概率方法在组合恒等式证明中的应用,O157
  15. 量化布尔范式的近似知识编译方法,TP182
  16. 基于D.C.分解的非凸二次规划SDP近似算法,O221.2
  17. 线性模型中参数估计相对效率的研究,O212.1
  18. 风电机组雷击损害风险评估方法研究,TM862
  19. 基于正交变换的时间序列索引,TP311.13
  20. 关于正则图的最大亏格的下界,O157.5

中图分类: > 数理科学和化学 > 数学 > 代数、数论、组合理论 > 组合数学（组合学） > 图论
© 2012 www.xueweilunwen.com