下面是城市公園的地圖,圖中所列數(shù)字以m為單位。每天早上公園開門前,清潔工人必須開著清潔車打掃公園內(nèi)所有的街道。該清潔車位于H點(diǎn)。令清潔工人感到很困擾的是,欲清掃完公園內(nèi)所有的街道,似乎不可能不走重復(fù)的路段。這種情形真的無法避免嗎?
你能說出清潔車清掃完所有路段再回到H點(diǎn)的最短路徑嗎?
解答與分析
清潔工人不可能清掃完所有的路徑而沒有任何一條路段重復(fù)。最短的路徑是 1560 m(其中 1330 m是清掃路徑, 230 m是重復(fù)經(jīng)過的路徑),欲走完所有路徑必須重復(fù)經(jīng)過AB、HG及IF。下面為最短路徑的一個(gè)例子:
H B C D H I D E F I F G H G A B A H
本題的數(shù)學(xué)分析基礎(chǔ)在于該路徑所形成的網(wǎng)路中奇結(jié)點(diǎn)和偶結(jié)點(diǎn)的分布情況。