本文關(guān)鍵詞：廣義循環(huán)圖彩虹支配問題的研究

  更多相關(guān)文章： 循環(huán)圖 彩虹支配 2-彩虹支配數(shù)

【摘要】：圖論不僅是組合數(shù)學(xué)的一個重要分支,而且還是離散數(shù)學(xué)的一個重要分支。圖的彩虹支配及其相關(guān)問題,是近年來一個比較熱門的研究問題。研究圖的彩虹支配問題不僅具有重要的理論價值,而且具有重要的應(yīng)用價值。它已被廣泛地用來解決計算機(jī)科學(xué)、信息科學(xué)、網(wǎng)絡(luò)理論等學(xué)科的問題,對其研究具有重大意義。本文主要研究的是廣義循環(huán)圖的2-彩虹支配問題,研究結(jié)果如下：(1).研究了廣義循環(huán)圖C(n；(1,2))的2-彩虹支配問題,求出了其2-彩虹支配函數(shù)的精確值；(2).研究了廣義循環(huán)圖C(n；{1,3}.)的2-彩虹支配問題,求出了其2-彩虹支配函數(shù)的精確值；(3).研究了廣義循環(huán)圖C(n；{1,2,...,k})的2-彩虹支配問題,求出了其2-彩虹支配函數(shù)的精確值。本文所研究的廣義循環(huán)圖的2-彩虹支配問題,是一個NP-完全問題。研究它不僅對彩虹支配問題有重大的意義,而且對其它的NP-完全問題也有借鑒作用。這些研究結(jié)果進(jìn)一步豐富了循環(huán)圖的彩虹支配的精確解。
【關(guān)鍵詞】：循環(huán)圖 彩虹支配 2-彩虹支配數(shù)
【學(xué)位授予單位】：內(nèi)蒙古農(nóng)業(yè)大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：O157.5
【目錄】：

• 摘要3-4
• Abstract4-7
• 縮略語表7-8
• 1 引言8-13
• 1.1 基本概念9-13
• 1.1.1 圖9
• 1.1.2 路與圖的連通性9-10
• 1.1.3 正則圖與完全二部圖10-11
• 1.1.4 子圖與生成子圖11-12
• 1.1.5 弦圖、n-太陽圖12-13
• 2 圖的彩虹支配問題發(fā)展13-19
• 2.1 支配的起源與發(fā)展13-14
• 2.2 支配的基本概念14
• 2.3 支配的計算復(fù)雜性14-16
• 2.4 支配集的應(yīng)用16
• 2.5 彩虹支配的研究進(jìn)展16-18
• 2.6 本文工作18
• 2.7 本章小結(jié)18-19
• 3 廣義循環(huán)圖C(n；{1,2})的2-彩虹支配問題19-27
• 3.1 廣義循環(huán)圖C(n；{1,2})的2-彩虹支配問題19-26
• 3.2 本章小結(jié)26-27
• 4 廣義循環(huán)圖C(n；{1，，3})的2-彩虹支配問題27-39
• 4.1 廣義循環(huán)圖C(n;{1,3})的2-彩虹支配數(shù)27-38
• 4.2 本章小結(jié)38-39
• 5 廣義循環(huán)圖C(n{1，2...,k})的2-彩虹支配問題39-46
• 5.1 廣義循環(huán)圖C(n;{1,2...,k})的2-彩虹支配問題39-45
• 5.2 本章小結(jié)45-46
• 6 總結(jié)46-47
• 7 展望47-48
• 致謝48-49
• 參考文獻(xiàn)49-53
• 作者簡介53

【參考文獻(xiàn)】

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

1 閻新芳,孫雨耕,胡華東;基于極大權(quán)的最小連通支配集啟發(fā)式算法[J];電子學(xué)報;2004年11期

2 朱藝華;沈毅俊;吳小燕;汪加才;;移動自組網(wǎng)電力及負(fù)荷感知的構(gòu)造最小連通支配集算法[J];電子學(xué)報;2006年11期

3 唐勇;周明天;;基于極大獨(dú)立集的最小連通支配集的分布式算法[J];電子學(xué)報;2007年05期

4 閻新芳;劉愛琴;楊挺;;基于極小獨(dú)立支配集的MANET虛擬骨干網(wǎng)算法[J];電子學(xué)報;2007年06期

5 邵澤輝;;網(wǎng)格圖的2-彩虹控制數(shù)[J];成都大學(xué)學(xué)報(自然科學(xué)版);2013年01期

6 彭偉,盧錫城;移動自組網(wǎng)絡(luò)中采用連通支配集的有效廣播技術(shù)(英文)[J];軟件學(xué)報;2001年04期

7 毛鶯池;馮國富;陳力軍;陳道蓄;;與位置無關(guān)的無線傳感器網(wǎng)絡(luò)連通性覆蓋協(xié)議[J];軟件學(xué)報;2007年07期

8 黃元江,湯德佑;傳感器網(wǎng)絡(luò)中基于連通支配集的路由算法[J];計算機(jī)工程與設(shè)計;2005年06期

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

1 趙承業(yè);圖的支配問題研究[D];大連理工大學(xué);2007年

2 付學(xué)良;若干類圖支配問題的研究[D];大連理工大學(xué);2008年

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

1 吉春年;廣義Petersen圖和循環(huán)圖的羅馬支配研究[D];大連理工大學(xué);2008年

2 羅梅琴;若干圖的等全著色及彩虹支配問題的研究[D];大連理工大學(xué);2008年

本文編號：1043632