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

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

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