本文關(guān)鍵詞： 完美匹配 強(qiáng)迫數(shù) 反強(qiáng)迫數(shù) 六角系統(tǒng) 偶多邊形鏈　出處：《蘭州大學(xué)》2016年博士論文　論文類型：學(xué)位論文

【摘要】：圖G中的一個(gè)完美匹配M的強(qiáng)迫數(shù)是指為確定M所需要的最少的M-匹配邊的數(shù)目.圖中完美匹配的強(qiáng)迫數(shù)的概念最早由Harary等提出,Klein和Randi′c也在早期的化學(xué)文獻(xiàn)中提出了同樣的概念,稱作是凱庫勒結(jié)構(gòu)的內(nèi)自由度,這在化學(xué)共振理論中有重要應(yīng)用.圖G中所有完美匹配的強(qiáng)迫數(shù)的集合稱作是G的強(qiáng)迫譜,強(qiáng)迫譜中最小整數(shù)稱作是圖G的強(qiáng)迫數(shù)或最小強(qiáng)迫數(shù),最大整數(shù)叫做圖G的最大強(qiáng)迫數(shù).從對立面考慮,M的反強(qiáng)迫數(shù)是指從圖G中刪去最少的不在M中的邊的數(shù)目使得M是刪邊后的圖中唯一的完美匹配.圖G中所有完美匹配的反強(qiáng)迫數(shù)的集合稱作是G的反強(qiáng)迫譜,反強(qiáng)迫譜中最小整數(shù)稱作是圖G的反強(qiáng)迫數(shù)或最小反強(qiáng)迫數(shù),最大整數(shù)叫做圖G的最大反強(qiáng)迫數(shù).本文共有六個(gè)章節(jié).第一章首先介紹了圖論中的一些基本概念和符號;然后介紹了匹配強(qiáng)迫和匹配反強(qiáng)迫問題的研究背景及進(jìn)展;最后我們給出了本文的主要研究結(jié)果.在第二章中,我們證明了強(qiáng)迫數(shù)等于1的六角系統(tǒng)H的強(qiáng)迫譜要么是從1到其Clar數(shù)cl(H)的整數(shù)區(qū)間[1,cl(H)],要么是[1,cl(H)]\{2}.我們還給出了六角系統(tǒng)的強(qiáng)迫譜沒有間隔的一個(gè)充分條件.在第三章中,我們首先證明了任意一個(gè)正整數(shù)集合都可以是某個(gè)圖的反強(qiáng)迫譜;接著我們刻畫了反強(qiáng)迫數(shù)等于1的平面基本二部圖;然后我們證明了圖的最大反強(qiáng)迫數(shù)不超過其基圈數(shù),并且刻畫了最大反強(qiáng)迫數(shù)等于基圈數(shù)的極值圖;最后我們證明了確定最大度為4的二部圖中完美匹配的反強(qiáng)迫數(shù)是NP-完全問題.在第四章中,我們證明了六角系統(tǒng)的反強(qiáng)迫譜中任意兩個(gè)相繼的整數(shù)之間至多有1個(gè)間隔,并且cata-型六角系統(tǒng)的反強(qiáng)迫譜沒有間隔.在第五章中,我們證明了兩類可構(gòu)造型六角系統(tǒng)的反強(qiáng)迫譜是整數(shù)區(qū)間.作為直接推論,強(qiáng)迫數(shù)為1的六角系統(tǒng)的反強(qiáng)迫譜沒有間隔.在第六章中,我們證明了偶多邊形鏈的反強(qiáng)迫譜沒有間隔,并且給出了計(jì)算偶多邊形鏈的最小反強(qiáng)迫數(shù)和最大反強(qiáng)迫數(shù)的線性算法.由此確定偶多邊形鏈的反強(qiáng)迫譜是線性時(shí)間的.
[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.
【學(xué)位授予單位】：蘭州大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2016
【分類號】：O157.5

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 王守中;江蓉;;一類2-共振六角系統(tǒng)的若干性質(zhì)[J];茂名學(xué)院學(xué)報(bào);2006年01期

2 江蓉;任海珍;;一類2-共振六角系統(tǒng)的性質(zhì)與構(gòu)造[J];西南師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2007年03期

3 江蓉;王守中;任海珍;;兩類2-共振的六角系統(tǒng)的刻畫[J];河北大學(xué)學(xué)報(bào)(自然科學(xué)版);2009年04期

4 張福基;陳榮斯;;六角系統(tǒng)克庫勒結(jié)構(gòu)的計(jì)數(shù)[J];新疆大學(xué)學(xué)報(bào)(自然科學(xué)版);1986年03期

5 張?jiān)茲G;;一類六角系統(tǒng)計(jì)數(shù)問題的計(jì)算機(jī)實(shí)現(xiàn)[J];新疆大學(xué)學(xué)報(bào)(自然科學(xué)版);1988年01期

