二部图中有关点不交子图的研究.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在
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二部 有关 点不交子图 研究
限制150内