关于一些图类的强迫与反强迫多项式的研究

来源 :兰州大学 | 被引量 : 4次 | 上传用户:wind2121
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图G的完美匹配M的强迫数由Klein和Randic与Harary等分别在化学与数学中先后引入,具体定义为M中边的最少条数,使得这些边的集合不包含在G的其它完美匹配里.而M的反强迫数是指不在M中边的最少条数,使得从G中删除这些边之后得到的子图有唯一的完美匹配M.一般地,二部图的完美匹配的强迫数与反强迫数的计算问题都是NP-完全的.研究表明,一个六角系统的最大强迫数等于它的Clar数,而最大反强迫数等于它的Fries数,且Clar数与Fries数都可以用来衡量芳香烃的分子稳定性.在一般图中,每个完美匹配的强迫数不小于最多不交交错圈的个数,Guenin和Thomas表明对不含K3,3或希伍德图的偶剖分作为好子图的二部图前面两者有相等关系;每个完美匹配的反强迫数不小于最大相容交错集的大小,并且对不含K3,3的剖分的二部图前面两者有相等关系.近几年,关于图的最大最小强迫数与反强迫数,以及强迫谱与反强迫谱的研究有了一些较深入的讨论.然而,计算一个图中有多少个完美匹配具有相同的强迫数与反强迫数是匹配强迫问题的一个新领域.在此基础上,本文提出了图的强迫多项式,即将具有相同强迫数的完美匹配个数作为系数的计数多项式,并从图G的强迫多项式中得到了一些重要的拓扑指标.比如,其多项式的系数之和是G的完美匹配的个数,将其多项式的导数中变元取值1时可以得到G的所有完美匹配强迫数之和,这两个指标相除可以得到G的平均强迫数.从图的强迫多项式中也可以得到它的最大与最小强迫数及强迫谱.类似地,Hwang等将具有相同反强迫数的完美匹配个数作为系数的计数多项式定义为反强迫多项式,从中同样可以得到一系列拓扑指标.本文计算了一些图类的强迫与反强迫多项式.方法是首先分析图的组合结构给出递推关系,再结合组合计数方法做出具体表达式.主要结构如下.第一章中我们介绍了两类重要的平面二部图,综述了匹配强迫与反强迫数的研究背景.第二章中我们引入了图的匹配强迫多项式并得到了其基本性质.给出了cata-型六角系统强迫多项式的递推关系.特别地,我们利用生成函数的方法推导出了 zigzag六角链强迫多项式的具体表达式并得到了其平均强迫数的渐近行为,从中推导出了由Klein和Randic得到的zigzag六角链的自由度.第三章中我们给出了平行四边形六角系统强迫多项式的递推关系及具体表达式,最大与最小强迫数以及当一个指标趋向于无穷时平均强迫数的渐近行为,并通过组合计数方法也给出了它的强迫多项式.第四章中我们研究了图的匹配反强迫多项式.得到了具有强迫边的六角系统的反强迫多项式的递推关系,从中推导出了其反强迫谱的连续性.特别地,我们给出了平行四边形六角系统反强迫多项式的具体表达式,最大与最小反强迫数以及当一个指标趋向于无穷时平均反强迫数的渐近行为.第五章中我们分别给出了 2 × n格子图与3 × 2n格子图的强迫与反强迫多项式的具体表达式,以及强迫与反强迫谱.第六章中我们列出了当3≤n≤36时广义彼得森图P(n,2)的强迫多项式以及当n≥37时P(n,2)的强迫谱[[n/12]+ 1,[n+3/7]+ δ(n)]∪[[n-2/6],[n/4]],其中δ(n)=1若≡3(mod 7),而其它情况δ(n)= 0,它是两个整区间的并.
其他文献
随着我国教育事业的发展,艺术教育越来越受到大家的关注,综合素质和核心素养的提出证明了我国已经开始重视素质教育的发展。舞蹈作为艺术的一个重要分支,是美育教育领域中不可或缺的一个部分,它有着促进学生身心健康、缓解学习压力的功能。学生通过学习舞蹈可以增强自信,激发自身认识美、欣赏美、感受美的能力,进而提升学习的热情。本文选取郑州Z中学初中的学生和教师作为研究对象,采取实证研究方法,通过收集问卷、访谈、实
车轴是铁路机车车辆走行部最重要的部件,它几乎承受了机车车辆的全部重量。机车车辆在运行过程中一旦发生断轴,将引起列车脱轨、翻车等重大恶性事故。轮轴过盈配合部位的微动
随着国家经济的发展,中小型企业的经济效益受到广泛重视,然而,在我国中小型企业财务管理的过程中,还存在较多难以解决的问题,无法提高财务管理工作效率,甚至会影响中小型企业
研究目的:动作变异性是运动技能动作重复过程中不可避免的问题,即使是大量的重复性训练也几乎不可能完成完全相同的动作。研究表明并非训练负荷量越大越好,而且在出现疲劳,动
语言是文化的载体,学习英语必然会学习这门语言的文化。2018年颁布的《普通高中英语课程标准》,将文化意识列为英语学科核心素养之一,并将培养学生的文化意识作为英语课程目
以分析物联网安全的发展和演进,对二维码及相关技术进行论述,进而提高政法机关对于二维码犯罪的治理能力。以2016年网络安全数据和互联网犯罪数据为基础样本分析,论述二维码
针织行业在整个纺织工业中占据重要的地位,针织机械作为针织行业中的重要设备,对产业升级和技术进步起着重要作用。作为针织机械中的重要一类,针织圆纬机的自动化水平也在不
土壤盐渍化是作物生产的主要障碍之一。棉花较耐盐胁迫,是盐碱地先锋作物,但高盐胁迫仍对棉花的生长发育及其产量品质造成严重的影响。当土壤盐浓度超过0.3%时,棉花植株的生
共振的概念来源于有机化学中Clar芳香六隅体理论和Randic共轭圈模型.图的k-共振性首先是在苯系统中进行研究的.一个苯系统被称为是k-共振的(k≥1),如果任意删掉i个(0≤i≤k)
文化和旅游并蒂莲生,文化产业与旅游产业相互融合相互促进,互动融合点非常之高。庐江县作为两汉文明之地有着丰富的历史文化资源,同时也蕴育着丰富多彩的旅游资源,对于庐江的