新的連通指數(shù)下的關(guān)鍵節(jié)點(diǎn)問題.pdf

1、本文研究的是關(guān)鍵節(jié)點(diǎn)問題:在一個(gè)無向圖中，刪除不超過K個(gè)節(jié)點(diǎn)的集合，使得剩余圖在某種意義下盡可能的分裂.文中主要討論了兩種類型的關(guān)鍵節(jié)點(diǎn)問題,提出了相應(yīng)的算法和數(shù)值試驗(yàn).
　　第一章介紹了關(guān)鍵節(jié)點(diǎn)問題的重要意義和國內(nèi)外研究概況，并列出了本文研究所需要的預(yù)備知識(shí).
　　第二章研究了樹上帶有連通分支點(diǎn)數(shù)上界的關(guān)鍵節(jié)點(diǎn)問題.首先介紹了樹上MaxNum型和MinMaxC型關(guān)鍵點(diǎn)問題的動(dòng)態(tài)規(guī)劃算法.接著分析了MaxNum型關(guān)鍵點(diǎn)問題刻

2、畫不連通性的缺陷，進(jìn)而提出帶有連通分支點(diǎn)數(shù)上界的關(guān)鍵點(diǎn)問題.最后設(shè)計(jì)一種多項(xiàng)式時(shí)間動(dòng)態(tài)規(guī)劃算法，分析其時(shí)間復(fù)雜度為O（n4），并進(jìn)行數(shù)值試驗(yàn)和幾種算法的結(jié)果分析.
　　第三章提出一個(gè)新的比例型連通指數(shù)，證明了一般圖上比例型連通指數(shù)下的關(guān)鍵節(jié)點(diǎn)問題是NP-完全的，給出了其整數(shù)規(guī)劃數(shù)學(xué)模型;其次對(duì)于樹上比例型連通指數(shù)下的關(guān)鍵節(jié)點(diǎn)問題，設(shè)計(jì)了一個(gè)多項(xiàng)式時(shí)間的動(dòng)態(tài)規(guī)劃算法，其時(shí)間復(fù)雜度為O(n4 log n)，并進(jìn)行了數(shù)值試驗(yàn).