渺位四角系统完美匹配数的排序与正盈量二部图最大匹配数下界的紧性

来源 :厦门大学 | 被引量 : 0次 | 上传用户:liongliong602
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图的完美匹配在量子化学中化学家称之为Kekulé结构,在统计物理上称为Dimmer构形,它们在量子化学与统计物理上有着十分重要的应用。四角系统拥有悠久的历史,早在20世纪处人们就开始研究它。有关数学方面的研究主要集中在拼图问题、非同构计数问题、完美匹配的存在性及匹配计数问题等。至今为止,这方面都已经取得了相当的成果。四角系统是二连通的二部图,其每个内部面都是单位正方形(又称细胞)且每条边至少属于一个细胞。其完美匹配与dimmer问题有直接的联系。存在完美匹配的渺位四角系统的完美匹配数的计算方法是通过其中某一个细胞的一对平行边割的研究而得到的。本文在此基础上定义了构成渺位四角系统的三种四角运算,研究了渺位四角系统的构成,发现任何渺位四角系统均可以看成由若干个锯齿链状四角系统经以上三种四角运算后构成,且任何两个渺位四角系统分别经三种四角运算后得到的三种不同的新渺位四角系统,这三种新渺位四角系统的完美匹配数有确定的大小关系;在这三种四角运算的支持下,最终给出了固定细胞总数情况下具有较少完美匹配数的渺位四角系统的排序。 另一方面,不存在完美匹配的平面图形,我们有最大匹配、极大匹配等有效工具。对二部图的完美匹配的存在性及最大匹配的研究由来已久,且已有不少很好的结论。一个二部图G(A,B)具有正盈量(positivesurplus)(对A而言)当且仅当对A的任何非空集合X所包含的顶点数一定小于其邻集所包含的顶点数;无向简单图G的亏度(deficiency)是未被最大匹配所覆盖的顶点数。本文对具有正盈量的二部图,刻画了其当亏度def(G)给定时达到最大匹配数下界的二部图,当亏度def(G)给定时,其从最大匹配数的下界为|E(G)|+(|A|-1)(def(G)-2),达到此下界的图为A中任何度数≥3的顶点具有def(G)条悬挂边的具有正盈量(对A而言)的连通二部图G(A,B),从而验证了此类二部图最大匹配数下界的紧性。
其他文献
本文主要研究一类混杂系统——线性时不变切换系统的能控的充分必要条件的简化。尽管在稳定性方面的研究结果比较丰富,但由于切换系统的复杂性,能控性方面的结果相对比较少。一
不动点理论是目前正在迅速发展的非线性泛函分析理论的重要组成部分,它与近代数学的许多分支有着紧密的联系.特别是在建立各类方程(其中包括各类线性或非线性的,确定或非确定
在这篇文章中我们考察了带有摩擦效应的波方程的定解问题:此处公式省略与抽象算子的二阶发展方程:此处公式省略对于第一个问题在对g有恰当的假设下,通过构造合适的泛函得到能
超图是离散数学中最具有一般性的结构,是图的自然推广,然而对于图中的一些结论甚至定义并不是都能轻而易举的推广到超图中的,图中的圈比较直观,但推广到超图中时情况就不一样了。
新一轮基础教育课程改革十分重视“生成性教学”,充分重视师生生命活动的多样性和教学环境的复杂性,以学生的发展为本,以文本为教学资源,以动态生成为主旋律,在教师、学生和
矩阵空间保不变问题是矩阵理论中活跃的研究领域。本文研究了不变量是矩阵的广义逆的线性映射保持问题。设F是一个域,M(F)为F上全矩阵代数,f为M(F)上的线性映射。 本文概述
图谱理论是代数图论和组合矩阵论中一个重要的研究领域,在近几十年中发展迅速,并得到广大研究者的关注和青睐.其中,对图的各类矩阵和特征值的研究是图谱理论的主要研究内容和
期刊
汽车后视镜是汽车上一个非常重要的部件,如果后视镜有盲区和图像变形,势必给安全行车带来隐患。研究出一种大视野低失真的后视镜对减少交通事故带来的损失有重要意义,而且现
期刊