1、本論文研究了圖論領(lǐng)域的兩個問題及其應(yīng)用：小樹寬圖和對集可擴圖。 近二十五年來，樹寬這一概念在圖論算法研究的許多方面起到了重要的作用。小樹寬圖在眾多領(lǐng)域都有應(yīng)用。許多通信網(wǎng)絡(luò)的拓撲結(jié)構(gòu)都是小樹寬圖。在化學(xué)領(lǐng)域，對LIGAND數(shù)據(jù)庫里面9712種化合物計算樹寬后發(fā)現(xiàn)：除一個外，其余物質(zhì)結(jié)構(gòu)圖的樹寬都不大于3；例外物質(zhì)的樹寬為4。使用常用編程語言(例如C語言)編寫的不含goto語句的程序，其控制流圖的樹寬以一個小常數(shù)為上界。

2、Halin圖的樹寬不大于3。由于Halin圖是對環(huán)形和樹形網(wǎng)絡(luò)一種非平凡的概括，本文研究了Halin圖中與網(wǎng)絡(luò)路由相關(guān)的幾個問題。 第二章解決了Halin圖中費用最優(yōu)的Hamilton路的問題。Hamilton路問題有三個版本：不指定端點、指定一個端點和指定兩個端點。論文給出了求解三個版本最優(yōu)Hamilton路的線性時間算法。 第三章探討了Halin圖中圈覆蓋問題。一個圖的圈覆蓋是一組圈使得圖中所有的選定頂點至少在這組圈

3、的一個圈中。圈覆蓋問題起源于環(huán)形光纖通信網(wǎng)絡(luò)的設(shè)計：采用一系列的圈去覆蓋要傳輸數(shù)據(jù)的子網(wǎng)絡(luò)。除了兩個版本的最優(yōu)圈覆蓋問題以外，本文還解決了用一個費用最優(yōu)的2-邊連通子圖去覆蓋給定頂點集的問題。針對本章的三個問題，論文都給出了線性時間的算法。 第四章研究了并行計算環(huán)境中樹分解的根選取問題。樹分解是圖論中最重要的幾個分解之一。在小樹寬圖上求解問題，第一步就是求解給定圖的樹分解。并行計算樹分解的一個先決條件就是為樹分解選定一個根。并且

4、根的選擇會影響處理時間。論文給出了求解使完成時間最早的根的算法，算法的時間復(fù)雜度為O(d|V(T)|)，其中d是樹T中最長路的長度。第五章給出了判定1-可擴圖的算法。最壞情況下，算法是O(|V||E|)時間的。該算法的復(fù)雜度與目前最快的由Carvalho和Cheriyan提出的算法是一樣的。但是本文的算法要比后者簡單很多。此外，論文給出了算法實現(xiàn)的細節(jié)。 第六章研究了(n，K,d)-偶圖。論文給出了求解使得給定圖為(n，K0，0

5、)-偶圖的最大正整數(shù)K0的算法。算法的時間復(fù)雜度為O(|V||E|)。此問題在設(shè)計任務(wù)管道和處理機之間的線路有應(yīng)用：刻劃了某些任務(wù)要指定處理機，但同時有些處理機不可用的情形。論文給出了有關(guān)(n，K,0)-圖連通度的結(jié)論。此外，論文還給出了判定(0，1，d)-圖的算法，其時間復(fù)雜度為O(IV||E|)。 第七章解決如何加最少的邊把給定偶圖擴展為1-可擴偶圖的問題。鑒于Gabow和Jordan給出了如何加最少的邊把有向偶圖擴展為強連