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

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

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

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