3-cactus上的連通p-median問(wèn)題

陳光亭，辛 雙，崔素輝

（杭州電子科技大學(xué)理學(xué)院運(yùn)籌與控制研究所，浙江杭州310018）

0 引 言

p-median問(wèn)題是選址理論中的經(jīng)典問(wèn)題，它是如下定義的：給定一個(gè)連通的無(wú)向圖G=（V，E），V是頂點(diǎn)集合，E是邊集合［1］。每一條邊e∈E賦予一個(gè)非負(fù)的權(quán)重（長(zhǎng)度）l（e），每一個(gè)頂點(diǎn)v∈V也有一個(gè)非負(fù)的權(quán)重 w（v）；d（vi，vj）表示vi和vj之間的距離，即連接vi、vj的最短路的長(zhǎng)度。問(wèn)題是找出一個(gè)含有p個(gè)頂點(diǎn)的子集H，使得v）d（v，H）最小。文獻(xiàn) 1 證明了該問(wèn)題是 NP-hard，文獻(xiàn) 2 給出了一些近似方案。在樹(shù)圖上，文獻(xiàn)1給出了一個(gè)O（p2n2）的算法，文獻(xiàn)3給出了一個(gè)O（pn2）的算法 。在路圖中，文獻(xiàn)4給出了一個(gè)O（pn）的算法。在本文中研究這樣的問(wèn)題：選出的p個(gè)設(shè)施點(diǎn)是連通的，即由這p個(gè)頂點(diǎn)導(dǎo)出的子圖是連通的，稱為連通p-median問(wèn)題?？梢远x為：給定一個(gè)連通的賦權(quán)圖G=（V，E），找出一個(gè)含有p個(gè)頂點(diǎn)的子集H，滿足 G（H）連通，且v）d（v，H）最?。?］。由于樹(shù)模型不能很好的表示現(xiàn)實(shí)的網(wǎng)絡(luò)，而下面定義的cactus則能更好的反映現(xiàn)實(shí)的模型，因此本文研究cactus上連通p-median問(wèn)題。

1 概念和符號(hào)

在一個(gè)圖中，如果移去某個(gè)頂點(diǎn)及其關(guān)聯(lián)的邊，圖的連通分支增加，那么該頂點(diǎn)叫做割點(diǎn)。一個(gè)沒(méi)有割點(diǎn)的連通圖稱為不可分圖；一個(gè)圖中的極大的不可分子圖稱為塊；圈是一個(gè)連通圖，且每個(gè)頂點(diǎn)的度都是2。如果圖中的塊是個(gè)圈，那么稱這個(gè)塊為圈塊。一個(gè)cactus是一個(gè)連通圖，它的每一個(gè)塊是三個(gè)或更多頂點(diǎn)的圈塊。一個(gè)賦權(quán)的k-cactus（簡(jiǎn)記為WkC），它的每一個(gè)塊至多包含k條邊，每一條邊和每個(gè)頂點(diǎn)都有一個(gè)非負(fù)的權(quán)重。如果k=3，則稱為3-cactus。

應(yīng)用廣探法遍歷一個(gè)圖的頂點(diǎn)時(shí)，由于圖頂點(diǎn)的有限性，廣探法最終會(huì)停止；且圖的每一個(gè)頂點(diǎn)恰被訪問(wèn)一次，因此遍歷路徑不會(huì)有圈形成。最終圖的邊可以分為兩類：樹(shù)邊即廣探法經(jīng)過(guò)的邊，和非樹(shù)邊即廣探法未經(jīng)過(guò)的邊，非樹(shù)邊也稱為橋邊。

設(shè)G=（V，E，L，W）是一個(gè)賦權(quán)3-cactus圖（簡(jiǎn)記為W3C），任選一個(gè)頂點(diǎn)r∈V作為圖G的根，那么這個(gè)圖就可以記為 G（r）。G（r）的距離塊圖 H（r）（簡(jiǎn)記為 W3B（r））是一個(gè)賦權(quán)圖，是指將 G（r）中的每一個(gè)圈塊轉(zhuǎn)換成一個(gè)完全圖 ，其它的結(jié)構(gòu)保持不變 ；對(duì)H（r）中每一條邊e=（u，v）∈H（E），令 lH（e）=dG（u，v），其中dG（u，v）表示u，v在G（r）最短路的長(zhǎng)度。如果在賦權(quán)H（r）的底圖上應(yīng)用廣探法，則訪問(wèn)路徑可以得到一棵樹(shù)，稱為 H（r）的廣探樹(shù)，用 T（r）表示 H（r）的廣探樹(shù)。

