圖的控制劃分?jǐn)?shù).pdf

1、在過去的三十多年里，隨著計(jì)算機(jī)科學(xué)的迅速發(fā)展，圖論也得到了飛速發(fā)展，而控制數(shù)理論的研究是圖論中發(fā)展最快的幾個(gè)領(lǐng)域之一．控制數(shù)理論能夠快速發(fā)展的主要原因是它在組合優(yōu)化、編碼理論、計(jì)算機(jī)科學(xué)、通信網(wǎng)絡(luò)、監(jiān)視系統(tǒng)和社會網(wǎng)絡(luò)等理論與實(shí)踐中有著重要的應(yīng)用背景．隨著研究的深入和應(yīng)用的激發(fā)，各種新的參數(shù)不斷涌現(xiàn)．其中圖的控制劃分?jǐn)?shù)就是在圖的控制集的基礎(chǔ)上被提出的．由于圖的控制劃分?jǐn)?shù)在社會網(wǎng)絡(luò)的選址問題中有很多的應(yīng)用，越來越多的研究人員開始關(guān)注這個(gè)參數(shù)

2、． 長期以來，圖的控制劃分?jǐn)?shù)(d(G))和全控制劃分?jǐn)?shù)(d<,t>(G))一直受到關(guān)注．之后，由于圖的控制函數(shù)的概念的引入，人們開始借助函數(shù)性質(zhì)來研究控制劃分?jǐn)?shù)．本文主要研究了符號全控制劃分?jǐn)?shù)(d<'s><,t>(G))，并且給出了一些關(guān)于符號控制劃分?jǐn)?shù)(d<,s>(G))和符號全控制劃分?jǐn)?shù)(d<'s><,t>(G))的Nordhaus-Gaddum型結(jié)果． 其相應(yīng)的結(jié)果分為以下兩部分： 第一部分，首先定義了圖的

3、符號全控制劃分?jǐn)?shù)；接著給出了它的一些基本性質(zhì)和它在正則圖上的可達(dá)界，同時(shí)得到了在完全圖上和在一些特殊圖上的符號全控制劃分?jǐn)?shù)． (有關(guān)結(jié)果被《Journal of Shanghai University》錄用) 第二部分，建立了圖的符號控制劃分?jǐn)?shù)與其補(bǔ)圖的符號控制劃分?jǐn)?shù)兩者的和的上界，并且對達(dá)到上界的極圖進(jìn)行了刻畫，同時(shí)得到了這兩個(gè)參數(shù)的積的下可達(dá)界和上界；然后給出了圖的符號全控制劃分?jǐn)?shù)與其補(bǔ)圖的符號全控制劃分?jǐn)?shù)兩者的和的可達(dá)上界