超图的多色染色和单色路划分问题研究

论文摘要

设H是一个超图.如果超图H=（V（H）,E（H））,|V（H）|=n,满足任意kk个点都恰好是一条超边∈∈E(则称超图H为完全的k-一致超图,简记为Kn（k）.完全的3-部3-一致超图,我们简记为Kn1,n2,n3（3）,它是指将V（H）划分成点不交的三部分V1,V2,V3,即（?）Vi=V（H）,Vi∩Vj=（?）,其中1≤i<j≤3,并且对任意的u ∈ V1,v ∈V2,ω∈V3.对应有超边uvw ∈ E（H）.超图H的一个m-点染色是指对超图H的顶点进行m种颜色1,2,.…,m的一个分配,如果超图H的一个m-点染色使得超图中没有单色超边,那么我们称超图H是m-可染的.特别地,超图H是2-可染的也称超图H有性质B.如果超图H的一个m-点染色,满足每条超边包含每种颜色的至少一个顶点,则我们称超图H的这个m-点染色为多色m-染色（polychromatic m-coloring）.值得注意的是,如果超图H有一个多色m-染色那么超图H就有一个多色l-染色,其中1 ≤ l ≤ m.首先,本论文在研究已有的超图的2-染色的相关结论的基础之上,讨论了关于超图的顶点的多色染色.我们对两个问题很感兴趣:（1）如何让超图的一个多色m-染色的m的值尽可能的大?（2）怎样在多色染色中让超边中每种颜色的顶点数出现的尽可能的均匀?我们得到了关于超图的顶点的多色染色的两个结果,改进了之前的部分结果.我们定义超图H*为超图H=（V,E）的对偶,其中V={X1,x2,...,xn},E={Yi,Y2,...,Ym},超图H*的顶点f1,f2,...,fm对应超图H的超边,并且它的超边Xi={yj|xi ∈ Yj},i=1,2,...,n.超图H*的一个多色m-染色对应H的一个覆盖m-分解.因此超图H的多色m-染色的结论可以用对偶形式陈述.其次,我们讨论了完全超图的2-边染色,通常用红色和蓝色这两种颜色来表示.目前对于完全超图的2-边染色的单色放松路划分的研究结果相对较少,先前主要集中对完全kk-一致超图的研究.本论文首次研究了均衡的完全3-部3-一致超图的2-边染色的单色放松路的划分问题,为以后研究一般的kk-部k-一致超图的单色划分问题打下基础.本论文共分四章进行讨论.第一章,我们主要介绍了图与超图的染色问题及超图划分问题的背景及意义,给出了本篇论文中所涉及到的基本概念与符号,阐述了超图的多色染色和单色划分问题的研究现状,列出了本文的主要结果.第二章,我们讨论了超图的点的多色染色与边覆盖分解.第三章,我们研究了均衡的完全3-部3-一致超图的单色放松路划分的问题.第四章,我们指出了本论文可进一步研究的问题.

论文目录

• 中文摘要
• 英文摘要
• 第一章 引言
•   §1.1 基本概念与符号
•   §1.2 超图的多色染色问题的研究现状
•   §1.3 超图的单色划分问题的研究现状
•   §1.4 本文的主要结果
• 第二章 超图的多色染色与边覆盖分解
•   §2.1 预备知识
•   §2.2 超图的多色m-染色
•   §2.3 超图的边覆盖分解
• 第三章 均衡的完全3-部3-一致超图的单色路划分问题
• 第四章 可进一步研究的问题
• 参考文献
• 攻读学位期间发表或提交的学术论文
• 致谢

文章来源

类型: 硕士论文

作者: 李婷婷

导师: 张霞

关键词: 超图,多色染色,覆盖分解,均衡的完全部一致超图,边染色,单色路

来源: 山东师范大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 山东师范大学

分类号: O157.5

DOI: 10.27280/d.cnki.gsdsu.2019.000035

总页数: 37

文件大小: 1966K

下载量: 19