Halin圖及小樹寬圖若干算法的研究.pdf

1、在平面上嵌入一棵樹T，T的每個內部頂點的度數至少為3并且T至少有一個內部頂點。作一個圈C連接T的所有葉頂點，T的所有葉頂點組成C上的所有頂點。這樣得到的平面圖稱為Halin圖。樹T稱為Halin圖的特征樹，圈C稱為Halin圖的伴隨圈。通常用H=7∪C表示一個Halin圖。 本文主要研究了Halin圖及小樹寬圖的幾個相關算法。論文第一章主要介紹相關概念和術語。對Halin圖和小樹寬的歷史和研究現狀做了介紹。第二到四章詳細介紹了利

2、用動態(tài)規(guī)劃和壓縮扇的方法求解Halin圖中的三個問題，并設計了線性時間的算法解決這些問題。第五章研究了小樹寬圖上的全一問題。 本文主要研究了Halin圖中的以下三個算法： (1)找最大權對集問題是著名的分派問題，并能得到最佳利益。在一個賦權一般圖上求解一個最大權完美對集的問題的算法的時間復雜度是O(|V|E|log|V|)。第二章解決了在一個賦權Halin圖上，尋找具有最大權的對集和完美對集、幾乎完美對集等問題，并給出線

3、性時間的算法。 (2)圖G=(V,E)，正整數K≤|V|。G的頂點是否能劃分成K個不相交的集合V<,1>，V<,2>…V<,K>，使得對于i∈{1，…，K}，由V<,i>誘導的子圖是一個完美對集。這個問題是一個NP完全問題。本文第三章首先證明出在Halin圖上2≤K≤4，然后給出相關算法。算法的時間復雜度是0(|V|)。 (3) 一個網絡可以表示為無向圖G=(V, E，d)其中V是頂點的集合， E是邊的集合，d是邊的費用

4、函數d：E→R。S是V的子集， 2≤|S|≤|V|。Steiner樹問題就是尋找G的一棵子樹T<,S>=(V，E，d)，S V V,E’E,并且使花費d(Ts)=∑<,e∈E’>d(e)最小。求Steiner樹問題是NP完全問題。本文第四章中把這個問題限制到Halin圖上，并給出線性時間算法。 Halin圖實際上是一種樹寬≤3的圖。樹寬是一種測量圖與樹的相似度的參數。許多圖都有常數上界的樹寬。例如，樹和森林的樹寬≤1，系列平行

5、圖和外平面圖的樹寬≤2，Halin圖的樹寬≤3。最后我們把Halin圖擴展到小樹寬(≤4)的圖上，進行最小全一問題的求解。 全一問題可以如下描述：假定一個n×n的棋盤的每個方格內安裝有一個電燈和一個按鈕。按下某個方格內的按鈕，將使這個方格內的電燈由亮變滅或者由滅變亮，而且會使與這個方格有邊相鄰的方格內的電燈也同樣改變。 如果初始狀態(tài)所有電燈都是滅的，那么是否可以通過按下一組按鈕，使得最終棋盤上的所有電燈都處于亮的狀態(tài)?這