







動物社區最近發生了一起盜竊事件,水牛先生祖傳的鉆石鋼筆不翼而飛,藍貓警長很快就捕獲了兩個小偷。
為了保護社區居民的生命財產安全,藍貓警長決定組織一支社區巡邏隊,從社區居民中挑選2 位居民,每天交替巡邏。
“我報名!”“還有我!”大家都可積極了。
藍貓警長綜合考慮了大家的時間和體力,最終選定了5位候選人—水牛先生、棕熊先生、羚羊小姐、斑馬女士和駝鹿大哥。
這5 位巡邏隊候選人分別住在這些地方:
為了保證效率,不耽誤居民太多時間,藍貓警長決定:
1. 巡邏時,不能走重復路線,但可以多次經過同一戶人家;
2. 每個巡邏的人都要從自己家出發,但終點不必一定是自己家。
“誰能同時滿足這幾個要求呢?”藍貓警長看著地圖,思考了起來。他很快就發現,只有兩位候選人可以滿足要求。
藍貓警長是怎么看出來的呢?
首先將這個問題簡化,我們將每個居民的住處看作一個點,住處之間的道路看作邊,就可以得到一張社區地圖的簡圖:
這樣我們就可以發現,這個問題本質上是個“一筆畫”問題,我們接下來要做的就是找出一筆畫的起點和終點。
如果隨便挑一個點亂走,不斷嘗試下去,當然也能找出一筆畫的路線,但這樣做效率實在太低了,所以我們還是要先找到“起點”。
注意巡邏路線的要求:每戶人家可以重復經過,每條路都必須走,但都只能走一次。也就是說,當你經過一個點時,那個點必須有2 條邊或者其他偶數條邊,這樣你就可以從一條邊進入,再從另一條邊離開。
經過一個點時,就可以不走重復的邊。
只有兩個點例外:起點和終點。
起點只用“離開”,不用“進入”;終點只用“進入”,不用“離開”。所以起點和終點可以有奇數條邊。
再結合簡圖看,圖中只有A、B 兩點連接的邊數是奇數,也就是說,只有A、B 點可以作為起點和終點。
再結合簡圖看,圖中只有A、B 兩點連接的邊數是奇數,也就是說,只有A、B 點可以作為起點和終點。
藍貓警長分析完,確定了水牛先生和棕熊先生作為巡邏隊隊員,并且為他們每個人各設計了一條巡邏路線。有了他們倆的幫忙,動物社區的治安越來越好了。
這是水牛先生從A 點出發的路線:
這是棕熊先生從B 點出發的路線:
你能給出更多的巡邏路線嗎?