頂點賦權(quán)圖中的連通子圖劃分問題

李 彤，陳 永，張 安，陳光亭

(1.杭州電子科技大學理學院，浙江 杭州 310018；2.臺州學院電子與信息工程學院，浙江 臺州 318000)

0 引 言

1 預備知識

給定一個簡單頂點賦權(quán)連通圖G=(V,E)，設(shè)所有頂點的權(quán)重之和為W。對于V的任意2個頂點不相交的子集導出的子圖G(V1)和G(V2)，如果存在一條邊(u,v)∈E，使得u∈V2且v∈V1，則說明V1和V2是相鄰的。對于k-GP問題的頂點集V的任意一個可行劃分，由于G是連通的，任何部分都至少與劃分中的一個部分相鄰。

2 近似算法與算法分析

定義2如果V2滿足：(1)V2中存在點u，u與V1之間有邊相連；(2)在V2中，u同時連接若干個連通分支C21,C22,…,C2s，且w(C21)≥w(C22)≥…≥w(C2s)；(3)w(V1)

本文提出的近似算法(簡稱：2-GP算法)思想如下：首先找到圖G的一棵生成樹T，再從T中任意刪除k-1條邊，產(chǎn)生k個連通分支V1,V2,…,Vk，w(Vi)表示第i個連通分支的權(quán)重，循環(huán)運用定義1至定義3的操作，逐步減小總權(quán)重最大子集的權(quán)重。算法的流程如圖1所示。

圖1 2-GP算法流程圖

2-GP算法主要步驟如下：

(2)在圖G中找一棵生成樹T。

(3)在T中去掉任意一條邊，得到2個連通分支V1,V2，設(shè)w(V1)≤w(V2)。

(5)輸出V1,V2。

引理2若定義1的操作不能進行，則在V2中u至少連接著2個連通分支。

引理3若定義2的操作不能進行，則w(V1)≥w(C21)。

證明因為圖G是連通的，所以定義2中條件(1)成立。又由引理2可知，定義2中條件(2)成立。因此，定義2不能進行的原因是因為定義2中條件(3)不成立，即w(V1)≥w(C21)。證畢。

引理4若定義3的操作不能進行，則V1與V2中的連通分支均不相連接。

圖2 最終圖的劃分結(jié)構(gòu)

圖3 算法緊例

3 結(jié)束語