轉信站: GIBBS!news2.ncku!ctu-gate!news.nctu!news!news-peer.gip.net!news.gsl.net

          **************************************** 
             SciScape 新聞 (http://leos.bu.edu/)   
          **************************************** 

[Jul 06, 00] 警察與相變化

一個城市需要有多少個警察才能監視著所有的街道？對數學家而言這
是一個相當困難的問題，他們稱這個問題為交點覆蓋問題"vertex 
cover(VC)problem"。現在物理學家更發現這其實還是個相變化
(phase transition) 的問題。Goettingen 大學的Weigt和Hartmann
日前發表了一篇論文，說明這個題目在城市越來越大的時候，會從一
開始的不容易處理變得越來越容易。
 
解決這個問題有兩個方法，一是安排警察在街道交點上，一是證明沒
有辦法找出排列的方法。當警察數目很多的時候，自然可以安排在所
有的交點上，而當交點數目遠超過警察數目的時候，要監視整個城市
其實是不可能的。除去這兩種容易處理的極端狀況，其他的情形就相
對比較不容易處理。

這個問題可簡化成三個參數，一是城市的大小，決定交點的數目，同
時假設每條街道是隨意連接的。二是相連程度，也就是每個接到交點
的街道數目。三是有警察的交點比例。如果以一般的小城做模擬(四
十個交點，連接程度為二)也要花上相當長的時間。

Weigt 和Hartmann兩人證明了這個問題具有相變化的性質。這個問題
在連結程度為二，具有警察的交點比例為小於20%及大於40%時容易用
電腦處理。在30%至40%時，電腦需要更多處理的時間。

--摘譯自:
Nature Science Update 06/30/00: Covering all bases
<http://helix.nature.com/nsu/000706/000706-1.html>

 -- 責任編輯: John C. H. Chen <chchen@tpts1.seed.net.tw>