圖的邊控制函數(shù)和全控制函數(shù).pdf

1、隨著計算機科學(xué)的迅速發(fā)展，圖論隨之也得到了飛速發(fā)展，而近幾十年來圖的控制數(shù)理論成為圖論中發(fā)展最快的領(lǐng)域之一。控制數(shù)理論能夠快速發(fā)展的主要原因是它在組合優(yōu)化、編碼理論、計算機科學(xué)、通信網(wǎng)絡(luò)、監(jiān)視系統(tǒng)和社會網(wǎng)絡(luò)等理論與實踐中有著重要的應(yīng)用背景。圖的函數(shù)(全)控制數(shù)是經(jīng)典(全)控制數(shù)概念的一類自然推廣。由于函數(shù)的引入，致使利用函數(shù)性質(zhì)來研究(全)控制數(shù)成為可能。目前，函數(shù)控制數(shù)已成為圖的控制集理論中一個嶄新而富有挑戰(zhàn)性的研究方向。 人

2、們已發(fā)現(xiàn)，對任意圖已定義的幾類函數(shù)控制數(shù)的判定問題均是NP-完全的，所以對它們的上、下界進行估計以及對其極值圖結(jié)構(gòu)的刻畫成為十分有意義的問題。本文研究了幾類函數(shù)全控制數(shù)，其主要結(jié)果分為以下兩部分： 第一部分(第三章)，首先建立了任意圖的符號邊全控制數(shù)(γ'st(G))的幾個下界，接著得到了完全圖和完全偶圖的符號邊全控制數(shù)(γ'st(G))，這些結(jié)果是全新的；(有關(guān)結(jié)果被《International Journal of Pure