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

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

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

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