论文部分内容阅读
令υ1,υ2,…,υm是Rn中的向量。对于λi∈R,λi≥0,(?)λi=1,υ=λ1υ1+λ2υ2+…+λmυm被称为是{υ1,υ2,…,υm)的凸组合。{υ1,υ2,…,υm}所有凸组合的集合就是{υ1,υ2,…,υ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数的明确计算公式。