本文關(guān)鍵詞：頂點覆蓋推廣問題的算法設(shè)計與圖不變量的研究

  更多相關(guān)文章： 近似算法 迭代松弛方法 部分頂點覆蓋問題 獎勵收集頂點問題 圖不變量 度阻尼距離 單圈圖 雙圈圖 仙人掌圖

【摘要】：考慮一個頂點賦權(quán)圖,定義圖中每個頂點子集的權(quán)重為其包含的頂點總權(quán)重,同時,如果存在某個頂點子集,滿足圖中每條邊均至少有一個端點屬于該頂點子集,則稱其為頂點覆蓋集。頂點覆蓋問題是指在給定的圖G中尋找一個權(quán)重最小的頂點覆蓋集。該問題作為圖論經(jīng)典問題,受到了研究者的廣泛關(guān)注。本文主要研究內(nèi)容之一是頂點覆蓋問題的兩個推廣問題——部分頂點覆蓋問題與獎勵收集頂點覆蓋問題。如果要求頂點子集只需覆蓋圖中至少k條邊,則頂點覆蓋問題就轉(zhuǎn)化為部分頂點覆蓋問題,顯然有當(dāng)k取到圖的邊數(shù)時,部分頂點覆蓋問題將退化為頂點覆蓋問題。類似地,如果給每條邊賦予懲罰費用,對于圖中的頂點子集,定義一種特殊的權(quán)重,為其包含的頂點總權(quán)重加上未被其覆蓋的邊的總費用,目標(biāo)為尋找一個權(quán)重最小的頂點子集,則稱為獎勵收集頂點覆蓋問題,顯然有懲罰費用均遠(yuǎn)大于頂點權(quán)值時,獎勵收集頂點覆蓋問題將退化為頂點覆蓋問題。本文采用迭代松弛方法依次設(shè)計了部分頂點覆蓋問題的一個近似度為2+q/~(OPT)的近似算法,其中Q表示有限的最大的頂點權(quán)值,OPT表示該問題的最優(yōu)解的值,一個近似度為2的近似算法,以及獎勵收集頂點問題的一個2-近似算法。圖不變量,指圖(或圖的一部分)到實數(shù)集的一個映射,并且其在同構(gòu)圖中取值相同。其中,基于頂點間距離的一系列圖不變量在理論化學(xué)領(lǐng)域得到了廣泛的研究和應(yīng)用。本文著重研究了度阻尼距離,其由Gutman等在2012年首次提出,其定義為其中dG(u)表示頂點u的度,RG(u,v)表示頂點u,v之間的阻尼距離。我們研究并刻畫了具有最大度阻尼距離的單圈圖和雙圈圖,以及具有最小度阻尼距離的仙人掌圖。
【學(xué)位授予單位】：北京化工大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：O157.5

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 祝丹梅,孫艷蕊;最小頂點覆蓋問題的一個近似算法[J];遼寧師專學(xué)報(自然科學(xué)版);2004年03期

2 陳文彬;;逼近4正則圖的最小頂點覆蓋問題的難解性(英文)[J];廣州大學(xué)學(xué)報(自然科學(xué)版);2014年01期

3 金珍;萬龍;;具有完美匹配的圖的頂點覆蓋問題[J];浙江大學(xué)學(xué)報(理學(xué)版);2013年05期

4 王蓮花;楊建雅;王繼順;;最大頂點覆蓋問題的一種近似算法[J];數(shù)學(xué)的實踐與認(rèn)識;2007年19期

5 賈興德;圖之極小頂點覆蓋[J];曲阜師范大學(xué)學(xué)報(自然科學(xué)版);1995年02期

6 張惠玲;謝邱敏;李煒;;最少頂點覆蓋問題的研究[J];中國新通信;2014年13期

7 杜俊峰;涂建華;;獎勵收集頂點覆蓋問題的一個2-近似算法[J];北京化工大學(xué)學(xué)報(自然科學(xué)版);2014年02期

8 聶曉艷;耿俊;湯建鋼;;圖的最小頂點覆蓋的粘貼DNA計算模型[J];首都師范大學(xué)學(xué)報(自然科學(xué)版);2013年01期

9 王淑棟,劉文斌,許進;圖的最小頂點覆蓋問題的質(zhì)粒DNA計算模型[J];華中科技大學(xué)學(xué)報(自然科學(xué)版);2004年11期

10 ;[J];;年期

中國博士學(xué)位論文全文數(shù)據(jù)庫 前3條

1 曲惠琴;DNA計算若干問題研究[D];復(fù)旦大學(xué);2005年

2 董亞非;若干DNA計算粘貼模型的研究[D];華中科技大學(xué);2004年

3 劉湘輝;IP網(wǎng)絡(luò)帶寬測量的模型與算法的研究[D];國防科學(xué)技術(shù)大學(xué);2005年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前9條

1 儲燕;WSN中基于帆布協(xié)議的覆蓋問題與路由算法研究[D];蘇州大學(xué);2015年

2 杜俊峰;頂點覆蓋推廣問題的算法設(shè)計與圖不變量的研究[D];北京化工大學(xué);2015年

3 何峰;二分圖頂點覆蓋問題的求解及應(yīng)用[D];昆明理工大學(xué);2002年

4 莊濤;s-路徑頂點覆蓋問題的算法研究[D];山東大學(xué);2012年

5 蔡晟;頂點覆蓋問題的確定參數(shù)可解算法研究[D];復(fù)旦大學(xué);2008年

6 張召剛;樹上的最大頂點覆蓋的算法設(shè)計和分析[D];浙江大學(xué);2007年

7 彭震宇;最大獨立集和最小弱頂點覆蓋問題求解及其應(yīng)用研究[D];江南大學(xué);2008年

8 李玉超;頂點覆蓋k-路問題的研究和富勒烯圖的參數(shù)計算[D];北京化工大學(xué);2014年

9 沈樹梅;FPT-算法在CBVC問題中的運用[D];昆明理工大學(xué);2005年

，

本文編號：1183104