對(duì)任一個(gè)賦權(quán) 3-cactus圖 G=（V，E，L，W），任選一個(gè)頂點(diǎn) r∈V作為根 ，記為 G（r），然后得到與G（r）相應(yīng)的 H（r），對(duì) H（r）應(yīng)用廣探法 ，得到相應(yīng)的廣探樹(shù) T（r）；在上述過(guò)程中 ，可以保持 G（r），H（r），T（r）中頂點(diǎn)的一致性，即在 T（r）中的頂點(diǎn) v 與 G（r），H（r）中的頂點(diǎn) v 代表同一個(gè)頂點(diǎn)。用 NT（u）表示H（r）中所有與u鄰接的非樹(shù)邊的集合。對(duì)任意的u∈V（T），wT（u）=wH（u），lT（eu）=lH（u，v）=dG（u，v），eu=（u，v），v是u的父節(jié)點(diǎn)。對(duì)H（r）中的每一條非樹(shù)邊e=（u，v），令α（e）=lT（eu）+lT（ev））；其中WT（r）（u）=ANC（u）表示在 T（r）中 u 的前輩。

對(duì) G（r）于中的頂點(diǎn) ，可以分層標(biāo)號(hào) 。令φ（r）=1，對(duì)任意的 v∈G（r），若（v，r）∈G（E），則φ（v）=φ（r）+1；對(duì)已標(biāo)號(hào)的頂點(diǎn) v，若（u，v）∈G（E），且 u 還沒(méi)有標(biāo)號(hào)，則φ（u）=φ（v）+1；對(duì)每一個(gè)頂點(diǎn) v，定義son（v）=｛u|φ（u）=φ（v）+1，（u，v）∈G（E）｝，也稱v是u的父節(jié)點(diǎn)，記為p（u）=v；若son（v）是空集，稱v是葉頂點(diǎn)，否則為非葉頂點(diǎn)。對(duì)son（v）中的任意兩個(gè)頂點(diǎn)u1，u2，若（u1，u2）∈G（E），則稱u1，u2是兄弟 ，記 u1=b（u2）和 u2=b（u1），顯然有φ（u1）= φ（u2）。對(duì)任意的頂點(diǎn) u，用 G（u）表示由頂點(diǎn)集｛v|φ（v）≥φ（u）｝及刪除邊｛（u，x）|x=p（u）或 x=b（u）｝后所得到的子圖。對(duì) G（r）中的任意一對(duì)兄弟u，v ，用 G（u，v）表示由邊（u，v）及 G（u）和 G（v）所組成的子圖。對(duì) G（r）的任一個(gè)連通 p-median M ，用δ（M）表示G（r）中所有頂點(diǎn)到M的賦權(quán)和。

引理1 設(shè) M是G（r）的任意一個(gè)連通p-median，則下面兩個(gè)結(jié)論中至少有一個(gè)成立：

（1）存在頂點(diǎn) u，使得 M?G（u），且 u∈M；

（2）存在一對(duì)兄弟 u 和 v，使得 M?G（u，v），且 u，v∈M。

對(duì)任意的 G（u），用 Q（u）表示 G（u）上的任意一個(gè)最優(yōu)連通 p-median（u∈Q）；對(duì)任意的 G（u，v），用Q（u，v）表示G（u，v）上的任意一個(gè)最優(yōu)連通p-median（（u，v）∈Q）。顯然有下面的引理成立：

引理 2 設(shè)Ω=｛Qu|u∈G（V）｝，Ψ=｛Q（u，v）|u，v是 G（r）中的兄弟｝。如果 Q∈Ω∪Ψ，且對(duì)任意的M∈Ω∪Ψ，都有δ（Q）≤δ（M），那么 Q是 G（r）的一個(gè)最優(yōu)連通 p-median。

