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

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

【相似文獻】

相關期刊論文 前10條

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

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

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

4 張�；�;陳榮斯;;六角系統(tǒng)克庫勒結構的計數[J];新疆大學學報(自然科學版);1986年03期

5 張云滸;;一類六角系統(tǒng)計數問題的計算機實現[J];新疆大學學報(自然科學版);1988年01期

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

7 林國寧;張�；�;;關于一類六角系統(tǒng)的共振多項式[J];新疆大學學報(自然科學版);1989年02期

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

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

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

相關博士學位論文 前7條

1 鄧凱;圖的匹配強迫譜與匹配反強迫譜研究[D];蘭州大學;2016年

2 周向前;平面圖的強迫集、反強迫集與交錯集之間的關系[D];蘭州大學;2016年

3 趙飚;匹配理論和網絡可靠性的若干問題[D];新疆大學;2003年

4 蔡金轉;關于一些圖類的全局強迫數及反凱庫勒數的研究[D];蘭州大學;2012年

5 徐志霞;化學圖論和網絡圖論的若干問題[D];新疆大學;2002年

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

7 蔣曉艷;關于一些圖類的匹配強迫數及譜的研究[D];蘭州大學;2011年

相關碩士學位論文 前10條

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

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

3 何清華;化學圖的Hosoya多項式及其改進Hosoya多項式[D];蘭州大學;2015年

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

5 陳海洋;兩類圖的Hosoya多項式[D];蘭州大學;2013年

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

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

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

9 張義;幾何凱庫勒結構和代數凱庫勒結構一一對應的六角系統(tǒng)[D];蘭州大學;2014年

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

，

本文編號：1503403