二部图中有关点不交子图的研究.docx

《二部图中有关点不交子图的研究.docx》由会员分享，可在线阅读，更多相关《二部图中有关点不交子图的研究.docx（146页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、宁夏大学硕士学位论文 摘要目录一 二部图中有关点不交子图的研究1二 海藻酸钠基复合吸附材料的制备及对亚甲基蓝的吸附研究28三 一维纳米材料增强纤维素基复合膜的构筑及性能研究66四 纯文本106 一 二部图中有关点不交子图的研究摘 要图论作为组合数学的一个重要范畴, 具有深远的历史. 二部图是将图的顶点集分成两部集和, 且中的任意一条边必然是由中的一个顶点和中的一个顶点连接构成的.如果图中任意两个顶点的边数至多为, 则称为标准多重二部图,二部图中点不交的圈(独立圈)以及弦圈的存在问题一直是图论的热点问题. 因此本文主要研究了: 标准多重二部图中点不交的重圈和二部图中包含点不交弦圈的边界条件.本文

2、一共分为了三章内容. 第一章介绍了和本文相关的术语和概念, 同时陈述了本文的研究背景; 第二章主要研究了标准多重二部图中点不交的重圈问题: 若标准多重二部图满足, 是正整数, 的最小度至少为, 则当为奇数时, ; 当为偶数时, , 除一个特例外. 且提出了一个进一步可讨论的问题. 第三章主要证明了: 设为正整数, 是一个二部图, 满足, , 则包含至少一个弦圈. 作为推广, 紧接着证明了 设为正整数, 是一个二部图, 满足, , 则包含个点不交的弦圈.关键词： 二部图, 度条件, 弦圈, 点不交.2 宁夏大学硕士学位论文 Abstract AbstractGraph theory, as an

3、 important category of combinatorial mathematics, has a long history. Bipartite graph is the vertex set of graph is divided into two sets of and, and each edge in graph must by of a vertex and a vertex of the connection. If any two vertices have at most edges in graph , we called the standard multip

4、le bipartite graphs. And the problem of the disjoint circle (the independent circle) is that the graph and the existence of string circle in bipartite graph has always been a hot topic in graph theory. This paper mainly studied : The disjoint of weight cycles in the standard multiple bipartite graph

5、s and the edge condition for independent cycles with chords in bipartite graphs.This paper is divided into three chapters. The first chapter mainly introduces the simple terms and basic concepts related to this paper. In the second chapter, we mainly study the problem of disjoint weight circles in t

6、he standard multiple bipartite graphs: let be a standard multiple bipartite graph with, where is a positive integer, we verified that if , then when the is odd, ; When the is an even number, , with a exception. And we also raises a further problem to be discussed. The third chapter mainly proves: le

7、t is a bipartite graph with , where is the positive integer. If, then contains at least one chorded cycle. As a promotion, we also proved that be a bipartite graph with 3kleq , where is the positive integer. If , then contains independent chorded cycles.Keywords：bipartite graph;degree condition; cho

8、rd cycles; vertex-disjoi3宁夏大学硕士学位论文 主要符号对照表 目录主要符号对照表3第一章 引言5第二章 标准多重二部图中点不交的重4圈12第三章 二部图中包含点不交弦圈的边界条件19摘 要28绪论311.1引言311.2 污水的常用处理技术311.3海藻酸钠简介351.4选题依据与研究内容442海藻酸钠/凹凸棒复合凝胶小球对亚甲基蓝的吸附性能研究463海藻酸钠/丝瓜复合材料对亚甲基蓝的吸附性能研究554海藻酸钠/琼脂/凹凸棒复合气凝胶对亚甲基蓝的吸附性能研究60摘 要66Abstract691 绪论712 凹凸棒/埃洛石/海泡石/纤维素基复合膜的制备及性能研究843

9、改性凹凸棒/海泡石的制备及性能研究904 改性一维粘土对高分子复合膜的增强效果945 结论与展望104主要符号对照表 顶点集为边集为的图 部集为和边集为的二部图 顶点集为边集为的多重图 顶点集为边集为的有向图 图的顶点集 图的边集 图的最小度 图的最大度 在图中的入度 在图中的出度 在图中的度 在图中的邻点集 在图中的邻点集 在图中的度数 由导出的的子图 由导出的点导出子图 长为的路 长为的圈 与的并集 与的交集 包含 与同构5宁夏大学硕士学位论文 第一章 引言 第一章 引言 在本章节中,在本章节中, 我们主要介绍了本文所涉及的一些基本概念和简单术语, 分为四小节内容, 具体为：第一节介绍了和

