圖的控制集的一些相關(guān)問題的研究.pdf

1、控制集是圖論中的重要概念，它定義為圖中的一個(gè)點(diǎn)集，使得圖中其它任何一點(diǎn)都與該點(diǎn)集中的某點(diǎn)相鄰。這一概念的提出始于Komg、Berge和Ore，他們的著作和Cockayne，Hedetniemi，以及Larskar和Walikar等人的文章為后來的研究者提供了有益的啟示。在過去的30多年里，對(duì)圖的各類控制集參數(shù)問題以及控制參數(shù)與圖的其他參數(shù)的關(guān)系問題的研究已經(jīng)成為圖論研究的一個(gè)重要領(lǐng)域.在此期間，各種新的控制參數(shù)被不斷提出，如具有“連通性

2、”的控制集，具有“距離控制性”的控制集，具有“無贅性”的控制集等等，本文在連通控制集和距離控制集的基礎(chǔ)上引入一種新的控制集-“[γ，R]-控制集”，并從算法的角度來討論它的性質(zhì)。如何尋找圖的最小控制集是一個(gè)NP困難問題，它不能通過回溯法或隨機(jī)化算法有效地解決，在這種情況下，對(duì)于其中的一些問題，代之以設(shè)計(jì)近似算法，我們要保證它是一個(gè)多項(xiàng)式時(shí)間算法，并且能得到一個(gè)近似于最優(yōu)解的“合理”的解.對(duì)于最小化問題，算法的近似解與最優(yōu)解的比值稱為算法

3、的近似比。近似比與1越靠近，算法所得的解就與最優(yōu)解越接近。遺憾的是，并不是所有問題都能找到近似比為常數(shù)的近似算法，比如，已經(jīng)證明：在P≠NP的前提下，最小控制集問題就不可能找到比O(lnn)更好的算法。 本研究首先引入[γ，R]-控制集的準(zhǔn)確定義，然后對(duì)一般圖中的最小[γ，R]-控制集問題提出了一個(gè)近似比為ln△γ+[2γ+1/R]-1的算法，這已經(jīng)與O(lnn)同階，可以認(rèn)為，在一般圖中，其改進(jìn)的余地已經(jīng)很小.然后我們分別考慮

4、圖的[γ，R]-控制數(shù)與圖的大小的關(guān)系、圖的[γ，R]-控制數(shù)與其補(bǔ)圖的[γ，R]-控制數(shù)的關(guān)系、圖的[γ，R]-控制集與全控制集的關(guān)系，得到了圖的[γ，R]-控制數(shù)的三個(gè)不同上界。從實(shí)際應(yīng)用出發(fā)，將最小[γ，R]-控制集限定在單位圓盤圖中，考慮單位圓盤圖中的特殊幾何結(jié)構(gòu)，得到了近似比為[4γ(γ+1)(1-2θ-sin2θ/π)]『γ+1/R](常數(shù))的算法，其中θ=arccosR/2γ+1.在γ，R取特殊參數(shù)的情況下，對(duì)算法的近似比