（运筹学与控制论专业论文）城市警车选址问题.pdf

原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本人完 全意识到本声明的法律责任由本人承担。 论文作者签名：三陋 日期： 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：性导师签名： 山东大学硕士学位论文 城市警车选址问题 刘大诚 山东大学数学与系统科学学院济南2 5 0 1 0 0 中文摘要 本文主要是解决实际问题中提出的城市警车选址问题。我们把城市看成一个平面图 g ，假设图的顶点表示路口，图的边表示路，然后在此图上进行分析。我们根据控制集 理论提出图论上的一个新问题图的强距离控制集问题，为解决此问题，我们通过 定的方法，把图g 转化成另外的新的有向图g 1 或无向二分图g ，并证明了新的有向图g l 的有向控制集和无向二分图g 的s p _ 控制集都是原图g 的强距离控制集，并给出了相关 的定理，然后设计了相关算法，并分别举例进行分析比较。 本文主要思想是把在原图g 上求一个强距离控制集化为在转化后的新的有向图g 上求一个有向控制集或无向二分图g 上求一个s p 一控制集。 本文共分三章，在第一章第一节介绍了警车选址问题的提出背景，着重介绍了紧急 事件处理问题，进而介绍了前人所做的工作及本文要解决的主要任务：在第二节介绍了 警车选址问题的研究基础，包括将要用到的图论中的基本概念，如最短路及相关的有关 控制集的概念和定理等；在第三节建立了警车选址问题的图论模型。 定理1 2 1 ：对图g = ( v ，e ) ，有d o m ( g ) d o m k ( g ) 。 定理1 2 2 ：对边赋权图g = ( y ，e ) 及任意给定的常数r o ， s d d o m ( g ) d d o m 。( g ) 。 并且当每条边的权值都不大于时，有d o m ( g ) d d o m 。( g ) 。 第二章在第一节构造了一个新的有向图g l ，把在原图g 上求强距离控制集化为在转 化后的新的有向图g l 上求一个有向控制集，给出了相关定理和引理，其中r o 是预先给定 山东大学硕士学位论文 的常数。然后在第二节设计了一个求解有向控制集的算法，然后给出了一个算例。随后 我们把此有向图转化成一个无向二分图去分析。 定理2 1 1 ：给定一个新的有向图g 1 = ( 巧，巨) ，设s 是它的一个有向控制集，则对原 图g = ( 矿，e ) 的任意点x g ，有d ( s ，z ) ，即s 就是原图g = ( v ，e ) 的一个强距离，0 一 控制集。 定理2 2 1 ：我们通过上丽算法1 得到的集合s 是一个极小有向控制集。 在第三章我们首先在第一节构造了一个无向二分图g ，给 _ 了s p 一控制集的概念， 并证明j 新图g 的s p 一控制集是原图g 的一个强距离控制集，并给出了相关定理；在此 基础上在第二节我们设计了另外一个求解警车选址问题的近似算法，同时也给出了相关 的算例，并与上一节的算例作了分析比较；第三节是问题的延m 我们把问题转化成数 学走见划来分析，但没有给出算法。 定理3 1 1 ：设s 为如上构造的图g = ( v x ，e ) 的一个s p 一控制集，则对图g = ( v ，) 上的任意点y g ，有d ( s ，y ) r o ，即s 为图g = ( 矿，e ) 的一个强距离一控制集。 定理3 2 1 ：用上面的算法1 得到的集合d 是新图g = ( v ，x ，e ) 的一个极小s p 一控 制集，进而是原图g 的一个强距离一+ 控制集。 关键词：警车选址，强距离控制集，有向控制集，s p 一控制集 山东大学硕士学位论文 t h el o ca r r i o no fu r b a np o l i c ev a ns t a t i o n a b s t r a c t ： l i u d a e h e n g s c h o o lo fm a t h e m a t i c sa n d s y s t e ms c i e n c e s s h a n d o n gu n i v e r s i 吼j i n a n ，s h a n d o n g ，c h i n a ，2 5 0 1 0 0 i np r a c t i c e ，t h e r ee x i s t sap r o b l e mo ft h el o c a t i o no fu r b a n p o l i c ev a n w e s o l v et h i sp r o b l e m b y t h ef o l l o w i n gm o d e l ：a c i t yi sl o o k e du p o na sap l a n eg r a p h ： g ，i nw h i c he a c hv e r t e xr e p r e s e n t s ac r o s s i n ga n de a c he d g er e p r e s e n t sar o a d u n d e rs o m er e s t r i c t i o n s ，t h e o r i g i n a lg r a p h gi st r a n s f o r m e dt oan e wd i r e c t e d g r a p hg 1 o ra n o t h e rn e wu n d i r e c t e db i p a r t i t eg r a p hg t h e n ，w ep u tf o r w a r dan e wp r o b l e mo fg r a p ht h e o r y ：t h ep r o b l e mo n s t r o n gd i s t a n c e - - d o m i n a t i n gs e to f ag r a p h w ec a n p r o v et h a tad i r e c t e dd o m i n a t i n g s e to ft h en e wd i r e c t e d g r a p h g o ras p - - d o m i n a t i n gs e to ft h en e wu n d i r e c t e d b i p a r t i t e g i sas t r o n gd i s t a n c e - - d o m i n a t i n gs e to ft h eo r i g i n a lg r a p h g ，a n d ，i ti s n p h a r d a c c o r d i n gt oa b o v et h e o r e m s ，w ed e s i g nt w oa p p r o x i m a t i o na l g o r i t h m s a n dg i v et w o e x a m p l e s a b o v ea l l ，t h e m a j o ri d e ao ft h i s p a p e r i st h a tw ec a r l _ t r a n s f o r mt h e p r o b l e mo ff i n d i n gas t r o n gd i s t a n c e - - d o m i n a t i n gs e to ft h eo r i g i n a lg r a p hgt o t h ep r o b l e mo f f i n d i n gad i r e c t e dd o m i n a t i i 培s e to f t h en e wd i r e c t e d g r a p hg o r as p - - d o m i n a t i n gs e to ft h en e wu n d i r e c t e d b i p a r t i t e g 1 山东大学硕士学位论文 c h a p t e ro n ei s 8 1 l i n t r o d u c t i o n ，w h i c hi n t r o d u c e st h em a i nb a c k g r o u n do f t h ep r o b l e ma n ds o m eb a s i cd e f i n i t i o n su s e di nt h i sp a p e rs u c ha st h es h o r t e s t r o a d ， d o m i n a t i n gs e ta n ds o m et h e o r e m sa b o u td o m i n a t i n gs e t ，t h e nw ee s t a b l i s ht h eg r a p h m o d e lo ft h el o c a t i o no fu r b a n p o l i c ev a n s t a t i o n i n c h a p t e rt w o ，w e f i r s tt r a n s f o r mt h e p r o n e m o f f i n d i n g a s t r o n g d i s t a n c e 一d o m i n a t i n g s e to ft h e o r i g i n a lg r a p h gt ot h e p r o b l e mo ff i n d i n g a d i r e c t e dd o m i n a t i n gs e to fan e wd i r e c t e d g r a p hg 【t h e nw eg i v es o m er e l a t e d t h e o r e m sa n du s et h et h e o r y g i v e nb e f o r et od e s i g na na p p r o x i m a t ea l g o r i t h m ，t h e n s o l v e da n e x a m p l e ， i nt h el a s tc h a p t e r , w ef i r s te s t a b l i s han e w u n d i r e c t e d b i p a r t i t e g t h e nw e u s et h ed e f i n i t i o no f as p - - d o m i n a t i n gs e to ft h en e wu n d i r e c t e d b i p m - t i t e g 。t o g i v ea n o t h e ra l g o r i t h m t h e n ，w es o l v e dt h es a m ee x a m p l ea sb e f o r e 。a tl a s t w e t r a n s f o r mt h ep r o b l e mo f f i n d i n gas p - - d o m i n a t i n gs e to ft h eu n d i r e c t e db i p a r t i t e gt om a t h e m a t i c a lp r o g r a m m i n g k e yw o r d s ：u r b a n p o l i c ev a ns t a t i o n ，s t r o n g d i s t a n c e - - d o m i n a t i n g s e t ， d i r e c t e dd o m i n a t i n g s e t ，s p - - d o m i n a t i n gs e t 4 山东大学硕士学位论文 第一章绪论 在本章第一节我们介绍警车选址问题提出的实际背景，在第二节我们介绍一些常用 的图论术语，其它的图论术语在必要时再进行阐述。 第一节警车选址问题的提出 应急系统的研究具有非常重要的现实意义，日益成为人们研究的热点。社会的灾害 如交通事故、火灾、山洪暴发等发生时，救护人员和负责人员如何在最短的时间里赶到 出事现场，如何最大程度的减少损失? 科学的进步，为人类在发生灾害后最大程度的减 少损失提供了可能的手段。相关的紧急事件应急处理系统可以在相当程度上降低灾害给 人类带来的巨大损失。 紧急事件应急处理系统的建立一直就受到重视。在上世纪7 0 年代，美国的有关机构 已提出了相关理论，后来加拿大也建立了相关的警车应急系统，只是加拿大在建立模型 时只考虑顶点的情况，而没有考虑边上的点，模型建立的比较简单。1 9 7 3 年，美国的e m s ( e m e r g e n c ym e d i c a ls e r v i c e ) 条例迸一步规定了对乡村的紧急医疗救护必须在3 0 分钟 内到达，城市必须控制在1 0 分钟以内。这就进一步给出了紧急事件应急处理系统的应急 限制期，这是合理的。众所周知，紧急事件应急处理问题最显著的特点就是在时间的紧 迫性，决策者应能在较短的时间内完成救护方案，该方案应使人员、车辆等在尽可能短 的时间内到达事发地点以保证应急开始时间最早。紧急事件应急处理系统建立的目的就 在于使救护人员在规定时间内到达事故发生地点，以便于在最短时间内进行救助处理， 使损失达到最小。 紧急事件应急处理问题是如此重要以至于1 9 9 0 年美国颁布的危险品安全运输条例 ( t h eh a z a r d o u sm a t e r i a l s t r a n s p o r t a t i o nu r n f o r ms a f e t ya c t ) 明确地把应急反应能力列为 与危险品运输密切相关的六个重要因素之一。而我国近期也在医疗、地震、消防等方面 颁布了有关处理紧急事件法令或条例。如我国于1 9 9 5 年4 月颁布的破坏性地震应急条 例和1 9 9 9 年3 月实施的中华人民共和国防震减灾法对地震的应急和震后救灾活动 作了详细的规定。 近年来，国际学术界非常注重对应急问题的研究，从第一个应急管理国际组织 山东大学硕士学位论文 国际应急管理工程协会( t i m e m s ) 诞生之日( 1 9 9 4 年) 起，高水平的研究成果层出不 穷。这些成果几乎囊括了从信息获取到应急策略制定的方方面面，并且广泛运用于森林 火灾、地震、矿井塌陷、辐射性废料泄漏事故等具体灾害领域。 下面对国际的几个相关问题的最新研究成果给予说明： c s u b r a m a n i a 和s k e r p e d j i e v ( 1 9 9 8 年) 建立了从气象信息发布到信息获取的模型 结构，这使得应急管理者能够迅速、准确地获取可能到来的灾害信息。并且，通过集成 各种应急决策工具，管理者能够正确地制定出对付灾害的应急反应计划。 k z o g r a f o s ，c d o u l i g e r i s 和e t s o u m p a s ( 1 9 9 8 年) 提出了电力公司管理应急事件的 集成逻辑框架，其中包含三方面的优化决策：( 1 ) 对服务维护单元数目( s e r v i c er e s t o r a t i o n u n i t ss r u s ) 的估计；( 2 ) 每个s r u 责任区域的定义：( 3 ) s r u 的派遣策略。他们的研 究成果已成功应用于美国某电力公司。 j lw y b o ( 1 9 9 8 年) 研制了预防和营救森林火灾的决策支持系统，通过应用计算 机系统实现对火灾的监控。该系统的新颖之处表现在对不同国家的多个营救小组的数据 共享和信息互联。 在9 1 l 事件之后，紧急事件应急处理系统的建立受到越来越多的关注和重视。紧急 事4 4 ：处理的问题有多种，而紧急事件应急服务设旌的选址问题是建立紧急事件应急处理 系统的一个关键问题。实际上早在上世纪六、七十年代，人们就研究过紧急服务设施的 选址问题。例如，在文献 4 】中考虑了这样一个问题：一个城市要建立紧急服务设施，比 如防火站，如何在优先数目的位置中选取最少的位置建立设施，使得在规定时间或者距 离内能够给所有需要紧急服务的地方提供紧急服务。 选址问题是紧急事务处理系统问题里面的一个典型例子，解决了这个问题，那么其 他诸如1 2 0 救护、1 1 9 救火等问题都可以建立类似的系统去解决。 选址问题是这样的，在一个地区设置数量与位置合适的应急点，当某个地方出现紧 急事件时，可以由负责这个地区应急点在最短时间内去处理事件，做到既有足够的应急 点处理紧急事件又能保证能在最短的时间内到达事故现场，我们的目标是实现能够用最 少数目的应急点满足上述条件。 7 选址问题是运筹学研究的重要领域，已有许多成果，但以前的研究多集中于应急物 质供应点已知的的条件下对单一应急点的应急问题，且都是以总成本和总长度最小为目 标。如k - m e d i a n 问题是从若干点中选出k 个点使得总长度最小，也有考虑在最长距离不 6 山东大学硕士学位论文 超出限制下使得利润最大。而由于应急系统自身的特点，费用将不再是首要考虑的因素， 时问成为最为重要的因素，其首要目标是使得运输时间最小。k - s e r v e r 问题虽然也是要求 时间最快，但其考虑的是在k 个服务者不断变化位置时的在线算法，与我们要研究的问 题不同。它们都要求选择的点数为给定数k ，而许多情况下选点的个数并不是所关心的主 要因素，因此应急系统选址问题的选择的点数可能是不确定的。我们将借鉴已有研究成 果，结合实际情况设计应急警车选址模型和算法，并借助算例验证模型的可行性。 济南市公安局最近对市民做出承诺，在济南市二环以内市区的任何一处出现警情， 在五分钟之内一定会派足够数目的警车到达现场处理：而在济南市二环以外的郊区发生 事故或出现警情，在十分钟之内一定会派足够数目警车到达现场进行事故处理。为处理 问题方便，我们假设在紧急情况下警车在公路行驶可以一路绿灯，速度稳定在每小时四 十公里。那么我们在整个济南市哪些地方设置警点放置警车，在各个警点分别配置多少 辆警车，能使得设置警点数最少，配置的警车数量足够又不至于太闲置，并且使得所用 的建点费用尽可能的低，从而达到节省费用的目的，实现对市民的承诺昵? 问题分为两 个方面，一是如何选择警车设置点，使得在整个城市任何一处发生警情后，警车能够在 规定时间内从最近警点沿最短路行驶到达出事现场；一是如何配置各个警点的警车数目， 使得在整个城市任何一处发生警情后，在规定时间内肯定有足够数目的警车到达出事现 场进行处理，又使得建设警点的费用最少。 这就是一个典型的选址问题。本文针对上述实际例子，主要考虑的是问题的前一个 方面，即警车设置点的选址问题。对这个问题，我们受先考虑如何在济南市二环以内选 择警车设置点，在二坏以外可类似考虑。 山东大学硕士学位论文 第二节预备知识 下面我们介绍在本文中将要用到的一些基本知识。 首先引入图的一些基本概念。 定义1 2 1 2j ：图是指一个有序三元数组( v ，e ，妒) ，其中是非空的节点集，e 是 边集，而p 是关联踊数，它使g 的每条边对应于g 的无序节点对( 不必相异) 。若e 是一 条边，而“，v 是使得妒( 口) = ( “，v ) 的节点，则称e 连接“，v ，节点“，v 称为e 的端点。有 时也可省略关联函数妒，这样e = ( “，v ) ，称作p 与顶点“，v 关联。如果两条边与同一个 顶点关联，我们就说这两条边是相邻的，同样，如果两个顶点关联同一条边，我们也浇 这两个顶点是相邻的。端点重合为一点的边成为环，两条或两条以上边与同一对端点关 联，则称这些边为重边，既没有环又没有重边的图称为简单图。 在继续下面的工作之前，我们还需要知道一些其它的基本知识，如我们必须知道如 何求图中任意两点之间的距离，求两点之间的最短路算法等。下面有必要对相关概念、 理论作一下简单描述。 定义1 2 2 ：一般的，用v v 表示v 是图g 的任顶点，用x g 表示x 是图g 的任 意边上的点( x 可为一条边的端点，即图的顶点，也可以是边上的点) 。在边不赋权图g 中，两顶点“和v 之间的最短路是指连接u 和v 的含边数最少的一条路，“和v 的距离是指 它们之间的最短路中所含的边数，用d ( u ，v ) 表示。在边赋权图g 中( 即每条边e e 赋以 权值w ( e ) ) ，两顶点“和v 之间最短路是指连接“和v 的边权总和最小的一条路，“和v 的 距离指它们之间的最短路上的边权之和，也用d ( u ，v ) 表示。在边赋权图g 中，对任意边 e = 0 ，w ) 上的点z ，i e d ( u ，z ) 和d g ，w ) 分别为边e = 0 ，v ) 上点z 到端点“和。的长度，即 d ( u ，x ) + d ( x ，w ) = w ( e ) ，任一顶点v 与点x g 的距离是指连接顶点v 与点z 的最短路线的 长度，用d ( v ，x ) 表示，即d ( v ，x ) = m i n d ( v ，“) + d ( u ，x ) ，d ( v ，w ) + d ( 工，计) 。顶点子集s 量v 到 任一点x ( 包含z 为顶点的情况) 的距离是指s 中的所有顶点到点。的距离中的最小值， 用a ( s ，x ) 表示，即d ( s ，x ) 2 喈l a ( v , x ) 。而我们还要用到一个顶点到任意一条边p 的 s 山东大学硕士学位论文 距离的定义，用d ( u ，e ) = 1 2 w ( e ) + d ( u ，v ) + d ( u ，w ) ( v ，w 是边e 的两个顶点) 来表示，同时 顶点子集s e v 到边p 的距离则用d ( s , e ) = m 咖p 0 ，e ) 来表示。 由上面理论，给定一个常数，代表一辆警车在规定的时间内从警车所在点到达警 情发生地点所走过的路程的极大值，那么在图上只要两点之间的最短路小于这个数，警 车就能在规定时间内从一点到达另一点，那么就说这两点可以相互控制，任一点都可以 作为控制点。这儿我们所说的控制集已不仅仅是顶点对顶点的控制了，还有顶点对边上 的点的控制。 下面介绍求解两点之间最短路的d i j k s t r a 算法和f l o y d 算法。 d i j k s t r a 算法和f l o y d 算法是两个最经典的求解最短路的方法。d i j k s t r a 算法一般用 于解决权值为正情况下的两顶点之间最短路问题，该方法简便易行，但对于更复杂的情 况求解效率不高或无法求解。例如要计算图中任意两点之间的最短路或存在负边权时。 f l o y d 算法却可解决该问题，而且当权值为负时，可以探测网络中的负圈。 本文将主要用到求解图中任意两点之问的最短路的算法，故此我们将主要用到f l o y d 算法。在没有负圈的网络中任意一条途径的长度不小于相应的最短路，并且最短路的 子路一定电是最短路，这是下面讨论的基础。 我们汜n ( i ，m ) 表示由顶点集合 v u v ，j u v ，v 。 生成的n 的子网络。特别 n ( i ，o ) 表示由顶点集k u 扣， 生成的子网络。我们把网络n ( i ，歹，m ) 中从v ，到v ，的最短 路长度记为“，。( m ) 。我们同时引入“后点标号”，令s ，( 晰) 表示_ ，( m ) 的第一条弧 的终点，则s 。( 0 ) 2 ，是显然的； 如果s 。= 沏一1 ) 已经求出，当”w 一1 ) t l i , m 一1 ) + 1 一l m , j 沏一1 ) 时，显然有 s 。( m ) = s 。( m 一1 ) ；否则的话，s 。( 州) 5 s 。一1 ) ，s 。( m ) 就是最终得到的后点标号。 要求v ，到v ，的最短路，若s 。) 。k ，则最短路的第一条弧为( v 。，v 。) ，第二条弧为“目 的第一条弧，以此类推，加上后点标号的f l o y d 算法i l l 女1 ；i 下： ( s o ) ( 准备) ：令“u ：= w ，s u ：- j ( f ，j = 1 , 2 ，m ) ，m 1 ： 生堡奎兰堡主兰垡堡壅 _一 ( s i ) ( 迭代) ：对1 n ，1 蔓m ，令s u ：= s u ( 当“w 兰“+ “m j ) ，否则令 s ：= ( s ，m ， 当“叫“。，+ i d m , j ) ，“叫：= r a i n ( “u ， “，+ “j ) ( s ：) ( 判断结束) ：如果m = ，停止；否则，令m ：+ 1 ，转( s 。) 。 注1 ：这个算法适合在矩阵上进行运算。 我们发现这个算法只适合于求顶点到顶点的最短路，但我们接下来会发现我们在做 一个转化后，顶点到边上的最短路问题也可以用此方法求解。 下面引入边不赋权图的控制集的定义。 定义1 2 3 【2 】：我们用n ( s l = ( 。i v v ，v 和s 中的顶点相邻) 表示图g 中关于顶点 子集s v 的邻集。 定义1 2 4 ：给定无向图g = ( y ，e ) 及顶点子集s 矿，若对矿一s 中的每一个顶点v ， 在s 中都有个顶点与其相邻( 即d ( s ，v ) = 1 ) ，则称s 为图g 的一个控制集( d o m i n a t i n g 州) ，或叫支配集i “。图g 的含顶点个数最少的控制集称为图g 的最小控制集。图g 的 最小控制集所含顶点的个数称为图g 的控制数，用d o m ( g ) 表示。求图g 的最小控制集的 问题称为图的控制集问题。 对图的一个控制集s ，它能在一步内控制p ，一s 中的顶点，即s 与矿一s 中的每个顶 点之距离是1 。文献【4 1 b o n d yja ，f a n g 对控制集的概念做了推广，由顶点子集在一步 内控制其余顶点推广到顶点子集在七步内控制其余顶点，即对图的一个顶点子集，它与 其余的每个顶点之间的距离至多是未。 定义1 2 5 【4 l ：给定图g = ( 矿，e ) 及顶点子集s i 矿，若对矿一中的每一个顶点v ， 在s 。中都存在一个顶点与它之间的距离不大于t ( 即a ( s 。，v ) k ) ，则称最为图g 的一 个k 一控制集( k - - d o m i n a t i n gs e t ) 。图g 的含顶点个数最少的女一控制集称为图g 的最 小一控制集。图g 的最小一控制集所含顶点的个数称为图g 的七一控制数，用 d o r t l 。( g ) 表示。求图g 的最小七一控制集的问题称为图的七一控制集问题。 我们以上的讨论都是在边不赋权图上进行的，这相当于假设在实际当中，每两个路 口之间的路的长度是相同的，即不论路长路短，只要是一条路，那么就假设警车可以从 生查奎堂堡圭堂堡鲨兰 路的一端在规定时间内到达另一端，也就是说在图上只要两点相邻就说这两点相互控制， 而没有考虑两点不相邻的情况。在实际问题中，每一条路的长度一般是不相同的，不能 仅用是不是相邻就判断这两点能不能相互控制，也就是说，两个点即使不相邻，也能相 互控制。 举例说明，如下面的正方图( 1 ) ( 设这个图边长为1 0 ) ，图中两点h 和e 之间有三条 边，但是每条边都比较短，那么如果一开始给定的常数比较大，设为1 1 ，那么我说点 h 和e 能够相互控制。也就是说，有一辆警车在某一点也可能在规定时间内到达隔三个路 口外的紧急事件发生地点。 图i 如下： ( 图1 ) 通过上面分析，我们有必要对我们前面的控制集理论作一下改进和推广，我们需 要将控制集的概念由边不赋权图推广到边赋权图。 定义1 2 6 ：给定边赋权图g = ( v ，e ) ，每条边e e 赋以权值w ( e ) ，再给定一个常 数。对顶点子集s v ，若对v s 中的每一个顶点v ，在s 中都有一个顶点与它之间 的距离不大于r o ( 即a ( s ，v r o ) ，则称s 为边赋权图g 的一个距离，0 一控制集( d i s t a n c e d o m i n a t i n gs e t ) 。图g 的含顶点个数最少的距离控制集称为图g 的最小距离 一控制集。图g 的最小距离厂。一控制集所含顶点的个数称为图g 的距离一控制数，用 山东大学硕士学位论文 d d o m 。( g ) 表示。求图g 的最小距离一控制集的问题称为图g 的距离r o 一控制集问题。 距离一控制集把边赋权图的其余顶点控制在一个给定的距离常数r o 之内：每个顶点到 这个集合的距离都不超过h 。 因为我们的警车选址问题是要求求出的警车控制点能够对路上的每一点都能控制， 也就是说，我们求的一个图的控制点不仅要能控制图上的顶点，还要能控制边上的所有 点。那么下面我们对距离一控制集的概念进行推广，使得一个顶点子集能用一个给定 的距离常数控制边赋权图的顶点和边上的所有点。 定义1 2 7 ：给定边赋权的图g = ( 矿，e ) ，每条边f = ( v ，v ：) e 燃n w ( e ) ，再给 定一个常数，对顶点子集s ，若x c g 的边上的每个点x ，在s 中都有一个顶点与它之间 的距离不大于( 即d ( s ，x ) r o ) ，则称s 为边赋权图g 的一个强距离一控制集( s t r o n g d i s t a n c e - - r o - - d o m i n a t i n gs e t ) 。 图g 的含顶点个数最少的强距离一控制集称为图g 的最小强距离一控制集。图 g 的最小强距离r o 一控制集所含顶点的个数称为图g 的强距离，0 一控制数，用 s d d o m 。( g ) 表示。求图g 的最小强距离一控制集的问题称为图g 的强距离r n 一控制集 问题。 定理1 2 1 ：对图g = ( y ，e ) ，有d o m ( g ) d o m k ( g ) 。 证明：显然若顶点子集s 是图g 的一个控制集，则s 也是图g 的一个七一控制集， 故成立a 口 定理1 - 2 2 ：对边赋权图g = ( 矿，e ) 及任意给定的常数，确r s d d o m ( g ) d d o m 。( g ) 。 并且当每条边的权值都不大于时，确- d o m ( g ) d d o m 。( g ) 。 证明：若s 是图g 的强距离，o 一控制集，n s 也是图g 的距离一控制集。当每条 边的权值都不大于时，若s 是图g 的距离，0 一控制集，则s 也是图g 的控制集。口 在参考文献 3 中已经证明了一个图的控制集问题是n p h a r d 的，因为强距离一控 山东大学硕士学位论文 制集问题可以在多项式时间内转化为一个控制集问题，故此强距离b 一控制集问题也是 n p h a r d 的。 通过上面的分析，我们知道警车选址问题主要就是找到这样的一个顶点集合，使得 这个顶点集合的点能够控制图上的所有顶点和所有边上的点，即找图的一个强距离一 控制集。 山东大学硕士学位论文 第三节建立图论模型 通过上面的分析，我们知道警车选址问题可以转化成求解图的一个强距离一控制 集问题。我们将在本节建立警车选址问题的图论模型。 首先考虑本文一开始提出的警车选址问题的前提，要求警车能够在五分钟之内以速 度4 0 公里小时行驶赶到事情出发地点。警车5 分钟能行驶毒。4 0 ：丝公里，因而5 分 6 03 钟之内每辆警车能够从警车设置点抵达最远距离为学公里的出事现场。我们通过上面的 j 分析，知道可以把济南市的各个路口看作顶点，两条路口之间的公路段看作连接两个顶 点的一条边，而这条路段的长度看作这条边的权重，我们得到一个边赋权的图g = ( v ，e ) 。 为了考虑问题方便，先给出一个特别的假设：警车都设置在路口( 当然在实际中，求出了 设置警点的路口后，还要适当考虑现有的警局或派出所的位置，以恰当的利用已有的设 施，减少费用) 。因在实际中，城市中的每条路的长度w ( e ) f ：粤1 ，所以我们一般取 j = ；。因为服务对象( 即出事地点) 可以分布在道路的任意点或者小区内，我们为考 虑问题方便，认为出事地点只在顶点和边上。我们用图的顶点特指路口，而边上的任意 点泛指出事地点。因为警车选址问题的目的是如何选取最少的警车设置点，使得在公路 的任意地点发生事故后，都能在相关的某个警车设置点派出警车，使得5 分钟之内到达 出事现场去处理警情，或者说至少有某个警车设置点距离出事地点不超过= i u 公里，也就 j 是说这个警车设置点可以娑一强距离控制这个出事地点。令：l o ，则图g ：( 矿，e ) f l 勺 强距离玮一控制集问题就是警车选址问题的图论模型。 注2 ：我们建立的关于强距离控制集问题的模型不仅可以用来描述警车设置点的选址问 题，而且可以描述一类为某个城市或地区应付紧急情况或事件而为紧急设施设点的问题， 如1 1 0 ，1 2 0 ，1 1 9 服务系统的设点问题等等。 1 4 些查态兰堡主兰些笙塞 一一一一 第二章警车选址问题的算法( 一) 第一节转化成一个有向图 通过上面的分析，我们知道警车选址问题可以转化为在个图上求解一个强距离 一控制集问题。但是求解一个图的强距离一控制集比较困难，我们试图将它转化为求 解一个图的控制集问题。为此我们希望构造一个新图，使彳导这个新图的一个控制集就是 原图的一个强距离一控制集，那么问题就变成了在一个图上求解一个控制集了，它相 对容易一些。 下面我们构造一个新的有向图，使得它的有向控制集是原图的强距离一控制集。 我们首先令e ( v ) = 知f e 与点v 关联) ，令w ( v ) = 。m 。a ( x 。) w q ) 表示点- ，的所有关联边的长 度中的最大值，然后构造新图g t 如下： 构造新图g i ：给定图g = ( 矿，e ) 和常数，o ，把每条边p = ( v ，v ：) 引赋以权值w ( p ) ，且假 设w ( p ) 矗。构造一个顶点集不变的新的有向图g i = ( k ，巨) j n t ：先令与= ，对任意顶 点“e 矿及v e 矿，只要d ( v ，“) + j 1w ( v ) ，就连一条从顶点“指向顶点v 的弧，同时把弧 ( ) 并入岛。 定义2 1 1 ：在有向图g l = ( k ，巨) 中，如果有一条从顶点“指向顶点v 的弧0 ，v ) e ， 我们就称顶点“有向控制顶点v ，同时称顶点“为弧( “，v ) 的始端，顶点v 为弧0 ，v ) 的末端 或终端，即顶点v 是顶点“的外邻点。弧0 ，v ) 称为顶点“的出弧，称为顶点v 的入弧。 定义2 1 2 ：给定有向周g 1 = ( k ，五) 及顶点子集s k ，若对k s 中的每一个顶点 v ，都存在一个顶点s ，使得弧0 ，v ) e l ，贝称s 为图g l 的一个有向控制集( d i r e c t e d d o m i n a t i n gs e t ) 。图g l = ( k ，巨) 的含顶点个数最少的有向控制集称为图g 。的最小有向控 制集。图6 l 的最小有向控制集所含顶点的个数称为图g l 的有向控制数，求图g 。的最小 山东大学硕士学位论文 有向控制集的司题称为图的有向控制集问题。 我t 1 i i 过上面的构造过程可以得到一个新的有向图g m = ( k ，e 1 ) ，下面的定理保证了 g 1 = ( k ，e i ) 的一个有向控制集，就是原图g = ( 矿，) 的一个强距离吃一控制集。 定理2 1 1 ：我们通过上面的构造过程，得到一个新的有向图g i = ( k ，蜀) ，设s 是它 的一个有向控制集，则对原图g = ( y ，占) 的任意点x e g ，有d ( s ，x ) r o ，即s 就是原图 g = ( y ，e ) 的一个强距离n 一控制集。 证明：不妨设s = ，“2 ，“矧) 。设点x 在图g = ( 矿，e ) 的边p = ( h ，v 2 ) e 上。 显然， 当边g 的两个端点v 。和v ，至少有一个属于s 时， 有 d ( s ，x ) m i n d ( v 】，z ) ，d ( v 2 ，x ) ) w ( p ) 冬成立。 而当边p 的两个端点v ，和v ：都不属于s 时，我们分两种情况讨论： ( 1 ) 若_ 和v 2 在图g i 中部被s 中的同一顶点甜有向控制，即( “，v 1 ) e l 和 ( “，v ：) ee ，由构造过程，我们知道如，v 1 ) + 三喇勺和撕，晚) + 三荆龟，则有： d ( s ，x ) 积甸 互i 陬v 1 ) + 心) + m ，v 2 ) 5 i i g 。饥) 。r 0 ： ( 2 ) 若h 和v ：在图g 中分别被s 中不同的两个顶点有向控制，不妨设这两个顶点 是毪和“：，即( “l ，v t ) 五l 和( u 2 , v 2 ) 毛，由构造过程知，有d ( u 。, v o + 妻w 0 ) 和 d ( u 2 , v e ) + 昙w 0 ) 蔓r o 成立，则有： d ( s ，工) m i i d 0 i ，n d u 2 ，工) ) ： 弛，v 。) + 喇+ 妣，v 2 ) 】 山东大学硕士学位论文 5i 1 ) = ，0 综上，若s 为图g l 的一个有向控制集，则对图g 上的任意点x g ，有d ( s ，x ) r o ， 即s 为图g = ( y ，昱) 的一个强距离一控制集。口 山东大学硕士学位论文 第二节通过有向控制集理论给出一个算法 由第一节，我们知警车选址问题可以转化成在一个图上求解一个强距离一控制集 问题，进而化成在我们构造的一个有向图g 。= ( 巧，e 。) 上求解一个最小有向控制集问题。 下面我们给出一个求解这个有向图的极小有向控制集的一个算法： 算法1 ： 步骤1 ：给定有向图g l = ( k ，e 0 ，按照图g 1 = ( h ，e 1 ) 的各顶点的出度从大到小的顺序 排列，令s ：= ： 步骤2 ：首先选取出度最大的顶点“e 以，然后把顶点“及它的外邻点去掉，令 s ：= s u 如 ； 步骤3 ：再在剩下的图上继续上面的过程，直到剩下的顶点全都是孤立点，则把孤 立点加入到s 中，所得到的点集合s 就是所求的有向控制集。 定理2 2 1 ：我们通过上面算法l 得到的集合s 是一个极小有向控制集。 证明：假设集合s 不是一个有向控制集，那么必然存在一个顶点v v s 不被任何 顶点v s 所有向控制，那么顶点v ，必然存在指向某个顶点v ：s 的弧，也就是这一点v 有 出度，那么根据算法1 ，应有点v ，s ，矛盾，故集合s 是一个有向控制集。 又因为如果s 不是极小的，则必然存在一点v s 可以去掉，使得集合s 的元素减少， 那么这一点v 可以被s 中其它点有向控制。根据算法这一点就不能被选进集合s 中，矛盾， 故此，集合s 是一个极小有向控制集。 口 下面我们举例说明如何用算法l 去求解一个有向图的极小有向控制集，进而求解警 车选址问题。 例一：- 令r o = 1 2 ，求下面图g 的一个强距离，o 一控制集( 见图3 ) 。我们令： ( “i ，“2 ) = e 】= 5 ，( “2 ，“3 ) = 已2 = 5 ，( 甜3 ，“4 ) = 8 3 = 9 ，( “4 ，“5 ) = e 4 = 5 ，( “5 ，“6 ) = e 5 = 8 ， 山东大学硕：l 学位论文 ( “6 ，“1 ) = 9 6 = 5 ，( “4 ，“6 ) = p 7 = 7 ，( “l ，“4 ) = 已8 = 8 ，( 甜】，“3 ) = p 9 = 8 ( “3 ，“8 ) = 已】o = 4 ，( “7 ，“8 ) = e l i = 9 ，( “5 ，“7 ) = g 】2 = 5 ，( “4 ，“7 ) = 已】3 = 4 u 6 ( 图3 ) l 1 8 解：我们首先根据有向图g 1 = ( k ，局) 的构造过程来构造g l = ( k ，e 1 ) ，那么我们需要首先计 算各点之间的最短路，然后根据是否有d ( v ，“) + i 1v v ( v ) ，o 来判断两个顶点v ，“之间是否连 一条边。 各点之间的最短路计算如下： d ( u 1 ，u 2 ) = 5 ，d ( u l ，“3 ) = 8 ，d ( u l ，“ ) = 8 ，d ( u l ，“5 ) = 1 3 ，d ( u i ，“6 ) = 5 ，d ( u 1 ，“7 ) = 1 2 ， d ( u i ，“8 ) = 1 2 ，d ( u2 ，) = 5 ， d ( 2 f 2 ，“4 ) = 1 4 ，d ( u 2 ，“5 ) = l8 ，d ( u 2 ，“6 ) = 1 0 ， d ( u 2 ，“7 ) = 1 7 ，d ( u 2 ，“8 ) = 9 ， d ( u 3 ，“4 ) = 9 ，矗 3 ，“5 ) = 1 4 ，d ( u 3 ，“6 ) = 1 3 ， d ( u ，“7 ) = 1 3 ，d ( u 3 ，“8 ) =