10、本文相关的一些概念和术语; 第二节介绍了本文的研究背景;第三节介绍了本文所涉及的一些已有的相关结果; 第四节介绍了本文所探讨的问题.1.1 基本概念和术语首先介绍本文所涉及的一些基本概念和简单术语,文中未给出的术语参考文献1. 一个无环无重边的无向有限图称为简单图, 一般用来表示. 其中表示图的阶数(也称大小), 表示图的边数. 给定图的集合, 如果该集合中任意两个图没有公共的交点,那么则称该图的集合是点不交的. 为了书写方便, 令表示中与相邻的顶点构成的集合, 表示中与相关联的边的条数或者称为在中的度, 则. 特别地, 如果, 则表示中由点集导出的子图, 如果不影响意思表达, 我们常用代替,

11、 对于的子图, 我们常常用来代替. 设表示正整数, 长度为的圈简称为圈. 设为中的圈, 我们用表示的圈长.设表示一个有向图, 图的顶点集用表示, 表示图的弧集, 当且仅当图中从顶点指向顶点的弧最多只有一条, 相对应的, 顶点和顶点在中相关联, 当且仅当或者, 则表示由导出的关于的子图, 其中. 如果表示在中弧集的个数, 则令, 则对于任意的, 表示对任意的, 与连接;表示对任意的, ; 表示对任意的, . 于是, 对于任意的, 令表示中的度数, 则, , 的最小度. 显然, 将中所有弧的方向抹掉可得到对应多重图.,令表示在中连接顶点和顶点之间的弧的个数, 则有当且仅当或者. 特别的, 如果且,

12、 则, 且. 不属于当且仅当.在这里, 如果, 则多重图称为标准多重图. 所以, 如果是的重边, 则或者; 如果是的单边, 则. 在中顶点的度数, 的最小度.令表示一个四边形, 多重图是指一个四边形中至多包含条重边, 如且, . 则定义表示包含个点不交的四边形. 令是的一个子图, 表示中顶点和之间弧的个数, 此时用代替; 对任意的子集, 表示中和之间弧的个数, 用代替. 特别地, 如果的子图中所有的边都是重边,则称的子图是重子图.在本文中涉及了图论中一些基本的定义:一个无向简单图, 如果存在和, 使得, , 且的每条边由中的一个顶点和中的一个顶点连接构成的, 我们称这样的图为二部图, 也叫二分

13、图,记为. 如果二部图的顶点集非空,且对, 都有, 则称为标准多重二部图, 一般情况下用来表示. 特别地, 对于一个二部图, 其中, 则称这个二部图有一个部集.连接圈上的任意两个顶点之间的一条边, 使得这条边不属于圈上的一条线段叫做弦. 如果一个圈至少有一条弦, 则称这个圈为弦圈.如果是中的一个圈, 令表示的长度, 所以, 长度为4的圈叫做四边形, 长度为6的圈叫做六边形.表示在中沿着的方向从到的路. 从而表示圈的反向, 且, , . 对于中的圈, 令, 则表示图. 除了以上的一些基本定义和简单术语外, 为了便于论述, 在后面的章节会给出一些特殊的概念和符号, 有可能会重复. 1.2 问题的研

14、究背景 图论的研究最早开始于大约275年前, 它的演变经历了悠久的历史. 我们通常用点表示事物对象, 两点之间的连线表示事物对象之间的某种特殊关联. 它的应用早已渗透到自然社会和社会科学的各个方面中, 如：军事、电讯、物理、科学、生产、化学等方面. 它大体分为三个阶段:第一阶段:1736年-19世纪中叶. 1736年, 欧拉(L.Euler) 解决了著名的哥尼斯堡城七桥问题, 第一篇图论论文出世, 因此欧拉被称为图论之父. 随后在1750年, 他还发现了多面体欧拉公式:其中, 表示面数, 表示顶点数, 表示棱数.这个定理被称为拓扑学的第一个定理, 促进了拓扑学的发展, 由此图论及拓扑学问世,

