門檻圖和擬門檻圖中的一些優(yōu)化問題.pdf

1、本文主要研究門檻圖和擬門檻圖的結構特點，并在此基礎上解決了這兩類圖中的一些優(yōu)化問題。 第一章中首先研究了門檻圖的結構，得出這類圖實質上是由一些單點的和或積得到的。認清這一結構性質后，本章設計了多項式時間算法構造出了反映門檻圖結構性質的兩種圖一門檻圖的中心樹Tc和樹形代表Td。然后，利用中心樹和樹形代表所反映的門檻圖的性質，本章解決了門檻圖中的以下優(yōu)化問題：(1)設計多項式時間算法識別門檻圖；(2)利用中心樹找出門檻圖的最大團，得

2、到門檻圖的最小邊割集是平凡的；(3)構造樹形代表，然后證明了樹形代表的葉子節(jié)點構成原圖的最大獨立子集；(4)給出門檻圖是哈密爾頓圖的充要條件；(5)設計多項式時間算法計算出門檻圖的帶寬。 第二章首先構造了擬門檻圖的樹形代表，同時由構造樹形代表的算法來識別擬門檻圖，因為一個圖是擬門檻圖當且僅當它是某個樹形圖的導出圖，而這個樹形圖就是該門檻圖的樹形代表。然后，出樹形代表出發(fā)來構造其中心樹，并在此基礎上解決了擬門檻圖中的以下優(yōu)化問題：