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

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

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