15、这一时期的图论处于萌芽阶段.第二阶段:19世纪中叶-1936年. 这一阶段, 出现了大量的图论问题,许多学者以图为基础工具研究了关于迷宫问题、棋盘上马行走路线问题、树的概念及其应用等, 其中最为代表的是1852年, 费南西斯.古色利(F.Guthrie) 研究的 四色猜想, 它是近代世界三大数学难题之一. 第三阶段:1936年至今.1936年, 匈牙利的伟大数学家哥尼格发表了著作:有限图与无限图的理论, 标志着图论成为了一门独立的学科. 与此同时, 1946年, 第一台计算机的发明成功, 伴随着交通、科技、生产、管理、信息、通讯、军事等的快速发展, 促进网络的快速飞跃, 使得更多的离散和组合问

16、题出现, 进一步扩大了线性规划、运筹学、组合学、离散数学、拓扑学等学科的发展, 图论及其应用的研究突飞猛进, 从而使图论的研究发展更加广泛, 已渗透到生物医学、人工智能、网络通讯、 电路、工业生产、企业管理等领域. 在进入二十一世纪以来, 在人工智能技术、大数据的极力影响下, 图论已经成为人们解决实际问题必不可少的数学工具之一.在图论的研究中, 路和圈是分析图论的基本工具, 所以许多实际问题都可以归类为图中路和圈的问题, 所以, 人们不仅对简单图、无向图、有向图中点不交的圈感兴趣, 而且也开始考虑有度条件或边界条件限制的二部图中路和圈问题. 因此本文研究点不交圈及弦圈的结构是非常有必要的.本文

17、主要考虑的问题是利用度条件或边界条件作为限制条件来研究标准多重二部图中的4圈和一般二部图中点不交的弦圈问题, 下面我们将介绍关于点不交圈的一些已有的结论.1.3 已有的结论对于一般图中点不交的子图的存在性, 1963年,Corradi和Hajnal给出了一般图中存在个点不交圈的边界条件.定理1.3.1. 2令是一个阶数至少为的简单图, 为正整数, 如果, 则包含个点不交的圈.在上述定理中, 特别地, 当的阶数恰好为时, 则包含个点不交的三角形.随后, 1970年, Hajnal 和Szemeredi又进一步研究证明了一般包含个点不交的圈.的边界条件:定理1.3.2. 3令,为正整数, , 如果

18、的阶数为, 使得, 则包含个阶数为的点不交完全子图. Enomoto(1998) 4和Wang(1999) 5以图的阶数和图中任意两个不相邻顶点的边界条件研究了图中点不交的圈的结构.定理1.3.3. 令 为正整数，是一个阶数至少为的图, 假设对于中任意一对不相邻顶点和, 有, 则包含个点不交的圈.1990年, ErdHos和Faudree提出了一个猜想.猜想1.3.4. 6令为正整数, 是一个阶数为的图, 假设, 则包含个点不交的4圈.2010年, Wang 7完美的证明了ErdHos-Faudree猜想, 紧接着, 2012年, Wang 8证明了当时, 猜想1.3.4依然是成立的. 同时,

19、 Wang 9研究证明了中同时包含点不交的3圈和4圈的边界条件.定理1.3.5. 9设是一个阶数为的图, 其中都为正整数, 且. 如果, 则包含个点不交的圈, 其包含个3圈, 个4圈.类似地, 在有向图、多重图及二部图中, 许多学者也得到了非常有意义的结果.首先, 我们介绍一类特殊的多重二部图：设表示完全二部有向图, 其中, 则对于任意的和,都有且.对于任意的正整数, 我们设和为两个点不交的有向二部图, 使得. 则由以及所有形如和的弧构成, 其中, , 以及. 因此,抹掉中每条弧的方向, 把得到的标准多重二部图记为. 首先, Wang10在提出了如下猜测:猜想1.3.6.10 设是正整数,是有

