混合多重图的边着色

论文摘要

近年来,超图理论得到迅速发展和完善。超图是有限集合的子集系统,是离散数学中最一般的结构,超图的着色理论在离散数学中起着非常重要的作用。为了很好的解决能源供应、工作排序等领域中的相关问题,著名学者、数学家Voloshin在1995年于传统超图概念的基础上,根据染色的要求不同,提出了混合超图的概念及其相关理论。混合超图及其相关理论自提出以来发展迅速,研究方法、途径多样。Daniel Král. Jan Kratochvíl. Heinz-Jürgen Voss.等学者曾在其论文《Mixed hypergraphs with bounded degree: edge-coloring of mixed multigraphs》中提出任何一个混合超图均可一一对应地转化成一个最大度不超过3的混合超图,且它们的着色亦是一一对应的。因此,研究最大度为3的混合超图的着色问题具有一般性,是困难的;而研究最大度为1的混合超图的着色问题是平凡的;所以我们着力研究最大度为2的混合超图的着色问题。最大度不超过2的混合超图的点着色可以一一对应地转化为相应的混合多重图的边着色,而图及多重图的边着色理论和方法是我们所熟知的。基于这一观点,本文研究混合多重图的边着色问题,通过对混合多重图边着色理论的研究来发展和完善混合超图的着色理论。整篇文章中,对混合多重图边着色及其相关理论的研究分如下几个部分:第一部分:引言,主要给出本文的研究意义和所研究的混合多重图的类型;第二部分:给出混合多重图的定义及其相关的基本概念;第三部分:结合相关的命题、引理,研究特殊的混合多重图（即最大重复度μ=1的混合多重图）——混合图的边着色问题及其相关理论,并得到定理3 .2.4、定理3 .3.2、定理3 .3.4、定理3 .3.5、定理3 .3.6、定理3 .4.5等较好的结果;第四部分:研究具有较好结构的混合多重图（即最大重复度μ≥2的混合多重图）的边着色及其相关理论,并得到定理4 .2.1、定理4 .2.2、定理4 .2.3、定理4 .2.4等结果。

论文目录

• 摘要
• ABSTRACT
• 文献综述
• 1. 引言
• 2. 基本定义
• 3. 混合图
• 3.1 基本定义及性质
• 3.2 基本结果
• 3.3 不含有 C-圈的混合图G 的结果
• 3.4 含有 C-圈且任一C-圈集是独立圈集的混合图G 的结果
• 4. 混合多重图（最大重复度μ≥2 ）
• 4.1 基本定义
• 4.2 基本结果
• 5. 总结
• 参考文献
• 附录
• 致谢