【摘要】：圖的k-路頂點覆蓋理論在無線傳感網(wǎng)絡(luò)和交通控制領(lǐng)域都有很重要的應(yīng)用。近幾年來在國內(nèi)外得到了廣泛的研究。圖的k-路頂點覆蓋問題,也簡稱為k-VCP,找到一個最小的頂點子集F,使得在圖G每一條長度為k的路中至少含有F中的一個頂點。k-路頂點覆蓋的最小基數(shù)叫做圖G的k-路頂點覆蓋數(shù),記做ψk(G)。實際上,我們用路的頂點數(shù)來表示次序,同時我們用長度來表示路的邊數(shù)。由圖G =(V(G),E(G))和圖H=(V(H),E(H))構(gòu)成的笛卡爾乘積圖G□H的頂點集為V(G)× V(H),并且當(dāng)u1 = u2且v1v2∈E(G)或u1u2 ∈E(G)且v1=v2時,頂點(u1,v1)和頂點(u2,v2)是相連的.由圖G =(V(G),E(G))和圖H=(V(H),E(H))構(gòu)成的字典乘積圖GoH的頂點集為V(G)×V(H),并且當(dāng) u1u2 ∈ E(G),或 u1 = u2 且v1v2∈E(H)時,頂點(u1,v1)和頂點(u2,v2)是相連的.由圖G =(V(G),E(G))和圖H =(V(H).E(H))構(gòu)成的強乘積圖G(?)H的頂點集為V(G)×V(H),并且當(dāng)u1u2 ∈ E(G)且v1 = v2,或u1 = u2 且 v1v2 ∈ E(H),或u1u2 ∈ E(G)且巧v1v2 ∈E(H)時,頂點(u1,v1)和頂點(u2,v2)是相連的.本文主要研究了乘積圖的k-路頂點覆蓋問題.第一章首先簡單介紹了預(yù)備知識和圖的k路頂點覆蓋的相關(guān)研究背景.第二章給出了 Pm□Cn的k路頂點覆蓋數(shù)的上下界.根據(jù)引理1.1和1.2我們證明了 ψk(Wn+1)的精確值,并且在此結(jié)果的影響下得到了Pm和Wn+1之間各類乘積圖的k路頂點覆蓋數(shù)的估計值.第三章證明了Km,n的k路頂點覆蓋數(shù)的確切的值.與此同時在Km,n的結(jié)果下,我們得到Km,n和P2的笛卡爾乘積圖的k路頂點覆蓋數(shù)的估計值第四章研究了笛卡爾乘積圖Pm□Cn和強乘積圖Pm(?)Cn的k路頂點覆蓋的更加精確的上界,并且給出了ψk(Cm□Pn2)的下界.本文所得結(jié)論是全新的.可以通過構(gòu)造k路頂點覆蓋集的方式得以驗證.每一章都給出了構(gòu)造的相應(yīng)k路頂點覆蓋集.證明了所得結(jié)論的正確性及有效性.所得結(jié)果為更復(fù)雜圖的k路頂點覆蓋問題提供了一定的理論基礎(chǔ).
【學(xué)位授予單位】：天津師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2018
【分類號】：O157.5

【相似文獻(xiàn)】

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

1 支志兵;寧愛兵;胡琳琳;張惠珍;;3度圖的最小頂點覆蓋問題的多項式時間算法[J];數(shù)學(xué)理論與應(yīng)用;2014年03期

2 吳春;朱國魂;謝玉忠;林宏;;一種求解平面圖的最小頂點覆蓋算法[J];計算機系統(tǒng)應(yīng)用;2010年09期

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

4 王新輝;劉三陽;劉紅衛(wèi);;頂點覆蓋問題的強化半定規(guī)劃松弛[J];西安電子科技大學(xué)學(xué)報;2005年06期

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

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

7 馬金良;;頂點覆蓋問題的一個算法[J];微電子學(xué)與計算機;1988年12期

8 鄭光勇;李肯立;潘果;徐雨明;蔣偉進(jìn);焦鉻;;化學(xué)反應(yīng)優(yōu)化算法求解最小頂點覆蓋問題[J];小型微型計算機系統(tǒng);2015年02期

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

10 張春露;殷志祥;;圖的最小頂點覆蓋問題的鏈置換模型[J];佳木斯大學(xué)學(xué)報(自然科學(xué)版);2018年02期

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

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

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

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

4 吳帆;基于生化反應(yīng)的典型約束可滿足問題求解算法研究[D];湖南大學(xué);2017年

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

1 李釗;一些乘積圖和完全二部圖的k路頂點覆蓋[D];天津師范大學(xué);2018年

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

3 方靚;泛化頂點覆蓋問題的局部搜索算法研究[D];東北師范大學(xué);2016年

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

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

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

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

8 周金鳳;圖的最小頂點覆蓋問題的幾種DNA計算模型[D];安徽理工大學(xué);2013年

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

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

，

本文編號：2644734