20、向二部图, 满足.且对, 有. 若表示有向二部图, 其中, 且, 则包含同构于的子图, 除非是偶数时,.显然, 上述猜想中的是由一系列点不交的有向圈和路构成. Wang1011证明了当最多包含两个分支时猜想成立. Zhang和Wang12证明了的每个分支是圈时,猜想成立. 最近, 高云澍和Wang等人13完整的解决了猜想.类似地, 在一般有向图中, Wang14最近证明了如下的定理：定理1.3.7. 14 设为正整数,为阶数的有向图, 使得对于任意不相同的两个点, 满足, 则对于任意给定的个不小于的整数 假设, 则包含个长度分别为的有向圈, 除非同构于三种已知结构的有向图.定理证明了Wang在

21、文献15中提出的猜想.2014年, Czygrinow和Kierstead等人16率先研究了标准多重图中点不交的重边三角形, 从而推广了Wang17关于点不交有向三角形的结果. 后来, 高云澍等人18研究了标准多重图中独立重四边形的存在性, 从而推广了Zhang和Wang19关于点不交有向四边形的结果.定理1.3.8. 19 令是一个阶数为的有向图, 是正整数, 假设的最小度至少是, 则包含个点不交的有向四边形, 除非同构于一类已知结构的图.定理1.3.9. 18 令是一个阶数为的标准多重图, 是正整数, 假设的最小度至少是, 则包含个点不交的, 除非同构于两类已知结构的图中的一类.如果对于给

22、定有向二部图, 使得, 其中是正整数. 我们把中每条弧的箭头抹掉, 我们把得到的标准多重二部图记为. 显然, . 另外, 若为中长度为的圈, 使得中至少条边为重边, 则显然, 对应的有向图中有长度为的有向圈. 因此, 研究标准多重二部图中的点不交定长重边圈是有向二部图中点不交定长圈的推广. 沿着这条线及第二章的结论, 下面的推论是显然的.推论1.3.10. 令是一个标准多重二部图,是正整数. 若的最小度至少为, 则, 除非当为偶数时, . 对于一般二部图, Wang20已经证明了下面两个定理:定理1.3.11. 20令为正整数, 是一个二部图, 满足, 其中是正整数. 若, 则包含个点不交的圈

23、.定理1.3.12. 20 令是一个二部图, 使得, 是正整数, 若的最小度至少是, 则包含个点不交的四边形和一条阶的路, 使得路和圈是点不交的.事实上, Wang20猜想和定理1.3.6同样的结论: 假设. 一般情况下, Wang20提出了以下猜想:猜想1.3.13. 20 令 ,是正整数, 是一个二部图, 满足, , . 假设, 则包含个点不交的子图同构.如果猜想1.3.13成立, 则猜想1.3.13是Hajnal 和 Szemeredis定理中二部图的形式. Wang证明了猜想1.3.13中的情况20,21. 另一方面, Wang21证明了猜想1.3.13中的情况. 并且,文献20中给出

24、了猜想1.3.13中的情况.定理1.3.14. 21 令是正整数，是一个二部图, 满足 . 假设, 则包含个点不交的六边形, 使得每个六边形至少有两条弦.如果一个圈上至少含有一条弦, 我们称这个圈为弦圈. 一个长度为6的圈叫做六边形. 近年来, 学者们不仅对图中包含点不交路和圈的研究感兴趣, 而且也对图中包含点不交弦圈做了进一步的研究.在文献23中, 高云澍等人考虑了二部图中包含点不交双弦圈的存在性, 从而推广了定理1.3.14. 也被看作是由P. Balister, H. Li和R. Schelp24证明的二部图中对应的相应结果.定理1.3.15. 23 令是正整数，是一个二部图, 满足 .

25、 假设, 则包含个点不交的六边形, 使得每个六边形至少有两条弦.基于Corradi a和 Hajnal的定理1.3.1.的研究, Andreae 和 Justesen2425发现了关于图包含个独立圈的边界条件. 沿着此路线, Wang24研究了二部图包含个点不交圈的边界条件, 但是Wang的证明与定理1.3.11和1.3.12完全不同.定理1.3.16.23 令是正整数,是一个二部图, 满足, . 假设,则包含个点不交的圈, 除非属于已知的一类图.令是一个确保两个点不交弦圈最少边数的阶图. Bialostocki 等人27得到了下面的定理.定理1.3.17. 27 任意一个阶数且大小至少为的图

