發(fā)布時間：2017-10-13 03:31

  本文關(guān)鍵詞：某些網(wǎng)絡(luò)的距離控制數(shù)

  更多相關(guān)文章： 距離控制數(shù) 控制數(shù) NPC NP-hard 笛卡爾乘積圖

【摘要】：圖論是離散數(shù)學(xué)的一個重要分支,它是現(xiàn)代電子計算機的理論基礎(chǔ),不論在理論上還是在現(xiàn)實中都扮演著重要的角色。圖論的發(fā)展具有悠久的歷史的,自歐拉首次給出柯尼斯堡七橋問題開始,圖論吸引了一大批學(xué)者的關(guān)注與研究,不斷的新的問題的提出與解決給圖論發(fā)展帶來了源源不斷的動力與樂趣。本文主要研究一些具有簡單結(jié)構(gòu)的、常見的圖類的距離控制數(shù)。在計算機網(wǎng)絡(luò)中,控制數(shù)具有重要的應(yīng)用,它表示控制整個網(wǎng)絡(luò)的所需要的最少的點數(shù),也就是所需要的最小費用。因而研究控制數(shù)具有重要的理論和現(xiàn)實意義。與控制數(shù)相關(guān)的一個重要概念就是束縛數(shù),它是網(wǎng)絡(luò)安全性能的一個重要指標(biāo)。距離控制數(shù)和距離束縛數(shù)是經(jīng)典的控制數(shù)和束縛數(shù)的自然推廣,具有更加廣闊的現(xiàn)實背景和意義。但確定一個圖的距離控制數(shù)是一個NPC問題。因此,確定一些典型圖類的距離控制數(shù)以及它們的界就顯得尤為重要。這能為進(jìn)一步確定其他復(fù)雜結(jié)構(gòu)的圖的距離控制數(shù)提供重要的界的依據(jù)。 本文第一章介紹了圖論中必要的基本概念,以及控制數(shù)、束縛數(shù)的現(xiàn)實背景。 第二章確定了與路相關(guān)的幾種笛卡爾乘積圖Pn, Pn×P2,Pn×P3,Pn×Km的k-距離控制數(shù)。 第三章確定了與圈相關(guān)的圖Cn, Cn×P2,Cn×P3,Cn×Km的k-距離控制數(shù)。
【關(guān)鍵詞】：距離控制數(shù) 控制數(shù) NPC NP-hard 笛卡爾乘積圖
【學(xué)位授予單位】：中國科學(xué)技術(shù)大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：O157.5
【目錄】：

• 摘要5-6
• Abstract6-7
• 目錄7-9
• 第一章 緒論9-21
• 1.1 圖論的歷史背景9
• 1.2 圖論的一些基本概念9-16
• 1.3 控制數(shù)16-18
• 1.4 束縛數(shù)18-19
• 1.5 本文工作19-21
• 第二章 與路相關(guān)的笛卡爾乘積圖的距離控制數(shù)21-29
• 2.1 k-距離控制集的性質(zhì)21-22
• 2.2 P_n×P_2的距離控制數(shù)22-24
• 2.3 P_n×K_m的距離控制數(shù)24-26
• 2.4 圖P_n×P_3的距離控制數(shù)26-29
• 第三章 與圈相關(guān)的圖的距離控制數(shù)29-37
• 3.1 關(guān)于C_n的距離控制數(shù)29
• 3.2 C_n×P_2的距離控制數(shù)29-33
• 3.3 關(guān)于P_n×K_m及P_n×P_3的距離控制數(shù)33-37
• 參考文獻(xiàn)37-39
• 致謝39

【參考文獻(xiàn)】

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

1 管梅谷;中國投遞員問題綜述[J];數(shù)學(xué)研究與評論;1984年01期

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

1 李寧;圖的控制問題研究[D];中國科學(xué)技術(shù)大學(xué);2011年

2 胡夫濤;圖的約束數(shù)研究[D];中國科學(xué)技術(shù)大學(xué);2012年

，

本文編號：1022606