圖的定位控制集與識別碼.pdf

1、眾所周知，由于圖的控制集理論在組合優(yōu)化、編碼理論、計算機科學(xué)、通信網(wǎng)絡(luò)、監(jiān)視系統(tǒng)和社會網(wǎng)絡(luò)等領(lǐng)域重要的應(yīng)用，使它成為近幾十年來圖論中發(fā)展最快的領(lǐng)域之一.隨著研究的深入和應(yīng)用的激發(fā)，各種新的控制參數(shù)不斷涌現(xiàn).其中圖的定位控制集(也稱為定位控制碼)和識別碼就是在控制集的基礎(chǔ)上被提出來的.圖的定位控制集和識別碼已成為編碼理論中較活躍的研究方向，它在通訊網(wǎng)絡(luò)和監(jiān)視系統(tǒng)中有廣泛的應(yīng)用. 由于任意圖的最小定位控制碼和識別碼的判定問題均是NP

2、-完全的，所以對這兩類碼的上、下界的估計、極值圖的刻畫、特殊圖上算法的設(shè)計和尋找其近似算法成為人們很感興趣的問題.本文主要研究了定為控制集和識別碼的界，其主要研究的結(jié)果如下： 第一部分，首先給出了圖的定位控制集和容錯定位控制集的概念，接著給出了它們的一些基本性質(zhì)，得到了容錯定位控制集在幾類有限圖和無限三角形格子圖中的一些界.接著我們在海明空間中對定位控制集進行了相關(guān)研究.(有關(guān)結(jié)果被《上海大學(xué)學(xué)報》錄用)第二部分，研究了圖的識別