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

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

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

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