陳光亭，辛 雙，崔素輝

（杭州電子科技大學理學院運籌與控制研究所，浙江杭州310018）

0 引 言

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

1 概念和符號

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

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

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

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

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

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

（1）存在頂點 u，使得 M?G（u），且 u∈M；

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

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

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

2 3-cactus上連通p-median問題的算法

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

算法1

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

輸出樹T每個頂點的DT（u）。

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

第二步對T（r）的每個頂點u∈V（T（r）），計算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é)點｝，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

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

輸出 該圖的連通p-median。

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

第二步 得到相應的距離塊圖H（r）和對應于H（r）的廣探樹T（r）。

第三步對每一個頂點u∈G（r），在相應的廣探樹T（r）上計算R1（u）和R2（u）。

第四步對廣探樹T（r）中的每一個頂點u，應用算法1計算DT（u）。

第五步對H（r）中的每一個頂點u，計算DH（u）=DT（u）-R2（u）。

第六步對H（r）的每一條橋邊e=uv，計算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）。

第八步對G（r）的每一個頂點v，計算RG（k-1，v，v），k≥1；對應于H（r）的每一條橋邊e，計算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））中找出最小的頂點 u 或邊 uv，則 Q（u）或 Q（u，v）就是圖 G 的連通 p-median；

給出計算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）的葉子，且所對應的邊是H（r）的橋邊，則RG（k-1，（u，v），（u，v）=0，k≥2；

若uv是對應于H（r）的橋邊，且u，v中至少有一個不是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é)點，判斷 vi，vj是否為兄弟，若是，則

對vi，vj∈so（nv），且vi，vj是兄弟，用v*表示合并vi，vj后的記號，仍表示v的子節(jié)點，記（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é)點中是兄弟的所有子節(jié)點后的子節(jié)點集合，將原來G（r）中由vvi，vvj，vivj構(gòu)成的圈，用vv*邊來代替，這時G（r）也就轉(zhuǎn)換成了一棵樹。那么對于G（r）的每一個頂點，可以用下面的遞歸算法來計算所有的R（Gk-1，v，v），k≥1。

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

3 若干結(jié)論

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

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

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

4 算法復雜性分析

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