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

超图的顶点着色

作　者: 陈星
导　师: 王迪吉；杜智华
学　校: 新疆师范大学
专　业: 基础数学
关键词: 积和式 多项式 Lovāsz局部引理 lopsidepency图 t-着色 色数 复合超图 强着色 强色数
分类号: O157.5
类　型: 硕士论文
年　份: 2008年
下　载: 48次
引　用: 0次
阅　读: 论文下载
 

内容摘要


超图是普通图的推广,普通图的着色在图论中占有重要地位。现已形成着色理论。而超图的着色作为普通图的着色的推广,其研究意义自然更加深刻,内容更加丰富,适用范围自然更为广泛。这篇文章主要研究了超图的着色并获得了一些相关结果。第一部分介绍了与本文有关的基本概念及其为什么要研究图和超图的着色问题。从而说明研究超图的着色是有重要意义的。第二部分研究了超图的多项式与着色的关系,用超图的多项式刻画了超图的着色。特别对超图的2-色多项式进行了具体研究。并且得到了判断一个超图不能2-着色的充要条件及可以2-着色的充分条件。接着又对边数等于顶点数的超图进行了研究,得到了可以2-着色的充分条件。最后由本人定义的多项式得到了一般超图色数的一个上界。这一部分的主要结果如下:命题2.2.H不能2-着色当且仅当p（H）=0,对所有的xi∈{0,1}。命题2.3.如果q（H）的某个系数满足q（H）（?）0（modki）（i 1,2,…,t）,那么H可以2-可着色。定理2.1.如果perm（M）（?）0（modki）（i=1,2,…,t）,那么H可以2-着色。定理2.2.如果对任意的i,若（?）|Ej\{i}|pcrm Mji（?）0（mod 2 ki）那么H可以2-可着色。定理2.3.设H是一个简单超图,那么有x（H）≤s+1。第三部分研究了超图的着色与Lov（?）sz引理的关系,我们利用Lov（?）sz局部引理给出超图可以t-着色的一个充分条件以及对其进行t-着色使得每种颜色在每条边中均出现的充分条件。接着给出了对超图进行2-着色使得每种颜色在每条边中至少出现两次的充分条件。并将该定理推广到t-着色。这一部分的主要结果如下:定理3.3.设H是一个超图,且H的每条边至少有k个点且至多与d条其它的边相交。令t≥2是一个整数。如果e（（d+1）（t-1）+1）t（-k）≤1,那么H有一个t-着色。定理3.4.设H是一个超图,且H的每条边至少有k个点且至多与d条其它的边相交。令t≥2是一个整数。如果e（（d+1）（t-1）+1）（1-（?））k≤1,那么H有一个t-着色且每种颜色在每条边种均出现。定理3.5.设H是一个超图,每条边包含至少k（k≥4）个点,且至多于d条其它的边相交。如果有e（k+1）2-k（d+2）≤1,那么H有一个2-着色且每种颜色在每条边至少出现两次。推广定理.设H是一个超图满足其每条包含至少k（k≥2t）个点且至多于d条其它的边相交。令t≥2,如果e（1-（?））k-1（1-（?）+（?））（d+2）≤1,那么H有一个t-着色使每种颜色在每条边中至少出现两次。第四部分研究了一些构图方式,对一些复合超图得到了其色数,另外的一些得到了它们的界。这一部分的主要结果如下:命题4.1.设H1和H2是两个超图,且x（H1）=λ1,x（H2）=λ2,那么x（H1+H2）=max{λ1,λ2)。命题4.2.设H1和H2是两个超图,其中x（H1）λ1,x（H2）λ2。那么,x（H1（?）H2）-2。命题4.3.设H1和H2是两个超图且x（H1）λ1,x（H2）λ2。那么,x（H1∪H2）≤λ1·λ2。命题4.4.设H1和H2是两个超图,满足x（H1）=λ1,x（H2）=λ2。那么x（H1·H2）≤min{λ1,λ2}.命题4.5.设H1和H2是两个超图,满足x（H1）=λ1,x（H2）=λ2。那么x（H1×H2）≤min{λ1,λ2}。第五部分研究了超图的强着色的一些性质。并确定了某些特殊超图的强色数（详见例1-例5）。与此同时,也提出了关于超图强着色可以进一步研究的一些问题。

全文目录


中文摘要  3-6
Abstract  6-9
文献综述  9-11
1.引言  11-14
  1.1 超图的基本概念  11-13
  1.2 研究背景  13-14
2.多项式在超图着色上的应用  14-18
  2.1 基本概念及研究背景  14-15
  2.2 主要结果  15-18
3.Lov(?)sz局部引理在超图着色的应用  18-23
  3.1 研究背景及已知结果  18-20
  3.2 主要结果  20-23
4.复合超图的色数  23-26
  4.1 研究背景  23-24
  4.2 主要结果  24-26
5.超图的强着色  26-30
  5.1 强着色的基本概念  26-27
  5.2 常见的超图的强着色数  27-29
  5.3 进一步研究的背景及问题  29-30
参考文献  30-32
致谢  32-33

相似论文

  1. 带有多项式基的径向点插值无网格方法的研究及应用,O241
  2. 中学数学竞赛中二次多项式与二次函数问题的研究,G633.6
  3. 涉及微分多项式和例外函数的正规定则,O174
  4. 整系数多项式的因式分解方法研究,O174.14
  5. 两类图的色等价图,O157.5
  6. Poisson-Charlier多项式及其在概率论中的应用,O211
  7. 延迟微分方程数值解的稳定性,O241.8
  8. 非对称量子纠错码的若干问题研究,O413
  9. 无线传感网动态频谱分配算法研究,TP212.9
  10. 多进制LDPC码构造方法的研究,TN911.22
  11. 基于贝叶斯理论的网页木马检测技术研究,TP393.092
  12. 基于着色Petri网的工作流引擎研究,TP311.52
  13. 基于广义随机着色Petri网的C~3I系统建模与仿真技术研究,N945.12
  14. 卫星对地观测需求分析方法及其应用研究,V474.26
  15. 基于Petri网的弹炮协同防空流程优化研究,E917
  16. Ceramage聚合瓷和Filtek Z350纳米复合树脂抗着色性能的体外研究,R783
  17. 三角域上融合曲面造型技术研究,TP391.72
  18. LTE系统数字预失真技术研究,TN929.5
  19. 认知无线电系统中基于图着色论的频谱分配方案,TN925
  20. 工艺偏差下的电源地网络快速仿真分析方法,TN402
  21. 片内偏差空间相关性的非参数化估计方法,TN405

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