張曉芹, 康麗英
(上海大學(xué)理學(xué)院,上海200444)
選址問題是運(yùn)籌學(xué)中的一個(gè)基本研究課題,在物流設(shè)施規(guī)劃、通訊系統(tǒng)設(shè)計(jì)等諸多領(lǐng)域具有十分廣闊的應(yīng)用背景.p-中心問題屬于設(shè)施選址問題,指在網(wǎng)絡(luò)圖中放置p個(gè)設(shè)施,使得每個(gè)客戶到達(dá)最近設(shè)施的最大權(quán)距離最小.對(duì)任意網(wǎng)絡(luò)圖,V和E分別表示網(wǎng)絡(luò)圖N的頂點(diǎn)集和邊集,n=|V|和m=|E|分別表示N的頂點(diǎn)數(shù)和邊數(shù).為敘述方便,引入符號(hào)Γ/Δ/p,其中Γ表示設(shè)施集合,Δ表示客戶集合,p表示需要放置的設(shè)施個(gè)數(shù).一般地,?!蕒V,E},Δ∈{V,E}.這表明設(shè)施和客戶的位置可能是圖N的頂點(diǎn),也可能是邊上任意一點(diǎn).若所有客戶的權(quán)值均為1,則稱該問題為無權(quán)中心問題.
1979年,Karive等[1]證明了一般圖的p-中心問題是NP-難的.他們還進(jìn)一步研究了一般圖的加權(quán)E/V/1問題和V/V/1問題,并相應(yīng)地給出了復(fù)雜性為O(mnlog n)和O(mn+n2log n)的算法.后來,Karive和Hakimi又為一般圖的加權(quán)E/V/p問題設(shè)計(jì)了一個(gè)O(mpn2p-1log n/(p-1)!)算法.Tamir于1991年在文獻(xiàn)[2]中將上述算法的復(fù)雜性改善為O(mpnplog nα(n)),其中α(n)表示Ackermann函數(shù)的逆.此外,還有許多學(xué)者致力于特殊圖的研究.到目前為止,關(guān)于樹中無權(quán)V/V/p,E/V/p和V/E/p問題的最有效算法的復(fù)雜性均為O(n)[3].而對(duì)于樹中加權(quán)的p-中心問題,Megiddo等[4]證明了V/V/ p問題可以在O(nlog2n)時(shí)間內(nèi)解決.而Jeger[5]則為V/V/p和E/V/p問題設(shè)計(jì)了一個(gè) O(pnlog n)算法.仙人掌圖中p-中心問題的研究可參閱文獻(xiàn)[6].本工作主要研究塊圖中無權(quán)E/V/1中心問題,并給出一個(gè)線性時(shí)間算法.
本工作所研究的圖均為有限無向簡(jiǎn)單圖,文中凡未加定義的術(shù)語和符號(hào)可參閱文獻(xiàn)[7].對(duì)任意圖N=(VN,EN),VN和EN分別表示N的頂點(diǎn)集和邊集.在N中,一個(gè)點(diǎn)x可能是N的頂點(diǎn),也可能是N的邊上的任意一點(diǎn).對(duì)N中任意2個(gè)點(diǎn)x和 y,PN(x,y)表示連接x和y的最短路,dN(x,y)表示x和y 2點(diǎn)間的距離,即PN(x,y)的長(zhǎng)度.若x和y之間沒有路相連,則dN(x,y)=∞.對(duì)于子集U?VN,N[U]表示由U導(dǎo)出的子圖.
若圖N中任意2個(gè)頂點(diǎn)之間都存在路,則稱N是連通的.頂點(diǎn)v稱為N的割點(diǎn),如果刪除v以及與v相關(guān)聯(lián)的邊會(huì)增加連通分支的個(gè)數(shù).圖N的塊是指不含割點(diǎn)的極大連通子圖.文獻(xiàn)[7]指出每個(gè)圖都是它的所有塊的并.若圖N的每個(gè)塊都是完全子圖,則稱N為塊圖[8-9].圖1(a)給出一個(gè)塊圖N,其包含的4個(gè)塊分別為B1=N[{v1,v2,v3,v4}],B2= N[{v4,v5,v6}],B3=N[{v3,v7}]和 B4=N[{v3,v8}].本工作總是研究連通塊圖N,且圖N中每條邊uv—的長(zhǎng)度均為1(若無特別說明,以下討論均含此假定).
圖1 塊圖N及其輪廓S的示意圖Fig.1 Illustration of block graph N and its skeleton S
塊圖N中無權(quán)的E/V/1中心問題可描述如下:找到一個(gè)點(diǎn)x*∈EN,使得目標(biāo)函數(shù)
最小.
為了解決上述問題,本工作采用文獻(xiàn)[10]中提出的塊圖N的輪廓S=(VS,ES).如圖1(b)所示,S的每個(gè)頂點(diǎn)代表N的一個(gè)頂點(diǎn)或者一個(gè)塊.對(duì)于N的每個(gè)頂點(diǎn)v和塊B,如果v∈B,則S中有一條長(zhǎng)度為1的邊連接頂點(diǎn)v和B.由此可知,連通塊圖的輪廓是一棵樹.若|VN|>1,則S的所有葉子點(diǎn)都代表N的頂點(diǎn).Aho等在文獻(xiàn)[11]中證明了一個(gè)塊圖的輪廓可通過深度優(yōu)先搜索方法在線性時(shí)間內(nèi)構(gòu)造出來.
由輪廓S的構(gòu)造易得,其頂點(diǎn)集VS被分成2個(gè)互不相交的子集VN和β,其中β表示塊圖N中所有塊的集合.本工—作定義S中的最長(zhǎng)路為S的直徑.當(dāng)從S中刪除邊xy 時(shí),用S(x,y)和S(y,x)分別表示包含頂點(diǎn)x和y的2棵子樹.
本節(jié)將通過研究塊圖的結(jié)構(gòu)性質(zhì),證明塊圖中無權(quán)的E/V/1中心問題可以在線性時(shí)間內(nèi)解決.基于輪廓S的特殊構(gòu)造以及文獻(xiàn)[12]中關(guān)于樹的中心與直徑的結(jié)論,現(xiàn)歸納S的一些基本性質(zhì).
性質(zhì)1 設(shè)x和y為輪廓S的2個(gè)頂點(diǎn),若x,y∈VN,則dS(x,y)=2dN(x,y).
性質(zhì)2 若PS(x,y)為輪廓S的一條直徑,則x,y∈VN,且dS(x,y)為偶數(shù).
性質(zhì)3 若PS(x,y)為輪廓S的一條直徑,c為S的1-中心,則c為PS(x,y)的一個(gè)頂點(diǎn),且滿足dS(c,x)=dS(x,y)/2.
以下簡(jiǎn)稱1-中心為圖的中心.設(shè)c為輪廓S的中心,根據(jù)性質(zhì)3可得,c是S直徑上的一個(gè)頂點(diǎn),因此,c∈VN,或者c∈β.
首先,考慮c∈VN的情況.
定理1 設(shè)c為輪廓S的中心,若c∈VN,則c為塊圖N的中心.
證明 因?yàn)閏∈VN,根據(jù)性質(zhì)1和4,可得
又由c為輪廓S的中心,可得
證明 在輪廓S中,令ui是子樹S(vi,c)的一個(gè)頂點(diǎn),且滿足dS(vi,ui)=φ(vi),i=1,…,dS(c),如圖2(a)所示.在塊圖N中,令Ni是N的一個(gè)子圖,使得Ni的每個(gè)頂點(diǎn)和塊都被S(vi,c)的一個(gè)頂點(diǎn)所表示,反之亦然,如圖2(b)所示.由φ(vi)的定義可知,ui為Ni中距離vi最遠(yuǎn)的一個(gè)頂點(diǎn).
圖2 定理2證明的示意圖Fig.2 Illustration of proof of Theorem 2
基于以上討論,下面給出塊圖中無權(quán)E/V/1中心問題的求解算法UCBG.
輸入:一個(gè)邊長(zhǎng)為1的連通塊圖N;
輸出:塊圖N的中心c*.
(1)構(gòu)造N的輪廓S;
(2)找出S的中心c;
(3)若c∈VN,則c*=c;
(4)若c∈B,則從S中刪除頂點(diǎn)c以及與c相關(guān)聯(lián)的邊,得到子樹S(v1,c),…,S(vdS(c),c);
(6)找出序列φ(vi)i中最大的3個(gè)數(shù),從大到小排列,依次記為φ(vj),φ(vk)和φ(vl);
(8)若φ(vj)=φ(vk)=φ(vl),則c*為N中塊c的任意一個(gè)頂點(diǎn);
(9)結(jié)束.
定理3 邊長(zhǎng)為1的塊圖中無權(quán)E/V/1中心問題可以在線性時(shí)間內(nèi)解決.
證明 該定理的證明歸結(jié)為算法UCBG的正確性與復(fù)雜性分析.定理1和2可直接說明算法UCBG的正確性.下面逐行分析算法的運(yùn)行時(shí)間.
第1行可利用深度優(yōu)先搜索方法進(jìn)行構(gòu)造,需要O(|VN|+|EN|)時(shí)間.第2行可利用Handler算法[13]求解,需要O(|VS|)時(shí)間.第4行,所有子樹S(vi,c)可在O(|VS|)時(shí)間內(nèi)得到.對(duì)任意整數(shù)1≤i≤dS(c),φ(vi)可在O(|VS(vi,c)|)時(shí)間內(nèi)計(jì)算出來.因此,第5行總共需要O(|VS|)時(shí)間,第6行只需經(jīng)過3次求最大值運(yùn)算,即可獲得φ(vj),φ(vk)和φ(vl),所需時(shí)間為O(dS(v)),而第3,4,7和8行只需常數(shù)時(shí)間.又因O(|VS|)=O(|VN|+|B|)= O(|VN|),所以,算法UCBG的復(fù)雜性為O(|VN+ EN|).
最后,通過求解圖1(a)中塊圖N的1-中心對(duì)上述算法進(jìn)行說明.塊圖N的輪廓S如圖1(b)所示.根據(jù)Handler算法,最長(zhǎng)路P(v5,v7)的中點(diǎn)B1是S的中心.因?yàn)锽1∈B,依照算法的第4行,從S中刪除頂點(diǎn) B1以及與其相關(guān)聯(lián)的邊,得到子樹S(v4,B1),S(v1,B1),S(v2,B1)和 S(v3,B1).由φ(vi)的定義得φ(v4)=2,φ(v1)=0,φ(v2)=0,φ(v3)=2,從而 φ(v4)=φ(v3)>max{φ(v1), φ(v2)}.根據(jù)算法的第7行,圖1(a)中邊的中點(diǎn)是塊圖的中心.
通過分析塊圖中心與輪廓中心的關(guān)系,本工作解決了塊圖中無權(quán)的E/V/1中心問題,并為其設(shè)計(jì)了線性時(shí)間算法.對(duì)任意p≥2,塊圖中無權(quán)的E/V/p問題能否類似地解決是一個(gè)比較有趣的問題,有待于進(jìn)一步研究.此外,塊圖中加權(quán)的p-中心問題也是一個(gè)值得探討的問題.
[1] KARIVO,HAKIMIS L.An algorithmic approach to network location problems—(I) the p-centers[J].SIAM J Appl Math,1979,37:539-560.
[2] TAMIR A.Improved complexityboundsforcenter location problems on networks by using dynamic data structures[J].SIAM J Discrete Math,1991(4):34-38.
[3] FREDERICKSONG N.Parametric search and locating supply centers in trees[C]∥ Proceedings of the 2nd Workshop on Algorithms and Data Structures.Berlin:Springer,1991:299-319.
[4] MEGIDDON,TAMIRA,ZEMELE,etal.An O(nlog2n)algorithm for the kth longest path in a tree with applications to location problems[J].SIAM J Comput,1981,10(2):328-337.
[5] JEGERM,KARIVO.Algorithms for finding p-centers on a weighted tree(for relatively small p)[J].Networks,1985,15(3):381-389.
[6] BEN-MOSHEB,BHATTACHARYAB,SHIQ S,et al.Efficient algorithms for center problems in cactus graphs[J].Theoretical Computer Science,2007,378(3):237-252.
[7] BONDYJ A,MURTYU S R.Graph theory with applications[M].London:MacMillan,1976.
[8] HUNGR W.Optimal vertex ranking of block graphs[J].Information and Computation,2008,206:1288-1302.
[9] WONGP K.Optimal path cover problem on block graphs[J].Theoret Comput Sci,1999,225:163-169.
[10] KANGL Y,CHENGY K.The p-maxian problem on block graphs[J].J Comb Optim,20:131-141.
[11] AHOA V,HOPCROPTJ E,ULLMANJ D.The design and analysis of computer algorithms[M].Reading:Addison-Wesley Publishing Company,1976:84-86.
[12] WUB Y,CHAOK M.Spanning trees and optimization problems[M].Florida:CRC Press,2004:1-23.
[13] HANDLERG Y.Minimax location of a facility in an undirected tree graph[J].Trans Sci,1973,7(3):287-293.