2 3-cactus上連通p-median問(wèn)題的算法

用DT（u）表示T（r）中所有頂點(diǎn)到u的賦權(quán)距離和；B（u）表示T（r）的子樹(shù)Tr（u）中的所有頂點(diǎn)到u的賦權(quán)距離和；B+（u）表示T（r）的子樹(shù)Tr（u）中所有頂點(diǎn)到u的父節(jié)點(diǎn)P（u）的賦權(quán)距離和；Wr（u）表示T（r）的子樹(shù)Tr（u）中所有頂點(diǎn)的權(quán)重和。

算法1

輸入 一棵賦權(quán)樹(shù)T（V，E）；

輸出樹(shù)T每個(gè)頂點(diǎn)的DT（u）。

第一步 任選一個(gè)頂點(diǎn)r∈V作為根，把輸入的樹(shù)T轉(zhuǎn)化成一棵有根樹(shù)，記這棵有根樹(shù)為T（r）。

第二步對(duì)T（r）的每個(gè)頂點(diǎn)u∈V（T（r）），計(jì)算B（u），B+（u），Wr（u）；若v是T（r）的葉子，Wr（v）=w（v），B（v）=0，B+（v）=w（v）l（v，p（v））；若v不是T（r）的葉子，記son（v）=｛u|u∈V（T（r）），v是u的父節(jié)點(diǎn)｝，B（v）=u），B+（v）=B（v）+Wr（v）l（v，p（v））；B+（ r）=B（ r）。

第三步D（r）=B（r）；u∈V｛r｝，D（u）=D（p（u））-B+（u）+B（u）+（Wr（r）-Wr（u））l（（u，p（u）））。

算法2

輸入 一個(gè)連通的賦權(quán)3-cactus。

輸出 該圖的連通p-median。

第一步 應(yīng)用 Tarjan’s算法［6］，確定圖 G（r）中的塊。

第二步 得到相應(yīng)的距離塊圖H（r）和對(duì)應(yīng)于H（r）的廣探樹(shù)T（r）。

第三步對(duì)每一個(gè)頂點(diǎn)u∈G（r），在相應(yīng)的廣探樹(shù)T（r）上計(jì)算R1（u）和R2（u）。

第四步對(duì)廣探樹(shù)T（r）中的每一個(gè)頂點(diǎn)u，應(yīng)用算法1計(jì)算DT（u）。

第五步對(duì)H（r）中的每一個(gè)頂點(diǎn)u，計(jì)算DH（u）=DT（u）-R2（u）。

第六步對(duì)H（r）的每一條橋邊e=uv，計(jì)算DT（e）；記它們的父親為p（u）=p（v）=p（e）；DT（e）=DT（p（e））-（B（u）+B（v））+（BT（u）+BT（v））+（WT（r）-WT（u）-WT（v））min｛lT（u，p（e），lT（v，p（e））｝。

第七步DH（e）=DT（e），e是H（r）的橋邊；Bh（u）=BT（u），u∈V（H）。

第八步對(duì)G（r）的每一個(gè)頂點(diǎn)v，計(jì)算RG（k-1，v，v），k≥1；對(duì)應(yīng)于H（r）的每一條橋邊e，計(jì)算RG（k-2，e，e），k≥2。

第九步從DH（v）-BH（v）+RG（p-1，v，v）和DH（e）-BH（e）+RG（p-1，e，e）（e=uv，BH（e）=BH（u）+BH（v））中找出最小的頂點(diǎn) u 或邊 uv，則 Q（u）或 Q（u，v）就是圖 G 的連通 p-median；

給出計(jì)算RG（k-1，v，v）和RG（k-2，e，e）的遞歸算法：

若v是T（r）的葉子，則RG（k-1，v，v）=0，k≥1；

若u，v都是T（r）的葉子，且所對(duì)應(yīng)的邊是H（r）的橋邊，則RG（k-1，（u，v），（u，v）=0，k≥2；

