直線簇上區(qū)間圖的兩類控制參數(shù)的算法.pdf

1、圖的控制數(shù)理論是圖論中一個(gè)重要的研究領(lǐng)域，它在計(jì)算機(jī)科學(xué)，通訊科學(xué)，網(wǎng)絡(luò)理論，電力系統(tǒng)，社會(huì)學(xué)，特別是在計(jì)算機(jī)網(wǎng)絡(luò)和通訊系統(tǒng)研究中有著廣泛應(yīng)用。我們稱點(diǎn)集S()V為圖G=(V,E)的控制集如果對(duì)任意的點(diǎn)v∈V-S，總存在S中的一個(gè)點(diǎn)與v鄰接。圖G的控制數(shù)γ(G)是圖G的控制集的最小基數(shù)。在圖的控制數(shù)理論研究中，算法復(fù)雜性研究是一個(gè)十分活躍的研究方向，其中一項(xiàng)重要工作是在特殊圖類上尋找控制數(shù)及其相關(guān)參數(shù)的有效算法。區(qū)間圖是一類著名的特殊圖

2、類，它形成弦圖和完美圖的子類，它們?cè)诮鉀Q很多現(xiàn)實(shí)問(wèn)題中有重要作用。由于區(qū)間圖具有良好的結(jié)構(gòu)性質(zhì)，因此許多NP-完全的控制數(shù)及其相關(guān)參數(shù)問(wèn)題限制在區(qū)間圖上都是多項(xiàng)式時(shí)間可解的。本文主要研究了兩類控制參數(shù)在區(qū)間圖上的算法問(wèn)題，分為兩個(gè)部分。 第一部分：研究了直線簇上區(qū)間圖的最小獨(dú)立控制集和最小連通控制集的求解問(wèn)題。人們已經(jīng)證明：許多控制相關(guān)參數(shù)如獨(dú)立控制數(shù)，連通控制數(shù)，全控制數(shù)的求解問(wèn)題，當(dāng)限制在一條直線上區(qū)間圖時(shí)，基本上都有線性時(shí)

3、間算法。本文研究了廣義區(qū)間圖的情況，即多條直線上(直線簇)的區(qū)間圖的最小獨(dú)立控制集和最小連通控制集的求解問(wèn)題。對(duì)給定的直線簇上區(qū)間圖的兩個(gè)模型，分別給出了求解上述兩類問(wèn)題的多項(xiàng)式時(shí)間算法。 第二部分：研究了包含賦權(quán)點(diǎn)的區(qū)間圖的最小獨(dú)立控制集和最小連通控制集的求解問(wèn)題。對(duì)一條直線上的區(qū)間圖，其上有n個(gè)區(qū)間和t個(gè)賦權(quán)點(diǎn)，要找此區(qū)間圖的最小獨(dú)立控制集(最小連通控制集)，使得其覆蓋的點(diǎn)權(quán)和最大。利用動(dòng)態(tài)規(guī)劃方法，給出了求解此區(qū)間圖的最大