城市警車選址問(wèn)題.pdf

1、該文主要是解決實(shí)際問(wèn)題中提出的城市警車選址問(wèn)題.我們把城市看成一個(gè)平面圖G,假設(shè)圖的頂點(diǎn)表示路口,圖的邊表示路,然后在此圖上進(jìn)行分析.我們根據(jù)控制集理論提出圖論上的一個(gè)新問(wèn)題——圖的強(qiáng)距離控制集問(wèn)題,為解決此問(wèn)題,我們通過(guò)一定的方法,把圖G轉(zhuǎn)化成另外的新的有向圖G<,1>或無(wú)向圖G<'1>,并證明了新的有向圖G<,1>的有向控制集和無(wú)向二分圖G<'1>的SP—控制集都是原圖G的強(qiáng)距離控制集,并給出了相關(guān)的定理,然后設(shè)計(jì)了相關(guān)算法,并分別

2、舉例進(jìn)行分析比較.該文主要思想是把在原G上求一個(gè)強(qiáng)距離控制集化為在轉(zhuǎn)化后的新的有向圖G<,1>上求一個(gè)有向控制集或無(wú)向二分圖G<'1>上求一個(gè)SP—控制集.在第三章我們首先在第一節(jié)構(gòu)造了一個(gè)無(wú)向二分圖G<'1>,給出了SP—控制集的概念,并證明了新圖G<'1>的SP—控制集是原圖G的一個(gè)強(qiáng)距離控制集,并給出了相關(guān)定理;在此基礎(chǔ)上在第二節(jié)我們?cè)O(shè)計(jì)了另外一個(gè)求解警車選址問(wèn)題的近似算法,同時(shí)也給出了相關(guān)的算例,并與上一節(jié)的算例作了分析比較;第