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

超图的边着色

作　者: 王娜
导　师: 王迪吉；杜智华
学　校: 新疆师范大学
专　业: 基础数学
关键词: 边着色 完全r-partitioned超图 线性超图 线性超树 成分着色
分类号: O157.5
类　型: 硕士论文
年　份: 2008年
下　载: 28次
引　用: 0次
阅　读: 论文下载
 

内容摘要


超图是一般图的重要推广,超图的着色概念也是一般图着色概念的自然推广。对于超图的着色有很多各种各样的应用背景,如时间表问题,资源的分配问题。而且它与其它的组合问题也有着广泛的联系,例如极值理论,Ramsey理论,概率方法,差值理论等等。在近三十年中,超图的着色问题已经有许多人研究,并且获得了很多结果。第一章主要研究完全r-partitioned超图的边着色。设H是一个超图,它的顶点集合V被划分为r个部分即V={V1,…,Vr),给定一个r维向量M=（p1,p2,…,pr）（Pi∈N*,1≤i≤r）,H中的边集是V中的每个多重集E并且满足: M (|E∩V1|,(|E∩V2|,…,（|E∩Vr|）,则我们称H是完全r-partitioned超图Kn1,n2,…,nrM,或记为Kn1,n2,…,nrp1,p2,…,pr。本人在这一章里得到了四个主要结论和一个猜想。定理1.2.1:若完全r-partitioned超图Kn1,n2,…,nr2,2,…,2,并且设n1≤n2≤…≤nr。如果2|n1,则(q（H）-（n1-1）（?）…（?）,否则(q（H）-n1（?）···（?）。定理1.2.2:若完全r-partitioned超图Kn1,n2,…,nrt,t,…,t,并且设n1≤n2≤…≤nr。如果有t|ni,或者（?）|（?）（1≤i≤r）,则q（H）=（（?））（（?））…（（?））（?）-1。定理1.2.3:若完全r-partitioned超图Kn1,n2,…,nrt,t,…,t,并且设n1≤n2≤…≤nr。如果t（?）ni且（?）（?）（（?））（1≤i≤r）,则定理1.2.4:若完全r-partitioned超图Kn1,n2,…,nrp1,p2,…,pr,并且设n1≤n2≤…≤nr。则（?）猜想1.2.1:若完全r-partitioned超图Kn1,n2,…,nrt,t,…,t,并且设n1≤n2≤…≤nr。则（?）第二章研究了线性超图的边着色。设H是一个超图,如果对任意两条边Ei,Ei（i≠j）,有|Ei∩Ej|≤1。若H是无圈的线性超图则我们称为线性超树。本人在这一章里得到了四个结论。定理2.2.1:设H是n个顶点上的无环线性超图,若S是由边秩大于等于3的边导出的部分超图。如果△s-2,q（S）-3,则q（H）≤n。定理2.2.2:设H是n个顶点上的无环线性超图,若S是由边秩大于等于3的边导出的部分超图。如果△s≤3,q（S）≤3,则q（H）≤n。定理2.2.3:设H为r阶射影平面,则q（H）=r2-r+1。定理2.3.1:设H是线性超树,且H的最大度为△,则q（H）=△。第三章研究了路,0图,Ti*（见图3.1）这三类图的成分着色。设H是个超图,对于它的一个k-边着色c:E（H）→{1,2,…,k),f（H,c）是由这k种颜色中同一色类导出的子超图中所含分枝数最少的子超图的分枝数。fk（H）表示H中所有k-边着色中f（H,c）的最大值,本人在这一章里得到了三个结论。定理3.2.1:设Pn是n个顶点的一条路,则fk（Pn）=（?）。定理3.2.2:f（Ti*）=（?）+1,（见图1（a））。定理3.2.3:设G0是0-图,则fk（G0） 2,（见图1（b））。

全文目录


中文摘要  3-5
Abstract  5-8
文献综述  8-11
1.完全r-partitioned超图  11-19
  1.1 基本概念  11
  1.2 主要结论  11-19
2.线性超图  19-25
  2.1 研究背景  19
  2.2 一般线性超图  19-22
  2.3 线性超树  22-25
3.特殊图的成分着色  25-28
  3.1 研究背景  25
  3.2 主要结论  25-28
参考文献  28-29
致谢  29-30

相似论文

  1. 关于图的几类着色和与强度的研究,O157.5
  2. 若干图类的强边着色,O157.5
  3. 伪Halin图的着色,O157.5
  4. 对称拉丁方的计数,O157.5
  5. 超图的奇圈横贯和偶边着色,O157.5
  6. 线性超图的谱,O157.5
  7. 四着色新算法及其应用,O157.5
  8. 一些图的圆边色数,O157.5
  9. 若干图的连续边着色,O157.5
  10. 两类图的连续边着色,O157.5
  11. 教务排课系统的设计与实现,TP311.52
  12. 13阶色指数临界图,O157.5
  13. 3色Ramsey数R（C_m_1，C_m_2，C_m_3）,TP301.6
  14. 一些图类的连续边着色,O157.5
  15. 仙人掌的连续边着色,O157.5
  16. 第Ⅱ类正则图的色特征,O157.5
  17. 山东商业职业技术学院排课系统的研究,TP319
  18. 超图各参数间的关系以及超图的边色数问题,O157.5
  19. Some Upper Bounds of Ramsey Functions,O157.5
  20. 若干图着色问题的研究,O157.5

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