圖的控制數(shù)理論中的概率方法.pdf

1、在近四十年來，隨著計(jì)算機(jī)科學(xué)和網(wǎng)絡(luò)通訊技術(shù)的迅速發(fā)展，圖論也得到了飛速發(fā)展，而控制數(shù)理論的研究是圖論中發(fā)展最快的幾個(gè)領(lǐng)域之一.控制數(shù)理論能夠快速發(fā)展的主要原因是它在組合優(yōu)化、編碼理論、計(jì)算機(jī)科學(xué)、通信網(wǎng)絡(luò)、監(jiān)視系統(tǒng)和社會(huì)網(wǎng)絡(luò)等理論與實(shí)踐中有著重要的作用. 對(duì)任意圖，人們發(fā)現(xiàn)幾乎所有的控制參數(shù)的判定問題均是NP-完全的，所以對(duì)它們的上、下界進(jìn)行精確估計(jì)以及極值圖的刻畫成為十分有趣的問題.由于概率方法在圖參數(shù)的界的估計(jì)方面具有獨(dú)特的

2、作用，因此借助概率方法研究控制數(shù)的界一直受到關(guān)注.本文主要用概率方法研究了幾類控制數(shù)的界. 本文的主要內(nèi)容和結(jié)果分為以下三部分： 第一部分，首次利用組合差異分析理論中的部分著色方法得到任意圖上的符號(hào)全控制數(shù)的概率結(jié)果(有關(guān)結(jié)果被《Ars Cornbinatoria》錄用). 第二部分，利用經(jīng)典的概率方法得到限制控制數(shù)的一個(gè)全新的上界. 第三部分，首先得到了路和圈上負(fù)邊全控制數(shù)的精確值，然后得到了任意圖的負(fù)