[發(fā)明專利]基于MLkP/CR算法的無向圖分割方法

有效

• 申請(qǐng)?zhí)枺?/td>: 200910073338.9
• 申請(qǐng)日: 2009-12-03
• 公開（公告）號(hào): CN101741611A
• 公開（公告）日: 2010-06-16
• 發(fā)明（設(shè)計(jì)）人: 何慧;張偉哲;張宏莉;楊志;王星;楊賢青
• 申請(qǐng)（專利權(quán)）人: 哈爾濱工業(yè)大學(xué)
• 主分類號(hào): H04L12/24
• 分類號(hào): H04L12/24
• 代理公司: 哈爾濱市松花江專利商標(biāo)事務(wù)所 23109
• 代理人: 張宏威

1.基于MLkP/CR算法的無向圖分割方法，其特征在于所述方法分為下述三個(gè)階段：

規(guī)約階段：對(duì)待分割的無向圖G₀(V₀，E₀)進(jìn)行規(guī)約，將無向圖G₀(V₀，E₀)中的若干點(diǎn)合成一個(gè)點(diǎn)，規(guī)約成無向圖G_n(V_n，E_n)，降低拓?fù)鋱D的規(guī)模，其中V₀是無向圖G₀中的頂點(diǎn)的集合，E₀是無向圖G₀中邊的集合，V_n是無向圖G_n中的頂點(diǎn)的集合，E_n是無向圖G_n中邊的集合；

初始劃分階段：對(duì)規(guī)約階段獲得的無向圖G_n(V_n，E_n)進(jìn)行k劃分獲得k個(gè)子圖G_i(V_i，E_i)，劃分獲得的每個(gè)子圖G_i(V_i，E_i)都是自連通的，每個(gè)子圖G_i(V_i，E_i)中的點(diǎn)的數(shù)目基本相等，并且被切邊數(shù)edge-cut最小；

優(yōu)化求精階段：對(duì)初始劃分階段獲得的劃分后的各個(gè)子圖進(jìn)行優(yōu)化求精，并還原成原始無向圖G₀(V₀，E₀)，獲得劃分后的無向圖G₀＝(V₀，E₀)，所述劃分后的無向圖G₀＝(V₀，E₀)中，|V₀|＝n，V₀的k個(gè)子集為V₁，V₂，…，V_k，其中?i≠j，并且∪V_i＝V₀，|V_i|＝|V₀|/k；兩個(gè)端點(diǎn)不在同一子集的邊的總數(shù)最小，其中∪V_i＝V₀表示所有的V_i的并集為V₀；k個(gè)子集為V₁，V₂，…，V_k之間的分割線的數(shù)量edge_cut＝∑e(u，v)，u∈G_i∧v∈G_j∧i≠j，所述點(diǎn)u和點(diǎn)v是分別屬于兩個(gè)子圖中的點(diǎn)，所述e(u，v)表示分割邊，是指點(diǎn)u和點(diǎn)v之間的連接邊。

2.根據(jù)權(quán)利要求1所述的基于MLkP/CR算法的無向圖分割方法，其特征在于，在規(guī)約階段，原始無向圖G₀的經(jīng)過第i次規(guī)約后獲得的子圖G_i(V_i，E_i)中，V_i中的任一點(diǎn)v的分割向量為P[v]＝i，如果邊e(u，v)∈E_i，則有P[u]＝P[v]＝i。