26、包含两个点不交的弦圈, 其中 一个图是内部三个不相交的含有相同的不同端点的路的联合. 一个弦圈是一个图的简单例子, 显然, 一个图不是一个弦圈. 在Bialostocki等人27 的研究结果, 高云澍等人28 研究了对于两个点不交的图存在的极值.定理1.3.18. 28 阶数且大小至少为的图包含两个点不交的图, 其中根据以上的结果, 对于正整数, 如果, 这就意味着包含个点不交的弦圈, 特别得, 当时, 我们记. 据我们所知, 对于二部图中具有点不交弦圈的结果不多. 关于其它点不交圈和点不交弦圈的结果, 我们推荐读者阅读本文列举的文献29-58以及更多的参考文献.1.4本文的研究内容根据以上已

27、有的结果, 特别是Wang14在一般有向图中的猜想以及Wang在文献26中的结论,在本文第二章以度条件和图的阶数作为限制条件研究了标准多重二部图中点不交的重4圈. 在第三章我们考虑了二部图包含点不交的弦圈的边界条件, 主要证明了以下三个定理. 定理1.4.1 令标准多重二部图, 满足, 是正整数, 若的最小度至少为, 则当为奇数时, ; 当为偶数时, , 除非. 定理1.4.2 设为正整数, 是一个二部图, 满足, , 则包含至少一个弦圈. 定理1.4.3 设为正整数, 是一个二部图, 满足, , 则包含个点不交的弦圈.13宁夏大学硕士学位论文 第三章 二部图中包含点不交弦圈的边界条件第二章

28、标准多重二部图中点不交的重4圈本章无具体说明, 均指的是简单无向有限图. 本章共有四节内容: 第一二节介绍了一些相关的概念定义和主要引理; 第三四节给出了定理1.4.1的证明和一个可进一步探讨的问题.2.1 基本概念及术语令表示一个简单图, 用,分别表示图的阶数和大小. 特别地, 对任意的, 我们常用表示顶点在中的度数或者在中与顶点相关联的边的数目. 如果表示的任意一个子图, 或者中存在同构于的子图, 则有包含,一般用来表示.令表示多重图. 对于, 表示在中连接和的边的数目,如果, 则令. 定义. 顶点在中的度定义为且的最小度. 我们称阶数为的多重图为四边形, 其中包含四边形且. 类似的, 称

29、阶多重图为四边形, 其中包含四边形且. 我们常常用描述包含个点不交的的集合, 则表示包含个点不交的四边形.令表示一个有向图, 显然, 如果将中所有弧上的箭头抹掉之后可以得到对应多重图. 对于任意的, 我们用表示在中的度, 且和分别表示的最大出度和最大入度. 设表示的两个点集或者两个子图, 我们用表示端点分别位于和中的边集合且. 如果且, 则,同时. 如果,则包含一个顶点集合相同的有向四边形. 如果,则称为标准的.对于一个确定的标准多重图, 文献16定义了两种简单图:和,其中和.若, 称则为重边; 若, 则称为单边.2.2 主要引理设是一个简单二部图.引理2.2.1 20 令是中的一个圈,是在上

30、且不在上的一个顶点, 假设, 则要么是一个四边形, 要么包含一个圈, 使得.引理2.2.2 20 令是中的圈, 是中的圈, 且与是点不交的. 如果, 则包含两个点不交的圈.引理2.2.3 20 令和是两个正整数, , , 令和是中长度分别为和的两个圈. 假设, 则包含两个点不交的圈和, 使得.引理2.2.4 20 令是的一个圈, , 是在上且不在上的两个顶点. 假设, 则存在, 使得要么是一个四边形且, 要么是一个四边形且.引理2.2.5 令和是的子图, 其中，是的一个圈, 假设包含两条不交的重边, 且 , 如果满足, 则.证明：反证法, 设, , 其中. , 且和是重边. 由于, 因此 .根

31、据对称性, 设, , 则, 因此.如果, 则, 因此, 这就意味着, 从而, 与已知矛盾. 所以, 这就意味着, 从而, 与已知矛盾.2.3 主要定理1.4.1的证明在下面的证明中, 对于给定的标准多重图, 我们总会考虑其对应的重边导出子图, 为了表示方便我们总是记. 为了便于理解, 我们给出一些其它的术语. 给定多重二部图, 对任意的以及的子图, 表示在中的邻集. 设和为中的任意两个子图或者两个点集, 表示中导出的子图, 定义 我们通过反证法证明. 假设奇数时, 设, 假设, 因为, 所以, 对任意的, 即, 由定理知, 包含个不交的圈, 且其中一个是阶的, 其余都是圈.令是在中个不交的圈,

