图中的若干极值问题

论文摘要

令υ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数的明确计算公式。

论文目录

• 摘要
• Abstract
• 第一章 序言
• §1.1 基本定义与符号
• §1.2 匹配理论的一些研究背景
• §1.3 Wiener数的介绍
• §1.4 本文的主要研究结果
• 第二章 二部图的完美匹配多面体的图
• §2.1 引言
• §2.2 完美匹配图是二部图的二部图的刻画及极值图
• §2.3 一般二部图的完美匹配多面体
• 第三章 非二部图的完美匹配多面体的图
• §3.1 引言
• §3.2 完美匹配图是二部图的非二部图的刻画及极值图
• 第四章　D-图
• §4.1 引言
• §4.2 基本图和饱和图的D-图
• §4.3 二部图的D-图的构造
• §4.4 具有唯一完美匹配图的D-图
• 第五章 Cactus图
• §5.1 引言
• §5.2 h-多边形cacti链的k-匹配与极值链
• §5.3 h-多边形cacti链的k-独立集与极值链
• §5.4 星形h-多边形cacti链的k-匹配和k-独立集
• 第六章 多联苯
• 6.1 引言
• §6.2 多联苯链的极值Wiener数
• §6.3 树状多联苯系统的极值Wiener数
• 参考文献
• 作者在攻读博士学位期间完成的有关学术论文
• 致谢