【摘 要】
：
假设M是图G的一个完美匹配,M（G）是图G所有完美匹配的集合.图的完美匹配计数问题（即计算.M（G）的基数）是图论的一个重要研究课题.然而,Valiant证明了图的完美匹配计数问题是#P-完全的.但是,如果图G是一个Pfaffian图,那么就能在多项式时间内算出|M（G）|的大小（及其相关问题）.图G被称为是一个Pfaffian图如果图G存在一个Pfaffian定向,即图G存在一个定向G使得图G的
论文部分内容阅读
假设M是图G的一个完美匹配,M（G）是图G所有完美匹配的集合.图的完美匹配计数问题（即计算.M（G）的基数）是图论的一个重要研究课题.然而,Valiant证明了图的完美匹配计数问题是#P-完全的.但是,如果图G是一个Pfaffian图,那么就能在多项式时间内算出|M（G）|的大小（及其相关问题）.图G被称为是一个Pfaffian图如果图G存在一个Pfaffian定向,即图G存在一个定向G使得图G的每一个M-交错圈都有奇数条边的定向与圈的绕行方向一致.Kasteleyn证明了所有平面图都是Pfaffian的.而对于非平面图的Pfaffian性的判定则复杂许多.1975年,Little得到了关于二部图的一个非常漂亮的 Pfaffian 结构刻画.Robertson,Seymour 和 Thomas 设计了 一 个能在O（n3）时间内判定一个二部图是否是Pfaffian图的算法.但对于一般图,至今还没有多项式算法,即使是其多项式算法的存在性也仍未确定.本文研究了一些图类的Pfaffian性质及其在图的完美匹配计数问题上的应用.全文共分为五章.在第一章,我们首先给出了本论文所涉及的基本概念,术语和有关记号,其次介绍了图的Pfaffian性的研究背景、概况及相关问题,最后介绍了本文得到的主要结果.在第二章,我们刻画了具有最大度大于等于|V（G）|/2-1的匹配覆盖二部图的Pfaffian性,并找到了一个能在O（|E（G）|2）时间内判定其Pfaffian性的算法.而且若图G是Pfaffian的,这个算法能直接构造出图G的一个Pfaffian定向.改进了已知的结果.在第三章,我们得到了能嵌入在torus曲面上的Pfaffian图的一个充分条件.利用这个结论,我们刻画几类有趣的网格图的Pfaffian性.改进了已知的结果.在第四章,我们给出了能嵌入在torus曲面上的两类网格图（8.6.4网格和8.8.4网格）的完美匹配数的显示表达式.而且,我们也得到了它们的熵.在第五章,我们给出了 一类能嵌入在Klein瓶和Mobius带上的六角系统的完美匹配数的显示表达式.
其他文献
南中国海（以下简称南海）,系西太平洋最大的边缘海之一。吕宋海峡是南海和西太平洋水体交换的唯一深层通道,水交换结构复杂,其水文动力学过程亦十分关键,可能对区域性气候变化等重要过程产生关键影响。氟氯烃（CFCs）和六氟化硫（SF6）,因其具有生物、化学惰性,遂成为一类优秀的海洋瞬态示踪剂（Marinetransienttracers）,已被广泛应用于若干海洋学过程研究。本研究开发了大洋水体中CFC-1
IRGs 蛋白（Immunity-related GTPases）是 IFN-γ诱导的免疫相关 GTPase 蛋白,在胞内病原体抵抗上发挥着重要作用。小鼠中有23种IRG基因,进化到人类就只有IRGC和IRGM,而IRGC是人类IRG基因中唯一一个编码全长序列的IRG蛋白。目前,关于IRGC的性质和功能还没有详细的报道和研究,因此从细胞分子层面上研究IRGC可以更好地探索IRG基因在人类中发挥的作
碳化硅拥有高熔点、高耐腐蚀性、高热导率、低热膨胀系数、化学性能稳定,中子吸收截面低,抗辐照性能优异等优点,适合在反应堆堆芯高温高压高通量中子辐照环境中服役。碳化硅被用作TRISO燃料球的包壳材料,聚变堆第一壁候选材料,连接关节部位的结构件等。SiC在核反应堆中的服役环境苛刻,长时间处于高温、高压、高辐照环境中,并且在中子辐照下会产生H、He、P等杂质原子。本论文采用H2+,He+,C+以及Kr+注
血吸虫病是一种严重危害人类健康的人兽共患寄生虫病,全世界范围内有超过2.5亿人感染血吸虫,还有78个国家和地区的将近7.79亿人面临着被感染的危险;据不完全统计每年有超过20万人死于血吸虫病,并造成了巨大的经济损失。湖北钉螺（Oncomelaniahupensis）是日本血吸虫（Schistosomajaponicum）唯一的中间宿主,其在血吸虫病的传播和流行过程当中发挥着不可替代的作用。除此之外
设X,Y是Banach空间,ε≥0,映射f:X→ Y为一个标准的ε-等距.本学位论文主要对Banach空间之间ε-等距的各种稳定性及其相关问题进行研究.我们重点研究了三类ε-等距,分别为对称的ε-等距,子空间N（?）Y*为w*-闭时的ε-等距以及取值于亚自反遗传不可分解空间的ε-等距.我们得到了如下结果.（1）我们率先研究了 ε-等距的对称化,给出了 f的对称化映射θ =f（·）-f（-）/2的弱
复合非线性反馈控制是针对具有输入饱和约束系统跟踪控制问题的控制系统设计技术,其目标是在实现跟踪控制的同时提高闭环系统的瞬态性能,使瞬态性能实现快速响应的同时保持输出超调很小甚至没有超调。当前复合非线性反馈控制方法主要用于解决具有输入饱和约束的线性系统跟踪控制问题,在非线性系统以及多智能体系统的应用还未充分展开。有鉴于此,本文将复合非线性反馈技术框架扩展到几类非线性系统以及多智能体系统。论文主要关注
随着科学技术的发展,特别是计算机、工业、网络等的飞速发展,使得全球商业、医疗、工业、金融和生活娱乐等各领域的数据和信息量呈指数增长。因此,对这些具有不确定性的海量数据进行归纳、总结,科学有效的发现其隐含的有价值的知识,已成为智能信息处理研究中一个极为重要课题。多粒度粗糙集理论作为一种能有效处理不确定问题的粗糙集拓展理论,它利用粒计算和粗糙集理论通过多个粒度空间来近似刻画目标决策,从更精细的角度处理
纽结理论和平图理论可看作特殊的嵌入图理论.上世纪末本世纪初,纽结理论分别拓展到虚拟纽结理论和空间图理论,平图理论拓展到带子图理论.带子图实际上等价于胞腔嵌入图.最近,虚拟纽结理论和空间图理论被统一为虚拟空间图理论.经典纽结理论和虚拟纽结理论的发展促进了带子图理论的发展,例如,提出了部分对偶的概念.本文围绕以上几类嵌入图及其多项式展开研究.本文的主要工作和创新点如下:（1）Huggett和Moffa
大多数真核生物的体细胞是二倍体,仅含有两组染色体,遗传自父本和母本。而一些特定组织如心脏、肝脏等含有多倍体细胞,尤其是肝脏组织含有较高比例的多倍体。肝脏是机体清除毒性代谢物的器官,而毒性代谢物易诱发基因突变,多倍体被认为有利于提供代偿性的正常基因来维持肝脏稳态,但进行增殖分裂将导致异倍体的产生,引起基因组的不稳定性和肿瘤发生发展。故此,对机体调控多倍体细胞的产生以及多倍体细胞进行细胞分裂的调控机理
一致性问题已经成为多智能体系统协调控制中的一个热点也是一个最基本的问题。一致性问题的关键是如何设计合适的用来描述每个智能体及其邻居之间的信息交换过程的协议或算法,从而使得所有多智能达到某个期望的状态。分数阶系统作为整数阶控制系统的扩展,可以提高对实际动态系统的表征、设计以及控制的能力,目前已成为控制领域的一个研究热点。本文基于目前的研究成果,把分数阶微积分模型引入到多智能体系统的一致性控制问题中,