32、 使得. 我们选择, 使得 尽可能小. 因此, 并且, 令, 由选择可知, 所以 .如果这儿存在, 使得, 则在中, . 由引理可知, , 矛盾. 所以我们可以假设存在, 使得, 因此, . 根据选择可得, , . 由可知由选择和引理, , 因此并且, 以上两个公式全部取等号, 则对, 都有, 且, . 所以, 矛盾.假设为偶数, 设, 假设不包含, 我们将证明. 因为, 所以 由定理可知, 包含个不交的圈. 当时, 显然,. 因此, 令是中点不交的个圈, 我们选择使得 尽可能小. 令. 因此, , . 我们分为以下4种情况:情况1 根据选择得, , 由选择和引理, 对对, 都有, 从而. 由

33、式可知, 所以对, 都有, 且对于任意的, 同理, 对任意的, 即对任意的, 在中都存在邻点. 令,.情况1.1, 其中, 子情况1.1.1 连接中相邻的两点.不失一般性, 根据对称性, 不防假设, 因此, ,矛盾.子情况1.1.2 连接中不相邻的两点.不失一般性, 根据对称性, 不防设, 如果, 使, 不妨设, , , 与选择矛盾. 因此中不相邻的两点, 即或. 假设, 则, 此时, , , 矛盾. 同理, 都有, 矛盾.情况1.2 , 使得.不失一般性, 根据对称性, 不妨设. 我们断言对, 都有, 否则, 不防设, 则, , , 矛盾. 断言成立. 因此, 这是因为. 我们分为以下两种情

34、况:子情况1.1.2, 都有, 其中.不失一般性, 根据对称性, 不妨假设且, 则, , 从而, 与选择矛盾.子情况1.2.2, 都有, 其中.不失一般性, 不妨设, 我们断言, 都有. 否则, 由对称性, 不妨设, 令, 因此, 对个圈进行如下分解: 令 且 显然, 对, 由于, 因为, , 因此, 所以对由于, 我们考虑顶点的度数 由式乘以得：, 与矛盾. 断言成立.所以对, 有. 根据对称性, 不妨设, , 此时, 因此, 与选择矛盾.情况2 根据选择得, , 由选择可知,由选择和引理, 对, 都有, 从而并且, 以上两个公式全部取等号, 则对, 都有, 且对任意的都成立. 即在中的任意

35、顶点, 在中都存在邻点.令，其中，则， , 矛盾.情况3 且.我们进一步选取, 使得是最大的. 令, , , 其中.我们断言. 反证法, 假设, 即, 由选择和引理, , , 所以因此存在属于, 使得, 根据引理,包含一个圈和一条阶为的路, 且它们是点不交的, 与的最大性矛盾. 所以.由选择和引理, , 因此, , 则. 根据选择, . 我们断言. 如果存在, 使得. 根据对称性, 不妨设, , 由于, 则或者, 或者, 矛盾. 因此, ,. 因此,这就意味着存在, 使得, 由引理, , , 所以, . 又因为对, , 则由选择和引理, , 且对, 都有, 于是, 则, 矛盾.情况4 .对,

36、令, , 我们选择, 使得中所含独立重边的数目是最多的.我们断言包含了两条点不交的独立重边. 我们先证中包含一条重边, 假设不存在, 则对任意的, , 有. 于是这就意味着存在, , 使得, 即. 根据引理,包含一个重边圈和一条重边, 且它们是点不交的, 用代替, 显然可以看出中包含一条重边, 矛盾. 我们记, 使得且. 下证包含了两条点不交的独立重边. 否则, 假设中恰好包含了一条独立重边, 我们知道对任意的, 都有, 即. 所以,. 又因为, 因此, 这说明, , 与所选择的中所含独立重边的数目是最多的矛盾. 断言成立. 所以,包含两条点不交的独立重边, 令为, , 其中.我们断言, 否则

