二部图的彩虹匹配问题

摘要

彩虹问题是图论中的重要研究内容之一，是在染色基础上研究的。早在上个世纪五六十年代国内外就已经有很多伟人在进行研究，但是由于在当时彩虹问题的实践应用意义不是特别的突出，彩虹问题也一直没有被广泛重视起来。最近随着科技的发展，计算机科学的兴起，图论也越来越被重视，同时彩虹问题成为一个热点问题被更多人所研究。现在人们对彩虹问题的内容研究的非常广泛，根据染色的方式可以分为正常染色的彩虹问题和非正常染色的彩虹问题。根据彩虹问题研究的具体内容，图论中研究比较多的有彩虹路，彩虹圈，彩虹树，彩虹圈，单色树，单色匹配，彩虹匹配等等。这些都是在染色的基础上提出的有很大的应用价值。
　　如果说图论是浩瀚的宇宙，那么彩虹问题就是整个太阳系，彩虹问题所涉及的问题不仅量多如牛毛，还种类繁多，要想有个系统的仔细的介绍，工作量实在是太巨大了，为了不浪费大家太多的精力，我在这篇论文中主要介绍了与我所研究内容有关的一些知识背景。为了方便大家更容易接受本文所讲的内容，在第一章研究背景1.2.1中主要介绍了与拉丁截线有关一些知识背景。在第一章研究背景1.2.2中重点介绍了图的边染色和彩虹匹配的基本概念，研究历程及经典的研究方法。众所周知彩虹问题现在已经不仅仅是图论问题，涉及到计算机网络，组合数学，数论等方面的知识，所以在本论文的研究过程中还用到了这些知识。
　　二部图中的彩虹匹配问题的鼻祖是古时候人们对于拉丁截线的猜想及研究，后来才转化为彩虹匹配问题进行研究的。拉丁截线是从现实生活中的实际问题转化来的，用图来描述拉丁截线可以这样认为拉丁截线指的就是拉丁方A中n个来自不同行不同列的互异的元素构成的集合，其中拉丁方就是由n行n列元素构成的方阵An×n。很多年前Aharoni和Berger提出这样一个猜想:任何一个由n个来自同一二部图的大小n+1匹配构成的集族，都包含一个大小为n的完美彩虹匹配。对于这个猜想虽然至今未解决，但是后人做了很多逼近这个猜想的结果和猜想。在第一章研究背景1.2.3中对Aharoni和Berger猜想的研究历程及成果作了详细的介绍。
　　当d＞1并且F1,…，Fk为同一二部图内的边集，当其满足△(Fi)≤d且|Fi|＞(k-1)d时，集族F1,…，Fk存在一个大小为k的完美彩虹匹配.这是后来Aharoni和Howard又提出的猜想。我们知道这个猜想是不正确的，因为当n=1时，这个猜想是错误的。本论文第二章主要证明了F1,…，Fk为同一二部图G(A∪ B，E)内的边集，当其满足△（Fi）≤2且|Fi|=n时，其中i=1,…，k，n=[23/7k]，集族F={F1,…，Fk}存在一个大小为k的完美彩虹匹配。这个结论的证明过程虽然比较复杂，但是证明思路还是比较清晰的。这个论题的证明过程主要分两大部，借鉴了很多前人的证明方法，尤其是前人对二部图中匹配集族的彩虹匹配问题的证明技巧，比如边的替换，反证法，鸽巢原理等证明方法。
　　本论文的第三章主要是从彩虹路问题角度去研究的，研究的主要内容是关于完全图的彩虹路问题。我们知道对于任意一个正常染色的完全图Kn来说，都存在一个大小为(3/4-o(1))n的彩虹路，本论文第三章主要证明了一个正常染色的完全二部图Kn,n的最大彩虹路的长度的一个下界是2/3n，并对此做出了一个猜想。在证明过程中也借鉴了前人的经验，使用了反证法，鸽巢原理等证明方法。
　　本文第四章是对第二章的一些简单的推论，即如果F1,…，Fk为同一二部图G(A∪ B，E)内的边集，当其满足△（Fi）≤2且|Fi|=n，设Fi中奇数圈和奇数路的数量之和为mi其中i=1,…，k，m=min{m1,………,mk}，如果m+n≥[33/7k]则集族F={F1,…，Fk}存在一个大小为k的完美彩虹匹配。如果F1,…，Fk为同一二部图G(A∪B，E)内的边集，当其满足△(Fi)≤2且|Fi|=2k-1,当k=1,2,3,5,7,9时则集族F={F1,…，Fk}存在一个大小为k的完美彩虹匹配。启发我们彩虹匹配问题还可以从圈的角度去考虑。第五章介绍了本论文所研究内容的实际应用价值，可以使我们对彩虹匹配问题，彩虹路问题有更清晰的认识。

目录

声明

摘要

第一章 绪论

§1．1 预备知识

§1．2 研究背景

1．2．1 拉丁截线的研究背景

1．2．2 彩虹边染色图的研究背景

1．2．3 彩虹匹配的研究背景

第二章 证明f(k)≥[23／7k]时集族F存在完美彩虹匹配

§2．1 k＜56时集族F存在完美彩虹匹配

§2．2 k≥56时集族F存在完美彩虹匹配

第三章 完全二部图的彩虹路问题

§3．1 完全二部图Kn，n的最大彩虹路的长度不小于2／3n

§3．2 完全二部图Kn，n的最大彩虹路的长度不小于4／5n

第四章 彩虹匹配的其他有关推论及实际应用价值

参考文献

致谢