圖的控制參數(shù)和一類極值問題.pdf

1、圖的某些參數(shù),如圖的控制參數(shù),因?yàn)槠湓趫D論的研究以及現(xiàn)實(shí)世界的各種應(yīng)用中固有的重要性,而得到廣泛的研究和發(fā)展.圖的控制集定義為圖中的一個(gè)點(diǎn)的集合,使得圖中其它任何一個(gè)點(diǎn)都與該點(diǎn)集中的某個(gè)點(diǎn)鄰接.確定圖的控制集問題在網(wǎng)絡(luò)的目標(biāo)、安全裝置和便利設(shè)施等的定位的方面有很大用處.在過去的30多年里,對(duì)圖的各種控制參數(shù)的研究已經(jīng)成為圖論研究的一個(gè)重要領(lǐng)域,迄今為止關(guān)于圖的控制參數(shù)問題的研究已有上千篇文章,現(xiàn)在已有近百種類型的控制形式得到研究.該文主

2、要工作包括以下幾個(gè)方面:(1)簡單介紹了幾種常見的控制參數(shù)的概念和應(yīng)用,以及它們的上下界和相互關(guān)系;(2)討論了連通圖G的連通k-控制數(shù)γ<'c><,k>(G)的上下界,并證明了不等式γ<'c><,k>(G)≤(2k+k+1/2)ir<,k>(G-2K);(3)給出在樹和單圈圖中,2-控制數(shù)和連通2-控制數(shù)相等的充分必要條件,并加以證明;(4)討論了給定連數(shù)和頂點(diǎn)數(shù)的圖的一類極值問題.對(duì)于所有給定邊數(shù)和頂點(diǎn)數(shù)的圖,我們將刻畫出其所有頂點(diǎn)