37、, 如果, 则有,矛盾. 所以, 则有所以存在, 使得. 根据引理, . 矛盾. 断言成立.对, 令, 其中, 因为, 所以如果时,; 如果时,. 所以, , 因此但是于是, 以上三个公式全部取等号, 即对, 都有, 所以, , . 因此, 要么, ,或,; 要么, , 或, .我们断言. 否则, 令, 由于, 则在中与不相邻. 由式可知,.所以存在, 使得. 不妨假设, , 则在中与不相邻. 否则, , 矛盾. 所以,. 则, , , 矛盾, 断言成立. 所以, 从而.因此, 若, 则. 我们用可以代替中的, 此时, 由上面断言可得. 同理, 如果, , 则, 此时, ,矛盾. 因此, ,

38、即 , 且, 因此, 即, 且, .如果, 则有, . 同理, 如果, 则, . 此时, , 矛盾. 因此, 则, , 且, 所以, , 且，.综上所述, 对于每一个, 其中, 且, 满足(i) 是重子图, , 且; (ii)是重子图, , 且;构造如下的两个图：则由于, 从而. 所以, 当为偶数时, .2.4可进一步讨论的问题最后, 我们列出一个没有解决的问题作为本章的结尾:猜想2.4.1 令是一个标准多重二部图,是正整数. 若的最小度至少为, 则, 除非当为偶数时, .第三章 二部图中包含点不交弦圈的边界条件本章我们主要讨论的是以边界为限制条件来研究点不交弦圈的问题. 如果无具体说明, 本

39、章中的图均指简单有限无向图. 本章共分为三节: 第一节介绍了一些概念和定义; 第二三节介绍了主要的引理及其定理的证明.3.1预备知识 对于一个简单图,我们常常用、分别表示图的阶数和大小(或者称为边数)，和分别表示图的最小度和最大度.如果一个圈至少有一条弦, 那么称这个圈为弦圈.一个图是内部三个不相交的路径的并集, 使得它们有相同的两个不同的端点. 而一个弦圈是一个图的简单例子, 但是, 实际上, 一个图并不一定是一个弦圈.对于一个二部图. 特别地, 如果其中, 则称这个二部图有一个部集.如果是的一个子集或的一个子图. 对于一个顶点, 表示中的邻集. 令, 则表示在中顶点的度数, 或者表示在中的

40、邻集的个数, 或者表示在中与相关联的边集的数目. 如果是的一个子集或的一个子图或中一系列不同的顶点, 则令.如果是的子集或的子图或中一系列不同的顶点, 我们用来表示由诱导出的关于的一个子图.中的圈, 令是圈的长度, 给定一个方向, 表示与圈相反的方向. 对于, 假设表示在中沿着的方向从顶点到顶点的路. 那么我们用, , . 对于中的圈, 假设, 则表示图.3.2 主要引理 令是一个二部图, 且.引理3.2.1 令是的一个弦圈, 是在中且不属于中的一个顶点, 假设, 则要么是一个弦圈, 要么包含一个弦圈, 使得.引理3.2.2 22 令是中阶数至少为的一个弦圈, 且满足则包含一个阶数至少为的弦圈

41、.引理3.2.3 令和是两个整数, 其中 . 和是中两个点不交的弦圈,使得, . 假设那么以下两种说法之一成立:包含一个点不交的弦圈, 且;包含两个点不交的弦圈和, 使得.证明：反证法, 假设和都不成立. 令, , 其中.不失一般性, 假设对, 明显地, , .我们断言 . 否则, 假设, 且对任意的, 都有. 我们不妨设, ,且. 由于不包含一个圈, 使得, 此时很容易可以得到对任意的, 都有. . 明显地, .而且, 我们可以看到当且仅当. 否则,中包含了一个阶数小于的阶数点不交的圈, 且中包含了一个点不交的六边形, 与矛盾. 类似地, 对任意的, 都有当且仅当. 因此矛盾. 即得证.根据式得, 对, 令. 由于,假设包含一个弦圈. 因为, 所以是的一个子路, 其中. 令, 明显地, 否则, 由式可得, ,矛盾. 此外, 由于, 从而得到, 与矛盾. 令, 则.由于对. 根据鸽笼原理, 可以在中找到七条边, 令, 使得. 且对, 都有的两个端点位于的不同部集中. 我们