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

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

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

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

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

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