強(qiáng)連通有向圖的MSSS問題--Kneser圖，區(qū)間圖.pdf

1、對于強(qiáng)連通有向圖D(V,X)而言，D的一個(gè)強(qiáng)連通支撐子圖H，若對于(V)a∈H，子圖H-a都不具有強(qiáng)連通性，那么稱H為極小強(qiáng)連通支撐子圖.類比于連通圖中的支撐樹，容易看出一個(gè)強(qiáng)連通有向圖D包含多個(gè)極小強(qiáng)連通支撐子圖.稱D的所有極小強(qiáng)連通支撐子圖中包含弧最少的為最小強(qiáng)連通支撐子圖DM·對于尋找強(qiáng)連通有向圖D的最小強(qiáng)連通支撐子圖DM的問題稱其為MSSS問題.在許多情況下解決強(qiáng)連通有向圖D的MSSS問題是非常有用的，但是這個(gè)問題很難實(shí)現(xiàn)，因?yàn)?/p>

2、若D包含哈密爾頓圈，那么就必須尋找D的哈密爾頓圈.在本文中，進(jìn)一步研究了兩類重要的可以找到其最小強(qiáng)連通支撐子圖的強(qiáng)連通有向圖.
　　本文第一章首先介紹了最小強(qiáng)連通支撐子圖問題的研究背景，其次介紹了本文的基本定義和符號(hào)，最后簡述了本文研究的核心問題，研究進(jìn)展及本文的主要結(jié)果.
　　本文第二章主要是確定了本文的主要研究方法.在第一節(jié)給出了可刪弧的定義，這也是研究方法和算法所涉及的核心定義，第二節(jié)利用深度優(yōu)先搜索算法確定可刪弧集，

3、第三節(jié)利用可刪弧集內(nèi)部的相關(guān)性定義一個(gè)由強(qiáng)連通有向圖D(V,X)的可刪弧集A(D)決定的無向圖GA，并將尋找強(qiáng)連通有向圖D(V,X)的最小強(qiáng)連通支撐子圖DM問題轉(zhuǎn)化為計(jì)算無向圖GA的最大獨(dú)立集問題.
　　本文第三章與第四章，會(huì)結(jié)合第二章給出的算法解決這兩個(gè)重要圖類的MSSS問題，更精確的說，當(dāng)可刪弧集A(D)所構(gòu)造的無向圖GA是Kneser圖或者區(qū)間圖，就可以利用算法在多項(xiàng)式時(shí)間內(nèi)計(jì)算出強(qiáng)連通圖D的最小強(qiáng)連通支撐子圖所包含弧的數(shù)量