幾類控制參數(shù)之間的關(guān)系.pdf

1、控制數(shù)理論的研究是圖論中一個活躍的方向，尤其在計算機科學和網(wǎng)絡(luò)通訊技術(shù)方向有廣泛的應用。關(guān)于控制數(shù)理論的研究主要集中于下列幾個方面： (1)各種控制參數(shù)之間的關(guān)系的研究； (2)各種控制參數(shù)的界的確定及其界的相互之間關(guān)系的研究； (3)各種控制參數(shù)的計算復雜性的研究及其算法設(shè)計。 本文討論了圖的幾類控制參數(shù)的界的估計問題。內(nèi)容分為： 第一章引言。 第二章給出了圖的預備知識以及各控制參數(shù)的定

2、義及基本性質(zhì)。 第三章介紹了各類k-控制參數(shù)的定義及基本結(jié)論。主要的結(jié)論是證明了k-連通控制數(shù)的一個關(guān)聯(lián)不等式，即：如果G是連通圖，證明了γck(G)≤(2k+k+1/2)irk(G)-2k，其中γkc(G)表示G的k-連通控制數(shù)，irk(G)表示G的無贅數(shù)。當k=1時，這個結(jié)論即退化為[25]中的結(jié)論。 第四章討論了幾類控制參數(shù)的Nordhaus-Gaddum結(jié)果。設(shè)是圖G的一個參數(shù)λ(G)，關(guān)于λ(G)，λ(-G)的