某些圖類的k-距離控制數(shù)與k-距離約束數(shù).pdf

1、圖論是數(shù)學(xué)的一個(gè)分支，特別是離散數(shù)學(xué)的一個(gè)重要分支。本文主要研究一些圖類的k-距離控制數(shù)和k-距離約束數(shù)。在網(wǎng)絡(luò)中，控制數(shù)是控制整個(gè)網(wǎng)絡(luò)的最小費(fèi)用，因而研究控制數(shù)具有顯著的理論意義和現(xiàn)實(shí)意義。約束數(shù)是網(wǎng)絡(luò)安全性能的一個(gè)重要參數(shù)。k-距離控制數(shù)和k-距離約束數(shù)作為控制數(shù)和約束數(shù)的自然推廣同樣具有重要的理論意義和現(xiàn)實(shí)意義。但對(duì)于一般的圖，確定它的k-距離控制數(shù)卻是一個(gè)NPC問(wèn)題，因而確定某些圖類的k-距離控制數(shù)和k-距離約束數(shù)以及確定他們的

2、界就顯得尤為重要。
　　本文在在第一章介紹了本文中所用到的關(guān)于圖論的基本概念。
　　第二章給出了給出了關(guān)于路Pn，路的笛卡爾乘積圖Pn×K2以及與路相關(guān)的一些圖的k-距離控制數(shù)。
　　第三章給出了關(guān)于圈Cn、圈的笛卡爾乘積圖Cn×K2以及與圈相關(guān)的圖的k-距離控制數(shù)，并證明了一般的圖G與它的兩種變形圖S'(G)和D'(G)的k-距離控制數(shù)的關(guān)系。
　　第四章給出了關(guān)于路Pn、圈Cn及Pn×K2的k-距離約束數(shù)，利