【摘要】：對于強連通有向圖D(V,X)而言,D的一個強連通支撐子圖H,若對于Va ∈H,子圖H-a都不具有強連通性,那么稱H為極小強連通支撐子圖.類比于連通圖中的支撐樹,容易看出一個強連通有向圖D包含多個極小強連通支撐子圖.我們稱D的所有極小強連通支撐子圖中包含弧最少的為最小強連通支撐子圖DM.對于尋找強連通有向圖D的最小強連通支撐子圖DM的問題我們稱其為MSSS問題.在許多情況下解決強連通有向圖D的MSSS問題是非常有用的,但是這個問題很難實現(xiàn),因為若D包含哈密爾頓圈,那么我們就必須尋找D的哈密爾頓圈.在本文中,我們進一步研究了兩類重要的可以找到其最小強連通支撐子圖的強連通有向圖.本文第一章首先介紹了最小強連通支撐子圖問題的研究背景,其次介紹了本文的基本定義和符號,最后簡述了本文研究的核心問題,研究進展及本文的主要結(jié)果.本文第二章主要是確定了本文的主要研究方法.在第一節(jié)給出了可刪弧的定義,這也是我們研究方法和算法所涉及的核心定義,第二節(jié)利用深度優(yōu)先搜索算法確定可刪弧集,第三節(jié)利用可刪弧集內(nèi)部的相關(guān)性定義一個由強連通有向圖D(V,X)的可刪弧集A(D)決定的無向圖GA,并將我們尋找強連通有向圖D(V,X)的最小強連通支撐子圖DM問題轉(zhuǎn)化為計算無向圖GA的最大獨立集問題.本文第三章與第四章,我們會結(jié)合第二章給出的算法解決這兩個重要圖類的MSSS問題,更精確的說,當(dāng)可刪弧集A(D)所構(gòu)造的無向圖GA是Kneser圖或者區(qū)間圖,我們就可以利用算法在多項式時間內(nèi)計算出強連通圖D的最小強連通支撐子圖所包含弧的數(shù)量或者找出其最小強連通支撐子圖.
【學(xué)位授予單位】：安徽大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2018
【分類號】：O157.5

【相似文獻】

相關(guān)期刊論文 前10條

1 崔秋月;劉娟;董暢暢;;超歐拉和雙有向跡的強積有向圖[J];四川師范大學(xué)學(xué)報(自然科學(xué)版);2018年04期

2 原軍;劉愛霞;;局部內(nèi)(外)半完全有向圖可跡的充分條件[J];應(yīng)用數(shù)學(xué)學(xué)報;2016年02期

3 韓婷婷;李瑞娟;;圓有向圖中的泛弧[J];貴州師范大學(xué)學(xué)報(自然科學(xué)版);2017年01期

4 鄧婕;池宏;許保光;;基于有向圖相似的應(yīng)急響應(yīng)程序模塊化問題研究[J];中國管理科學(xué);2017年04期

5 崔秋月;劉娟;;關(guān)于超歐拉的冪有向圖[J];廊坊師范學(xué)院學(xué)報(自然科學(xué)版);2017年03期

6 董暢暢;劉娟;;超歐拉路可合并有向圖及半完全有向圖（英文）[J];新疆師范大學(xué)學(xué)報(自然科學(xué)版);2017年03期

7 崔建;葉旺;;圓有向圖的(1,2)步競爭圖中存在哈密爾頓圈的條件[J];重慶工商大學(xué)學(xué)報(自然科學(xué)版);2017年06期

8 盧永紅;;循環(huán)有向圖的距離和與平均距離[J];山西師范大學(xué)學(xué)報(自然科學(xué)版);2014年01期

9 張新鴻;李瑞娟;李勝家;;圓有向圖的(i,κ)步競爭圖[J];應(yīng)用數(shù)學(xué)學(xué)報;2013年06期

10 張新鴻;李瑞娟;李勝家;;關(guān)于強哈密爾頓連通有向圖的一個反例[J];山西大學(xué)學(xué)報(自然科學(xué)版);2012年01期

相關(guān)會議論文 前10條

1 李剛;童

本文編號：2799350