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

概率方法与图的染色问题

作　者: 孙宜蓉
导　师: 刘信生；陈祥恩
学　校: 西北师范大学
专　业: 应用数学
关键词: 概率方法边染色最大度引理主要性质边色数全染色矩量具体实例应用实例
分类号: O157.5
类　型: 硕士论文
年　份: 2004年
下　载: 203次
引　用: 0次
阅　读: 论文下载

内容摘要

本文共分四个部分。第一部分主要是引入一些在本文中经常出现的的基本概念和主要性质，并对某些概念给出具体实例。第二部分介绍了第一矩量原理，Markov不等式以及四种形式的Lov(?)sz局部引理的内容，给出了这几种概率方法在超图上的应用，用几种思路找到了超图存在2-可染色的不同条件，其中着重对一般形式的Lov(?)sz局部引理给出应用实例，即无圈边染色，证明了当图G的围长大于等于700ΔlogΔ时，图G的无圈边色教小于等于△+2然后，用概率论的方法证明了几种形式的Lov(?)sz局部引理，并从中发现几种Lov(?)sz局部引理之间的关系，找出其不同的适用范围。第三部分主要讨论了邻点可区别的边染色这一概念，用第一矩量原理，Markov不等式以及几种形式的Lov(?)sz局部引理分别得到了任一最大度为d的图G的邻点可区别的边色数。第四部分引入了邻点可区别的全染色这一新的概念，并用第一矩量原理，Markov不等式以及几种形式的Lov(?)sz局部引理分别得到了任一最大度为d的图G的邻点可区别的全色数。

全文目录

独创性声明  4-5
摘要  5-6
Abstract  6-7
前言  7-8
1 基本概念和性质  8-10
2 几种概率方法及应用  10-19
3 邻点可区别的边染色  19-24
4 邻点可区别的全染色  24-30
参考文献  30-32
致谢  32

概率方法与图的染色问题

内容摘要

全文目录

相似论文