城市警車選址問題.pdf

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

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