本文關(guān)鍵詞：點(diǎn)賦權(quán)二部圖上最大邊裝填問題和最小頂點(diǎn)覆蓋問題的相關(guān)性及其算法研究

  更多相關(guān)文章： 匹配 頂點(diǎn)覆蓋 難 邊裝填 計(jì)算復(fù)雜性 整數(shù)規(guī)劃

【摘要】：給定一個(gè)無向圖,一個(gè)邊的子集稱為匹配,如果里面的任意兩條邊都沒有共同的交點(diǎn)；一個(gè)頂點(diǎn)的子集稱為頂點(diǎn)覆蓋,如果圖中每一條邊的兩個(gè)端點(diǎn)中的至少一個(gè)在該頂點(diǎn)子集內(nèi)。經(jīng)典的最大匹配問題要求圖中包含邊數(shù)最多的匹配,而經(jīng)典的頂點(diǎn)覆蓋問題要求圖中包含頂點(diǎn)數(shù)最少的頂點(diǎn)覆蓋。匹配與頂點(diǎn)覆蓋問題是組合最優(yōu)化研究的中心問題。在計(jì)算復(fù)雜性方面,匹配可認(rèn)為是類問題的典型代表,頂點(diǎn)覆蓋問題可認(rèn)為是難問題的典型代表。對匹配與頂點(diǎn)覆蓋問題的持續(xù)和深入研究推動(dòng)了學(xué)科的發(fā)展,豐富了算法理論和技巧,揭示了深刻的數(shù)學(xué)關(guān)系。Kǒnig(1931)找到了讓這兩個(gè)問題相互聯(lián)系的圖論結(jié)構(gòu)：二部圖。經(jīng)典的Kǒnig定理斷言：在二部圖中,最大的匹配包含的邊數(shù)等于最小的頂點(diǎn)覆蓋包含的頂點(diǎn)數(shù)。20世紀(jì)以來離散數(shù)學(xué)的發(fā)展見證了Kǒnig定理的深刻性。很多推動(dòng)學(xué)科發(fā)展的著名定理都和Kǒnig定理等價(jià),它們包括：代數(shù)學(xué)中的P. Hall定理,偏序集上的Dilworth定理,圖論中的Menger定理,網(wǎng)絡(luò)流的最大流最小割定理等等。本文研究點(diǎn)賦權(quán)二部圖上的邊裝填與頂點(diǎn)覆蓋問題,關(guān)注它們的關(guān)系及其算法研究。給定一個(gè)無向圖,每個(gè)頂點(diǎn)上有一個(gè)正整數(shù)權(quán)重,一個(gè)邊的子集(邊允許重復(fù))稱為一個(gè)邊裝填,如果圖中每個(gè)頂點(diǎn)與中的邊相關(guān)聯(lián)的數(shù)目不超過該點(diǎn)的權(quán)重；一個(gè)頂點(diǎn)的子集稱為頂點(diǎn)覆蓋,如果圖中每一條邊都與相交。最大邊裝填問題要求圖中包含邊數(shù)最多的邊裝填,而最小頂點(diǎn)覆蓋問題要求圖中頂點(diǎn)權(quán)重之和最小的頂點(diǎn)覆蓋。這兩個(gè)問題推廣了經(jīng)典的最大匹配與最小頂點(diǎn)覆蓋問題,有重要的理論意義和廣闊的應(yīng)用前景。本文分析了這兩個(gè)問題的計(jì)算復(fù)雜性,用整數(shù)規(guī)劃理論證明了這兩個(gè)問題的最優(yōu)值在二部圖結(jié)構(gòu)下相等,并提供了多項(xiàng)式時(shí)間算法求解任意二部圖上的這兩個(gè)問題的最優(yōu)解。我們的結(jié)果推廣了Kǒnig定理,并為相關(guān)的裝填與覆蓋問題提供了有益的參考。
【學(xué)位授予單位】：昆明理工大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：O157.5

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

10 ;[J];;年期

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

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

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

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

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

1 郭洪敏;最小頂點(diǎn)覆蓋問題的幾種DNA算法研究[D];安徽理工大學(xué);2016年

2 段俠;點(diǎn)賦權(quán)二部圖上最大邊裝填問題和最小頂點(diǎn)覆蓋問題的相關(guān)性及其算法研究[D];昆明理工大學(xué);2016年

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

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

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

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

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

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

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

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

，

本文編號：1225037