第1章 圖論模型

本章中我們著重介紹圖論相關(guān)的一些模型和算法.先從一個經(jīng)典的圖論模型——哥尼斯堡七橋問題談起.

18世紀初在普魯士的哥尼斯堡城有一條河穿過城市的中心，河中分布著兩個小島，這兩個島與河岸由七座橋連接起來，如圖1.1（a）所示.有人提出一個有趣的問題，即一個步行者怎樣才能不重復、不遺漏地一次走完七座橋，最后回到出發(fā)點.這一問題被命名為哥尼斯堡七橋問題，也被認為是圖論學科的起源.這個問題看似非常簡單，但是卻難住了當時博學的教授們，最后大數(shù)學家歐拉解決了這一問題.他解決這一問題的過程可以看作是一個簡單的數(shù)學建模過程.

第一步，我們把這個問題的本質(zhì)提煉出來，即人們分別在岸上和島上行走的路線與距離，橋的形狀長度與本問題無關(guān)，我們只需要關(guān)注過橋的順序.基于這一考慮，第二步我們可以分別用四個點來表示河的兩岸和河中的島嶼，而用點之間的連線表示連接它們之間的橋，這樣我們就得到了一張簡單的圖，如圖1.1（b）所示.我們所要求解的問題就轉(zhuǎn)化成了是否可以從圖中一點出發(fā)，經(jīng)過每條連線恰好一次回到起點.第三步，我們觀察到在經(jīng)過圖中點時必然由一條連線進另一條連線出，因此我們所要求的走法存在的必要條件是圖中每個點相關(guān)聯(lián)的連線數(shù)目是偶數(shù)，從而得出結(jié)論，哥尼斯堡七橋問題中所要求的走法是不存在的.

下面我們再給出一個看似和圖無關(guān)，但可由圖來巧妙解決的問題——過河問題.

一只狼，一只羊，一筐菜位于河的同側(cè).一個擺渡人要將它們運過河去，由于船小，運力有限，一次只能載三者之一.很顯然，狼和羊，羊和菜都不能在無人監(jiān)視的情況下留在一起，那么擺渡人應該怎樣把它們運過河呢?

我們的目標是將羊，狼，菜從河的一邊運到另一邊，在每次擺渡發(fā)生后，羊、狼、菜中最多一個以及人的位置會發(fā)生變化（即從河岸的一邊到另一邊），而根據(jù)題意，其中一些位置的組合是不可以出現(xiàn)的.因此，整個擺渡過程可以看成是狼、羊、菜、人的位置的可行的變化過程.我們可以建立一張圖來刻畫這一過程.不妨設開始三者都在河的北岸，需要運到南岸.

我們用一個長度為4的0,1序列來表示人、羊、狼、菜在擺渡發(fā)生前或后的位置，其中1表示北岸，0表示南岸.根據(jù)要求，我們列出可能的10種狀態(tài)，分別用平面上10個點來表示，對于它們當中任何兩個點，用一條線相連，當且僅當這兩點所表示的位置狀態(tài)可以通過一次擺渡轉(zhuǎn)化.這樣我們就得到了一張圖（見圖1.2），而圖中從點（1,1,1,1）經(jīng)過一些邊到點（0,0,0,0）的每一種走法都對應一種可行的擺渡方案.

如果我們需要找一個最好的方案，很自然就是要找經(jīng)過邊最少（擺渡次數(shù)最少）的方案.這點可以通過圖論中的最短路徑算法實現(xiàn)，我們會在后面的章節(jié)中介紹這一算法.

不論是哥尼斯堡七橋問題還是過河問題，我們所建立的模型都是一張簡單的“圖”，而它就是圖論這一學科主要的研究對象.就是這樣一個簡單的模型與現(xiàn)實生活有著緊密的聯(lián)系，有著廣泛的應用.如圖1.3所示是本章所要介紹的模型的關(guān)系結(jié)構(gòu).