兩類控制參數(shù)在特殊圖類上的算法研究.pdf_第1頁
已閱讀1頁，還剩46頁未讀， 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領(lǐng)

文檔簡介

1、在過去的三十多年里，隨著計算機科學(xué)的迅速發(fā)展，圖論也得到了飛速發(fā)展，而圖論中發(fā)展最快的領(lǐng)域也許就是控制數(shù)理論的研究.控制數(shù)理論能夠快速發(fā)展的主要原因是它在現(xiàn)實世界中，例如編碼理論、計算機科學(xué)、通信網(wǎng)絡(luò)、監(jiān)視系統(tǒng)和社會網(wǎng)絡(luò)等理論與實踐中有著廣泛而深刻的應(yīng)用背景. 設(shè)圖G=(V(G)，E(G))為簡單無向圖，V(G)和E(G)分別為圖G的頂點集和邊集.設(shè)D()V(G)，若V(G)\D中的每一個點至少與D的某一個頂點相鄰接，也即N[D

2、]=V(G)，則稱D為G的控制集.1998年，Haynes和Slater基于某類應(yīng)用背景提出了配對控制集的概念.2000年，Hedetniemi，Hedetniemi和Rall提出了圖的無圈控制集問題.集S()V稱為G的配對控制集(無圈控制集)，如果S是G的控制集且導(dǎo)出子圖存在完美匹配(不含有圈). 控制相關(guān)參數(shù)的算法復(fù)雜性問題作為控制數(shù)理論研究中的一個重要領(lǐng)域，受到了越來越多的研究人員的關(guān)注.不過，對于任意圖，幾乎所有的

3、控制相關(guān)參數(shù)問題均是NP-完全的.即使一個問題被證明是NP-完全的，人們?nèi)匀挥锌赡艿玫酱藛栴}的特定實例的多項式算法.(例如，對于任意圖具有NP-完全性的控制數(shù)問題已經(jīng)被證明在樹、區(qū)間圖、AT-free圖上是多項式可解的.)本文主要研究了兩類新型控制參數(shù)(配對控制數(shù)和無圈控制數(shù))在特殊圖類的算法復(fù)雜性問題，主要工作分為兩個部分： 第一部分，由于任意圖的配對控制集問題具有NP-完全性，作者考慮了AT-free圖類.在研究了AT-fr

4、ee圖類的結(jié)構(gòu)性質(zhì)的基礎(chǔ)上，給出了配對控制集在AT-free圖的BFS-樹上分布的結(jié)構(gòu)性質(zhì).利用這些性質(zhì)，給出了求解AT-free圖類最小配對控制集的多項式時間算法. 第二部分，針對文[41]中提出的一些公開問題，同時在注意到無圈控制集問題對于二部圖都是NP-完全的這一事實基礎(chǔ)上，研究了二部圖的一個子類二部置換圖的無圈控制集問題.當限定在二部置換圖上時，證明了無圈控制數(shù)等于其控制數(shù)(γa(G)=γ(G)).利用此結(jié)論給出了二部置

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論