輕點匹配K劃分拓撲圖的研究.pdf

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

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

3、劃分算法(GGGP)，然后對非規(guī)則圖的多層k路劃分模式中的壓縮過程采用的匹配算法加以改進。針對網(wǎng)絡拓撲圖中樹狀結構較多、頂點權重與邊權重存在正比聯(lián)系的特點，提出采用輕點匹配的多層k路劃分算法。它對于現(xiàn)實Internet網(wǎng)絡的拓撲結構有很好的適應性，可以很好地改進重邊匹配帶來的節(jié)點權重過大帶來的弊端。在研究隨機匹配，重邊匹配，改進的重邊匹配和輕邊匹配的基礎上，首次提出輕點匹配的概念，通過劃分實驗，將輕點匹配與其它匹配的分割效果進行對比，證