圖的定位控制集與識(shí)別碼.pdf

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

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