有關(guān)小樹寬圖和對(duì)集可擴(kuò)圖算法的研究.pdf

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

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

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

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

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