图中的若干极值问题

来源 :厦门大学 | 被引量 : 0次 | 上传用户:doublexiu
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
令υ12,…,υm是Rn中的向量。对于λi∈R,λi≥0,(?)λi=1,υ=λ1υ12υ2+…+λmυm被称为是{υ12,…,υm)的凸组合。{υ12,…,υm}所有凸组合的集合就是{υ12,…,υm)的一个凸包。在Rn中的有限个向量的集合X的凸包被称为是一个多面体,并且用P来表示。一个多面体P的顶点是多面体的零维面,并且P中的两个顶点u和υ可相邻当且仅当它们是多面体的同一个一维面中的点。一个多面体P的图(或者骨架)G(P)是一个图,它的顶点是多面体的顶点,并且它有一条边连接一对顶点,如果对应于多面体的这对顶点是相邻的,也就是这对顶点被多面体的一条边所连。这类图的研究已经有较长的历史。一个多面体称为是(0,1)多面体,如果它的顶点所对应的向量的每个分量都是0、或者1。在1984年,Naddef和Pulleyblank证明了如果一个(0,1)多面体的骨架G(P)是一个二部图,那么G(P)是一个超立方体;如果G(P)是非二部图,那么G(P)是哈密顿连通的。这类(0,1)多面体包含很多著名的多面体,如:匹配多面体、拟阵基多面体、稳定集多面体和置换多面体。我们研究了完美匹配多面体的若干极值问题。人们对具有完美匹配的图已经做过大量的研究,其最基本的结果是在1947年,Tutte所给出的对具有完美匹配的图的一个刻画。最近,为了研究具有完美匹配的图的Tutte集(或者barrier)和极端集,Bauer,Broersma,Morgana和Schmeichel提出了一种新的图运算被称为D-图,并且得到了很多有趣的性质。图G的水平是一个最小的整数k≥0使得Dk+1(G)(?)Dk(G),这里取D?(G)=G。我们主要研究了若干图类的水平,并且给出了几类特殊图类的D-图的刻画。在匹配理论中,完美匹配的计数也是匹配理论的一个重要的研究方向。我们研究了几类多边形Cacti链的匹配和独立集,并且确定了关于k-匹配和k-独立集的多边形Cacti链的极值链。Wiener数是理论化学研究中的一个重要参数,我们研究了树状多联苯的Wiener数。这篇论文分为六章。在第一章,我们首先介绍了图和匹配的一些相关定义和概念。其次,我们概述了匹配理论新近的一些主要结果和发展现状。第三,我们概述了Wiener数的理论背景及其主要结果。在这章的最后,我们列举了本文的主要研究成果。在第二章,我们给出了完美匹配图是二部图的二部图的刻画。得到了这类图关于边的一个紧的上界,并且构造了达到此上界的极值图类。在第三章,我们给出了完美匹配图是二部图的非二部图的刻画。得到了这类图关于边的一个紧的上界,并且构造了达到此上界的极值图类。在第四章,我们首先研究了基本图的水平,并且证明了对于任意一个非二部图的基本图,它的D2(G)是一个完全图。此外,我们还给出了饱和图的D-图的刻画,对于非二部图的情形给出了一个例子。第二,根据二部图的典型分解,我们给出了二部图的D-图的精确构造,并分别给出了level=0和level=1的二部图的刻画。最后,我们给出了level=0的具有唯一完美匹配的饱和图的D-图的刻画以及这类图的边数的一个紧的上界。在第五章,我们考虑了几类多边形Cacti链,并研究了他们的匹配和独立集,明确给出了这几类多边形Cacti链的匹配和独立集多项式的递推式以及若干特殊值的亏d-匹配数。另外,我们确定了关于k-匹配和k-独立集的多边形Cacti链的极值链。最后,我们明确给出具有n个多边形的星形多边形Cacti链的匹配和独立集多项式。在最后一章,我们确定了所有具有九个六边形的最大和最小Wiener数的多联苯链和具有最大Wiener数的树状多联苯系统,并给出了极值多联苯链的Wiener数的明确计算公式。
其他文献
随机过程应用的不断发展与进步,使得其应用范围越来越广,特别是在工程技术、生物学与生命科学、管理、经济金融等领域都取得了较好的应用效果。本文试图对我国人才市场中人才流
通过对平整变接触支持辊轧制策略的有限元仿真分析和上机试验,以及拉矫工艺参数的神经网络在线设定及卷取过程钢卷内部应力场的逐层迭代计算分析,形成了一套热镀锌机组板形控制
法律职业共同体的存在是法治国家赖以存续的基础,建立独立且自治、成熟并强大的法律职业共同体是法治社会建成的必经之路。现阶段,我国法律职业共同体虽已初步形成,但距离理
现实中的决策人不可能是完全理性的,他的价值取向和多元化目标并不总是始终一致的,往往相互矛盾和没有统一的度量标准。由此本文将单一参照基准的多目标决策方法TOPSIS法加以推
研究了次声传感器的频率特性的分布情况,定量分析了次声传感器组成部件参数对幅频特性的影响。通过求解次声传感器前后腔内的次声波动态方程得到频率响应模型和截止周期误差
在纳米光刻中,采用周期相差不大的两光栅分别作为掩模和硅片上的对准标记。当对准光路通过这两个标记光栅时受到两次调制,发生双光栅衍射及衍射光的干涉等复杂现象,最后形成有规
在新冠肺炎疫情防控中,政府的行政行为对部分民事合同的履行产生较大影响,可能造成合同不能履行、迟延履行或合同目的不能实现等法律后果。在法律适用上,由于不可抗力与情事
朝鲜北学派实学代表人物朴齐家曾先后4次出访燕京,他冲破了夷夏之辨和小中华的传统狭隘观念,系统地总结了北学论思想,提出了从器物利用到思想文化对外开放的主张,以实现正德利用