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

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

2、畫(huà)不連通性的缺陷，進(jìn)而提出帶有連通分支點(diǎn)數(shù)上界的關(guān)鍵點(diǎn)問(wè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)問(wèn)題是NP-完全的，給出了其整數(shù)規(guī)劃數(shù)學(xué)模型;其次對(duì)于樹(shù)上比例型連通指數(shù)下的關(guān)鍵節(jié)點(diǎn)問(wèn)題，設(shè)計(jì)了一個(gè)多項(xiàng)式時(shí)間的動(dòng)態(tài)規(guī)劃算法，其時(shí)間復(fù)雜度為O(n4 log n)，并進(jìn)行了數(shù)值試驗(yàn).