【摘 要】
:
作为匹配和拟阵交的共同推广,Cunningham和Geelen在1996年引入了图的路匹配的概念.他们指出许多领域的问题都可以转化为路匹配问题,也就是说,利用路匹配可以解决例如匹配、拟阵、多面体以及代数等很多方面的问题.作为路匹配的应用,他们给出了可匹配集合多面体的强多项式分离算法,并证明了最大路匹配的值就等于给定图所确定的匹配拟阵中顶点集合的秩,同时也等于Tutte矩阵的秩等等.本文共分为六章,
论文部分内容阅读
作为匹配和拟阵交的共同推广,Cunningham和Geelen在1996年引入了图的路匹配的概念.他们指出许多领域的问题都可以转化为路匹配问题,也就是说,利用路匹配可以解决例如匹配、拟阵、多面体以及代数等很多方面的问题.作为路匹配的应用,他们给出了可匹配集合多面体的强多项式分离算法,并证明了最大路匹配的值就等于给定图所确定的匹配拟阵中顶点集合的秩,同时也等于Tutte矩阵的秩等等.本文共分为六章,第一章着重介绍了路匹配的应用背景以及路匹配自引入以来的主要研究成果,并且在此基础上概述了本文得到的主要结论.第二章和第三章主要是通过最大路匹配来刻画图的结构,在最后的三章中我们考虑了给定图的最大路匹配的大小以及完美路匹配的可扩性等问题.在2004年,Spille和Szego给出了与通常匹配意义下的Gallai-Edmonds分解{A,C,D}类似的一种顶点分解{A1,C1,D1},并且给出了相应的结构定理.我们已经知道集合A就等于图中所有极大障碍集合的交集.在第二章中,我们将这一著名结果推广到了路匹配的框架中,从而得到了关于A1的一个表达式.在Gallai-Edmonds结构定理中,由D所导出的图的每个分支都是因子临界的(即删去任意一点后都有完美匹配).对于这类图的刻画在匹配理论中已经得到了.而路匹配分解中的D1所导出的图不一定是因子临界的.因此,在第三章中我们刻画了由D1所导出的图,并且讨论了D1所导出的图中两类分支之间的内在关系.Frank和Szego给出了一般图中有完美路匹配的一个刻画,事实上这个结果是Tutte定理的一个直接推广.但是从这个结果中得到的一个图有完美路匹配的充分条件却非常强,很难满足.因此,在第四章中我们集中考虑了完美路匹配在一般图以及一些特殊图类中存在的条件.对于一般图给出了极集合条件和联接数型条件,并且更进一步地证明了这些联接数型条件在某种意义下是最好的.对于特殊图,我们考虑了正则图和以t+1个顶点的星作为禁止子图的无K1,t图,得到了在这两类图中存在完美路匹配的条件.一个图G=(V,T1,T2;E)的路匹配数val(G)是描述G中最大路匹配大小的一个参数.在第五章中,我们用两种不同的方式给出了val(G)的界.第一个界是用关于联接数b,|V|,和|Ti|的一个函数给出来的,这里i=1,2.并且从这个结果可以得到Woodall关于图的最大匹配所含边数的界.第二个界所考虑的是无K1,t图,我们用关于t,连通度m,|V|,和|Ti|的某个函数给出了val(G)的界.在第四章中,我们已经讨论了一个图有完美路匹配的充分条件.那么如果我们加强这些条件是否就能够使得任意一个值为n的正常路匹配都可以通过某种扩张成为完美路匹配呢?在本文的最后一章中,我们给出了关于路匹配n-可扩的定义,这种定义从本质上讲是匹配可扩的一个推广.我们得到了一个图在顶点数|V|和n+k有相同的奇偶性,或k>n时n-可扩的联接数型充分条件(这里k是图G中端集合的大小),并且说明了这些充分条件在某种意义下是最好的.由此产生的一个推论将Chen关于匹配可扩性中的结果改进到了最好.那么在|V|和n+k奇偶性不同,并且k≤n时,我们说明了在这种情况下图的可扩性与联接数是没有直接关系的.最后我们给出了无K1,t图n-可扩的充分条件.
其他文献
多面体链环是由多个环相互嵌套成的具有多面体形状的一种拓扑几何结构。多面体链环的研究为表征、描述DNA和蛋白质链环提供了新思路,同时也为分子设计提供了可能的理论模型。化学和生物体系中的大分子结构较复杂,如何表征和刻画环状富勒烯、碳纳米管、DNA和蛋白质这些大分子是我们面临的机遇和挑战。本论文基于多面体链环的研究,构筑并应用纽结理论的知识分析和讨论了新的环状富勒烯链环、碳纳米管链环、病毒多面体链环模型
空间生态学和性生态学都是当前理论生态学和数学生态学研究的重要领域。性生态学和空间生态的结合乃是当今研究的前沿和热点。因为大多研究空间生态学忽略了有性生殖,而有性生殖的研究又没考虑空间因素。偶对近似和矩方法是近几年发展起来了的先进空间分析方法。它们是通过空间相关性来反映种群空间分布的两种近似随机空间模型。其优点是可以系统地进行数学分析处理,克服了空间模拟耗时和随机性带来的缺陷。本论文选题正是利用偶对
本研究首次以生长于乌鲁木齐河源区高海拔、强辐射、温度波动大的极端环境下的地衣为研究对象,通过对该地区地衣种类统计、生活型分析、区系比较、不同海拔的地理分布以及分子进化的研究,得到以下几点结论:1.该地区地衣分布有35种,隶属于14属,10科,其中,中国新记录种1种,即Rhizoplaca haydenii,揭示了极端环境下地衣分布数量较之其他地区较少,作为“先锋植物”的地衣,在高海拔、强辐射、温度
双非线性抛物型方程在金属材料合成中有着重要的应用价值,但人们对其解的形态以及动力学行为了解甚少.在这篇博士学位论文中考虑如下形式的双非线性抛物型方程:其中α和f是任意次多项式增长的非线性函数,Ω是RN中的有界光滑区域.由于非线性项α的存在,给该问题的研究带来了很大的困难.首先,我们采用Faedo-Galerkin逼近方法,对更一般形式的双非线性P-Laplacian方程,证明了解的存在性.其次,利
低温环境是一个独特的生态系统,它被认为是天然的“菌种保藏中心”。近年来冷环境下微生物的研究取得了长足的发展,尤其是微生物生态学的研究。天山地区具有寒冷、中纬度和高海拔等特点,是研究低温微生物的理想生境。本文选取了天山2米深的雪坑、1.6米深的活动层冻土和3.0米深的永冻土作为材料,应用PCR-DGGE技术研究了其中微生物的群落结构和分布,分析和讨论了它们之间的关系及其与温室气体(CH4和N2O)排
本工作采用能量为190keV-450keV的不同价态的Arq+(q=15~18)离子轰击原子序数Z=4~79的金属靶,对Ar离子的X射线发射机制进行研究。文中依次对Ar17+离子,Ar16+离子,Ar18+离子和Ar15+离子进行了分析。主要的实验工作及结论如下:对Ar17+离子的K壳层X射线分支比进行分析,研究了Kβ/Kα分支比随电荷态与能量的变化规律以及Kα和Kβ射线的平均能量。在级联跃迁模型
本工作利用兰州大学2×1.7MV串列加速器产生的能量为17.9-120 keV/amu的C1+、30-323keV/amu的C2+、71.7-438 keV/amu的C3+、287-480 keWamu的C4+、15.9-80.4 keV/amu的O1+、30-254 keV/amu的O2+及63.5-321.6 keV/amu的O3+与惰性气体原子He、Ne、Ar进行碰撞,对碰撞中的转移电离过程
本文以单调动力系统(monotone systems)为研究对象,在放松K-型序下的拟单调条件限制的同时考虑了斜积半流的动力学行为.分为自治和非自治动力系统两部分.在自治动力系统(autonomous systems)方面,已有的拟单调条件在许多应用中不能满足.一个典型的例子就是在神经元之间具有抑制和刺激的联络时的时滞Hopfield-型神经网络模型.受此启发,我们引入了弱拟单调条件(WQM),建
在这篇博士学位论文中,我们主要考虑非自治无穷维动力系统的拉回吸引子的存在性问题,针对拉回吸引子存在的关键性条件——(?)-拉回渐近紧的验证,提出了两种有效的验证方法,并将这两种方法应用到具体的非自治的无穷维动力系统中,得到了一系列新的深刻的结果.全文共分五章:第一章,介绍无穷维动力系统的背景,拉回吸引子的发展及研究进展情况,详细介绍了本文所讨论的主要问题和研究思想.第二章,给出了本文用到的一些基础
由于兼具毛细管电泳(CE)超高分离效率和激光诱导荧光检测(LIF)超高灵敏度的优势,CE-LIF联用技术已经成为测定多组分化合物的一种有力工具,在药物及生命分析等领域得到了广泛的应用。但是,很多化合物本身并没有荧光,即使有些化合物自身具有荧光,其激发波长和所用激光光源波长的不一致也会限制CE-LIF方法的应用。为了克服这一缺点,分析工作者通常采用衍生反应修饰分析物,使之转变成具有适合光学性质的衍生