混合多重图的边着色论文

《混合多重图的边着色论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、新疆师范大学硕士学位论文　摘要　近年来，超图理论得到迅速发展和完善。超图是有限集合的子集系统，是离散数学中最一般的结构，超图的着色理论在离散数学中起着非常重要的作用。　为了很好的解决能源供应、工作排序等领域中的相关问题，著名学者、数学家Voloshin在１９９５年于传统超图概念的基础上，根据染色的要求不同，提出了混合超图的概念及其相关理论。　混合超图及其相关理论自提出以来发展迅速，研究方法、途径多样。Ｄａｎｉｅｌ　Ｋｒáｌ．　Ｊａｎ　Ｋｒａｔｏｃｈｖíｌ．　Ｈｅｉｎｚ－Ｊüｒｇｅｎ　Ｖｏｓｓ．等学者曾在其论文

2、《Ｍｉｘｅｄ　ｈｙｐｅｒｇｒａｐｈｓ　ｗｉｔｈ　ｂｏｕｎｄｅｄ　ｄｅｇｒｅｅ：　ｅｄｇｅ－ｃｏｌｏｒｉｎｇ　ｏｆ　ｍｉｘｅｄ　ｍｕｌｔｉｇｒａｐｈｓ》中提出任何一个混合超图均可一一对应地转化成一个最大度不超过３的混合超图，且它们的着色亦是一一对应的。因此，研究最大度为３的混合超图的着色问题具有一般性，是困难的；而研究最大度为１的混合超图的着色问题是平凡的；所以我们着力研究最大度为２的混合超图的着色问题。最大度不超过２的混合超图的点着色可以一一对应地转化为相应的混合多重图的边着色，而图及多重图的边着色理论和方法

3、是我们所熟知的。基于这一观点，本文研究混合多重图的边着色问题，通过对混合多重图边着色理论的研究来发展和完善混合超图的着色理论。　　　　　整篇文章中，对混合多重图边着色及其相关理论的研究分如下几个部分：　　　　　第一部分：引言，主要给出本文的研究意义和所研究的混合多重图的1新疆师范大学硕士学位论文　类型；　　　　　第二部分：给出混合多重图的定义及其相关的基本概念；　　　　　第三部分：结合相关的命题、引理，研究特殊的混合多重图（即最大重复度µ=1的混合多重图）——混合图的边着色问题及其相关理论，并得到定理3.2.

4、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等结果。　关键词：混合多重图；混合图；上色数；下色数；可行集。　2新疆师范大学硕士学位论文　ABSTRACTHypergraphisasubsetsystemoffinitesets.Thetheoryofhypergraphsisgrowing

5、rapidly.Thecoloringtheoryofhypergraphplaysanimportantroleindiscretely-divisiblemathematics.In1995Voloshinproposedtheconceptofmixedhypergraphinthefoundationofconditionalhypergraph.Itisveryhelpfultoattackrelativeproblemsinsuchareasasschedulingofsystemsofpower

6、supplies,jobscheduleandavarietyofappliedareas.IntroducedbyVoloshin,avariantofstudyingmethodsandwaysareappliedinmixedhypergraphs.SuchsomeleanedmenasDanielkral,jankratochvil,Heinz-jurgenvossconcludethatonecanconstructamixedhypergraphwithmaximumdegreethreewhos

7、epropercoloringsone-to-onecorrespondtothepropercoloringsoftheoriginalone.Thoseoneswithmaximumvertexdegreeonearetrivialandthoseoneswithmaximumvertexdegreethreearenotlessgeneralthanallmixedhypergraphsanddifficulty.Thus,werestrictourattentiontomixedhypergraphs

8、withmaximumvertexdegreetwo.Again,theyproposethatthereisamixedmultigraphwhoseproperedge-coloringsone-to-onecorrespondtothepropervertex-coloringsofanymixedhypergraph.Sincewearefamiliartothetheoryandmetho