網(wǎng)絡(luò)拓?fù)鋱D多層K劃分模式輕點匹配研究.pdf

1、圖劃分是一個重要的研究問題，在廣范的應(yīng)用領(lǐng)域中起作用。包括科學(xué)計算、超大規(guī)模集成電路設(shè)計，任務(wù)安排，現(xiàn)代戰(zhàn)爭模擬等。
　　圖劃分問題是將一個由頂點和邊組成的圖，劃分為k個部分，同時使每個部分盡量相等，不同部分之間的關(guān)聯(lián)盡可能少。這樣群集計算機的每個節(jié)點負(fù)責(zé)相應(yīng)部分的工作，所有節(jié)點同時工作，達(dá)到并行高速處理的目的。
　　當(dāng)圖的頂點和邊較多時，直接進(jìn)行k路劃分難度較大。為此，可將圖壓縮為粗圖后再進(jìn)行k路劃分，這樣比較容易。然后再

2、把這個k劃分后的粗圖還原到原始圖，這就是多層k劃分的核心思想。多層k劃分共有三個階段：粗化階段，初始劃分階段和細(xì)化求精階段。壓縮頂點和邊的過程是粗化過程，多層k劃分的粗化階段的壓縮過程主要采取匹配算法。匹配算法主要有隨機匹配、重邊匹配、改進(jìn)的重邊匹配、輕邊匹配等，它們在非規(guī)則圖的劃分過程中可以起到很好的作用。
　　本文討論圖劃分方法，首先介紹得到廣泛研究的多種二分法，包括譜二分法、Kernighan-Lin及其改進(jìn)算法、圖增長劃分

3、算法（GGP）、貪心圖增長劃分算法（GGGP），然后對非規(guī)則圖的多層k路劃分模式中的壓縮過程采用的匹配算法加以改進(jìn)。針對網(wǎng)絡(luò)拓?fù)鋱D中樹狀結(jié)構(gòu)較多、頂點權(quán)重與邊權(quán)重存在正比聯(lián)系的特點，提出采用輕點匹配的多層k路劃分算法。它對于現(xiàn)實Internet網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)有很好的適應(yīng)性，可以很好地改進(jìn)重邊匹配帶來的節(jié)點權(quán)重過大帶來的弊端。在研究隨機匹配，重邊匹配，改進(jìn)的重邊匹配和輕邊匹配的基礎(chǔ)上，首次提出輕點匹配的概念，
　　通過劃分實驗，將輕