（n，n）圖的k-終端割與（n，n+1）圖的3-終端割問題研究.pdf

1、在一個邊權(quán)無向圖中，取定結(jié)點集的一個子集，子集中的元素稱為終端。k-終端割問題(k-terminalcutproblem)指的是尋找一個邊子集，使得圖中去掉該邊子集后，各終端互不連通，且該邊子集權(quán)和最小。近年來，k-終端割問題在理論界引起了極大的關(guān)注，并被廣泛地應(yīng)用于許多實際領(lǐng)域中，諸如并行與分布計算、VLSI電路設(shè)計以及網(wǎng)絡(luò)連接等。本文主要研究無向簡單連通(n，n)圖的k-終端問題和(n，n+1)圖的3-終端割問題，并限定圖中邊權(quán)為正

2、且兩兩不同。 在充分考慮(n，n)圖結(jié)構(gòu)特點的基礎(chǔ)上，本文給出了它的一個重要性質(zhì)，即：當(dāng)最小k-終端割中包含有Pc((n，n)圖中唯一的基本回路)上邊時，一定包含Pc上的最小加權(quán)邊。利用這個性質(zhì)，文中巧妙地將(n，n)圖與樹聯(lián)系起來，并結(jié)合樹的最小k-終端割算法給出了Pc上終端數(shù)不小于2的情況下，(n，n)圖上時間復(fù)雜度為O(kn)的k-終端割問題確定算法。進而，為了解決(n，n)圖中Pc上終端數(shù)小于2時的k-終端割問題，在沒有

3、增加算法的時間復(fù)雜度的情況下，本文對該算法作了適當(dāng)修改，并指出修改后的算法實際上可以作為求解(n，n)圖中k-終端割問題的通用算法，從而在一定意義上較好地解決了(n，n)圖中的k-終端割問題，與已有算法相比較，其運算效率也有了明顯提高(已知最好算法在解決(n，n)圖中k-終端割問題時的時間復(fù)雜度為O(nk3+(nlogn)k2))。 為了尋求(n，n+1)圖中3-終端割問題的有效解決方案，本文充分分析了(n，n+1)圖的結(jié)構(gòu)特點