若uv是對(duì)應(yīng)于H（r）的橋邊，且u，v中至少有一個(gè)不是T（r）的葉子，則RG（k-2，uv，uv）=｛RG（i-1，u，u）+RG（k-i，v，v）｝，k≥2；若v不是T（r）的葉子，記son（v）=｛v1，v2，…，vs｝為v在T（r）中的子節(jié)點(diǎn)，判斷 vi，vj是否為兄弟，若是，則

對(duì)vi，vj∈so（nv），且vi，vj是兄弟，用v*表示合并vi，vj后的記號(hào)，仍表示v的子節(jié)點(diǎn)，記（v*）=R（Gk-1，v，（vi，vj）），k=1；R（G（k-1）-1，v*，v*）=R（Gk-1，v，（vi，vj）），k=2；

R（G（k-1）-1，v*，v*）=R（Gk-1，v，（vi，vj）），k≥3；用so（nv）=｛v1，v2，…，vt｝（t≤s）表示合并v的子節(jié)點(diǎn)中是兄弟的所有子節(jié)點(diǎn)后的子節(jié)點(diǎn)集合，將原來(lái)G（r）中由vvi，vvj，vivj構(gòu)成的圈，用vv*邊來(lái)代替，這時(shí)G（r）也就轉(zhuǎn)換成了一棵樹(shù)。那么對(duì)于G（r）的每一個(gè)頂點(diǎn)，可以用下面的遞歸算法來(lái)計(jì)算所有的R（Gk-1，v，v），k≥1。

若 v 是 G（r）葉子，則 R（k-1，v，v）=0，k=1，2，…，p；否則，設(shè) son（v）=｛v1，v2，…，vt｝，

3 若干結(jié)論

結(jié)論1對(duì)任意的頂點(diǎn)v∈Gr（V），有DG（v）=DH（v）［7］。

結(jié)論2對(duì)任意的頂點(diǎn)v∈Gr（V），有BG（v）=BH（v）=BT（v），B+H（v）=（v）。

結(jié)論3若e=（u，v）∈Gr（E）是對(duì)應(yīng)于H（r）的橋邊，則有DG（u，v）=DH（u，v）=DT（u，v）。

4 算法復(fù)雜性分析

首先，在中T（r）計(jì)算DT（v），DT（e）（e是對(duì)應(yīng)于H（r）的橋邊）的復(fù)雜度為O（n）；其次計(jì)算G中每個(gè)頂點(diǎn)v的RG（p-1，v，v）的復(fù)雜度為O（d（v）p），其中d（v）表示v在G中的度；最后計(jì)算對(duì)應(yīng)于H（r）的每個(gè)橋邊e的RG（p-1，e，e）復(fù)雜度為O（p）。因此得到所有的RG（p-1，v，v）和RG（p-1，e，e）的復(fù)雜度為 O（pn）。應(yīng)用 Tarjan’s［6］的算法，算法 2的第一步可以在 O（m+n）內(nèi)完成；由圖 W3C構(gòu)造 W3B也是 O（m+n），其中m是圖G中的邊數(shù)，也是O（n）。因此整個(gè)算法的復(fù)雜度為O（pn）。

［1］ Kariv O，Hakimi SL.An algorithmic approach to network location problems.II：the p-medians［J］.JAppl Math，1979，37（3）：539-560.

［2］ Lin A JH，Vitter JS.Approximations with minimum packing constraint violation［M］.Brown University：Department of Computer Science，1992：29-92.

［3］ Tamir A.An O（pn2）algorithm for the p-median and related problems on tree graphs［J］.Operations Researc letters，1996，19（2）：59-64.

［4］ Hassin R，Tamir A.Improved complexity bounds for location problrms on the real line［J］.Oper Res Lett，1991，10（1）：395-402.

［5］ Chen Chien Tsai.The p-center problem with some practical constraints［J］.Department of Information Management，2006，52（1）：1-4.

［6］ Tarjan R E.Depth first search and linear graph algorithms［J］.SIAM journal on Computing，1972，2（1）：146-160.

［7］ Lan Y，Wang Y.An optimal algorithm for solving the 1-median problem on weighted 4-cactus graphs［J］.European joural of operational research，2000，22（1）：602-610.