图的匹配强迫谱与匹配反强迫谱研究

发布时间：2018-02-11 15:38

本文关键词： 完美匹配强迫数反强迫数六角系统偶多边形链　出处：《兰州大学》2016年博士论文　论文类型：学位论文

【摘要】：图G中的一个完美匹配M的强迫数是指为确定M所需要的最少的M-匹配边的数目.图中完美匹配的强迫数的概念最早由Harary等提出,Klein和Randi′c也在早期的化学文献中提出了同样的概念,称作是凯库勒结构的内自由度,这在化学共振理论中有重要应用.图G中所有完美匹配的强迫数的集合称作是G的强迫谱,强迫谱中最小整数称作是图G的强迫数或最小强迫数,最大整数叫做图G的最大强迫数.从对立面考虑,M的反强迫数是指从图G中删去最少的不在M中的边的数目使得M是删边后的图中唯一的完美匹配.图G中所有完美匹配的反强迫数的集合称作是G的反强迫谱,反强迫谱中最小整数称作是图G的反强迫数或最小反强迫数,最大整数叫做图G的最大反强迫数.本文共有六个章节.第一章首先介绍了图论中的一些基本概念和符号;然后介绍了匹配强迫和匹配反强迫问题的研究背景及进展;最后我们给出了本文的主要研究结果.在第二章中,我们证明了强迫数等于1的六角系统H的强迫谱要么是从1到其Clar数cl(H)的整数区间[1,cl(H)],要么是[1,cl(H)]\{2}.我们还给出了六角系统的强迫谱没有间隔的一个充分条件.在第三章中,我们首先证明了任意一个正整数集合都可以是某个图的反强迫谱;接着我们刻画了反强迫数等于1的平面基本二部图;然后我们证明了图的最大反强迫数不超过其基圈数,并且刻画了最大反强迫数等于基圈数的极值图;最后我们证明了确定最大度为4的二部图中完美匹配的反强迫数是NP-完全问题.在第四章中,我们证明了六角系统的反强迫谱中任意两个相继的整数之间至多有1个间隔,并且cata-型六角系统的反强迫谱没有间隔.在第五章中,我们证明了两类可构造型六角系统的反强迫谱是整数区间.作为直接推论,强迫数为1的六角系统的反强迫谱没有间隔.在第六章中,我们证明了偶多边形链的反强迫谱没有间隔,并且给出了计算偶多边形链的最小反强迫数和最大反强迫数的线性算法.由此确定偶多边形链的反强迫谱是线性时间的.
[Abstract]:The forcing number of a perfect matching M in graph G is the minimum number of M- matching edges needed to determine M. The concept of the perfect matching forced number in the graph was first proposed by Harary et al. Klein and Randi'c were also proposed in the early chemical literature. And came up with the same concept, It is called the internal degree of freedom of the Kakuhler structure, which has an important application in the chemical resonance theory. The set of all the perfectly matched forcing numbers in graph G is called the forced spectrum of G. The minimum integer in the forced spectrum is called the forced number or the minimum forced number of the graph G. The maximum integer is called the maximum forced number of graph G. the anti-forcing number of M is to delete the least number of edges not in M from the graph G. so that M is the only perfect match in the deleted graph. The set of perfectly matched anti-forcing numbers is called the anti-compulsive spectrum of G. In the spectrum of anti-compulsion, the minimum integer is the anti-forcing number of graph G or the minimum number, and the largest integer is the maximum number of anti-compulsions of graph G. there are six chapters in this paper. In the first chapter, some basic concepts and symbols in graph theory are introduced. Then, the research background and progress of matching forcing and matching anti-compulsion are introduced. Finally, we give the main results of this paper. We prove that the forced spectrum of a hexagonal system H with a forced number equal to 1 is either an integer interval from 1 to its Clar number CLH] or [1 Clar H]\ {2}. We also give a sufficient condition that the forced spectrum of a hexagonal system has no interval. In Chapter 3, We first prove that any set of positive integers can be an anti-forced spectrum of a graph; then we characterize a basic bipartite graph of a plane with an anti-forced number equal to 1; then we prove that the maximum number of anti-forcing numbers of a graph does not exceed the number of its base cycles. Finally, we prove that the perfect matching number of bipartite graphs with maximum degree 4 is NP-complete problem. We prove that there is at least one interval between any two successive integers in the spectrum of a hexagonal system and that there is no interval in the spectrum of a cata- type hexagonal system. In Chapter 5th, We prove that the spectrum of two kinds of constructive hexagonal systems is an integer interval. As a direct corollary, there is no interval between the spectrum of two classes of hexagonal systems with a forced number of 1. In Chapter 6th, We prove that there is no interval between the spectrum of even polygon chains, and give a linear algorithm to calculate the minimum number and maximum number of the even polygon chains, which determines that the spectrum of even polygon chains is linear.
【学位授予单位】：兰州大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：O157.5

【相似文献】