6 陳弘;六角系統(tǒng)的完美匹配[J];信陽師范學(xué)院學(xué)報(bào)(自然科學(xué)版);1989年01期

7 林國寧;張福基;;關(guān)于一類六角系統(tǒng)的共振多項(xiàng)式[J];新疆大學(xué)學(xué)報(bào)(自然科學(xué)版);1989年02期

8 陳弘;一類六角系統(tǒng)的完美匹配[J];信陽師范學(xué)院學(xué)報(bào)(自然科學(xué)版);1990年02期

9 林詒勛;林國寧;;凸六角系統(tǒng)(Ⅰ)[J];新疆大學(xué)學(xué)報(bào)(自然科學(xué)版);1990年01期

10 張福基,陳榮斯;六角系統(tǒng)中完美匹配的覆蓋與對應(yīng)(英文)[J];新疆大學(xué)學(xué)報(bào)(自然科學(xué)版);1991年03期

相關(guān)博士學(xué)位論文 前7條

1 鄧凱;圖的匹配強(qiáng)迫譜與匹配反強(qiáng)迫譜研究[D];蘭州大學(xué);2016年

2 周向前;平面圖的強(qiáng)迫集、反強(qiáng)迫集與交錯集之間的關(guān)系[D];蘭州大學(xué);2016年

3 趙飚;匹配理論和網(wǎng)絡(luò)可靠性的若干問題[D];新疆大學(xué);2003年

4 蔡金轉(zhuǎn);關(guān)于一些圖類的全局強(qiáng)迫數(shù)及反凱庫勒數(shù)的研究[D];蘭州大學(xué);2012年

5 徐志霞;化學(xué)圖論和網(wǎng)絡(luò)圖論的若干問題[D];新疆大學(xué);2002年

6 何敬華;若干曲面格子圖的譜[D];蘭州大學(xué);2008年

7 蔣曉艷;關(guān)于一些圖類的匹配強(qiáng)迫數(shù)及譜的研究[D];蘭州大學(xué);2011年

相關(guān)碩士學(xué)位論文 前10條

1 趙小東;強(qiáng)迫數(shù)為2的六角系統(tǒng)[D];蘭州大學(xué);2007年

2 楊斌斌;兩類環(huán)狀六角系統(tǒng)的計(jì)數(shù)[D];廈門大學(xué);2007年

3 何清華;化學(xué)圖的Hosoya多項(xiàng)式及其改進(jìn)Hosoya多項(xiàng)式[D];蘭州大學(xué);2015年

4 婁貞貞;三類六角系統(tǒng)圖的譜及其應(yīng)用[D];新疆大學(xué);2013年

5 陳海洋;兩類圖的Hosoya多項(xiàng)式[D];蘭州大學(xué);2013年

6 姜永勝;關(guān)于一類混合苯型系統(tǒng)圖相關(guān)性質(zhì)的研究[D];新疆大學(xué);2014年

7 魏首柳;本質(zhì)不連通冠狀系統(tǒng)的若干結(jié)構(gòu)特征[D];福州大學(xué);2005年

8 李永軍;識別六角系統(tǒng)同譜異構(gòu)圖的計(jì)算機(jī)方法[D];新疆大學(xué);2007年

9 張義;幾何凱庫勒結(jié)構(gòu)和代數(shù)凱庫勒結(jié)構(gòu)一一對應(yīng)的六角系統(tǒng)[D];蘭州大學(xué);2014年

10 丁娟;關(guān)于雙渺位F-苯系統(tǒng)的Randi（？）指數(shù)[D];湖南師范大學(xué);2011年

，

本文編號：1503403