圖論在計算機科學中應用

圖論是一門古老的數(shù)學分支，它起源于游戲難題的研究，如1736年歐拉所解決的哥尼斯堡七橋問題，以及迷宮問題、博弈問題、棋盤上馬的行走路線問題等。同時，圖論又是近年來發(fā)展迅速且應用廣泛的一門新興學科，已滲透到諸如語言學、物理學、化學、電訊工程、計算機科學以及數(shù)學的其它分支中，特別在計算機科學中，如形式語言、數(shù)據(jù)結構、分布式系統(tǒng)、操作系統(tǒng)(cāozuòxìtǒnɡ)等方面均扮演重要的角色。第一頁，共十五頁。歐拉圖歐拉圖的概念是瑞士數(shù)學家歐拉（LeonhardEuler）在研究哥尼斯堡（Knigsberg）七橋問題時形成的。在當時的哥尼斯堡城，有七座橋將普萊格爾（Pregel）河中的兩個(liǎnɡɡè)小島與河岸連接起來（見圖3.1（a）），當時那里的居民熱衷于一個難題：一個散步者從任何一處陸地出發(fā)，怎樣才能走遍每座橋一次且僅一次，最后回到出發(fā)點？第二頁，共十五頁。這個問題似乎不難，誰都想試著解決，但沒有人成功。人們的失敗使歐拉猜想：也許這樣(zhèyàng)的解是不存在的，1936年他證明了自己的猜想。

為了證明這個問題無解，歐拉用A，B，C，D四個頂點代表陸地，用連接兩個頂點的一條弧線代表相應的橋，從而得到一個由四個頂點、七條邊組成的圖（見圖3.1（b）），七橋問題便歸結成：在圖3.1（b）所示的圖中，從任何一點出發(fā)每條邊走一次且僅走一次的通路是否存在。第三頁，共十五頁。歐拉指出，從某點出發(fā)再回到該點，那么中間經(jīng)過的頂點總有進入該點的一條邊和走出該點的一條邊，而且路的起點與終點重合，因此，如果滿足條件的路存在，則圖中每個頂點關聯(lián)的邊必為偶數(shù)。圖3.1（b）中每個頂點關聯(lián)的邊均是奇數(shù)，故七橋問題無解。歐拉闡述七橋問題無解的論文通常(tōngcháng)被認為是圖論這門數(shù)學學科的起源。第四頁，共十五頁。圖3.1第五頁，共十五頁。計算機鼓輪設計(shèjì)問題第六頁，共十五頁。圖3.4第七頁，共十五頁。計算機鼓輪設計問題設計旋轉鼓輪，要將鼓輪表面分成16個扇區(qū)，如圖3.4（a）所示，每塊扇區(qū)用導體（陰影(yīnyǐng)區(qū)）或絕緣體（空白區(qū)）制成，如圖3.4（b）所示，四個觸點a、b、c和d與扇區(qū)接觸時，接觸導體輸出1，接觸絕緣體輸出0。鼓輪順時針旋轉，觸點每轉過一個扇區(qū)就輸出一個二進制信號。問鼓輪上的16個扇區(qū)應如何安排導體或絕緣體，使得鼓輪旋轉一周，觸點輸出一組不同的二進制信號？第八頁，共十五頁。

顯然，圖3.4（b）所示，旋轉時得到的信號依次為0010，1001，0100，0010，…，在這里，0010出現(xiàn)了兩次，所以這個鼓輪是不符合設計要求的。按照題目要求，鼓輪的16個位置與觸點輸出的16個四位二進制信號應該一一對應，亦即16個二進制數(shù)排成一個循環(huán)序列，使每四位接連數(shù)字所組成(zǔchénɡ)的16個四位二進制子序列均不相同。這個循環(huán)序列通常稱為笛波濾恩（DeBruijn）序列。如圖3.4（c）所示，16個扇區(qū)所對應的二進制循環(huán)序列正是笛波濾恩序列。第九頁，共十五頁。圖3.4第十頁，共十五頁。我們構造一個有8個頂點(dǐngdiǎn)的有向圖，頂點(dǐngdiǎn)為8個三位二進制數(shù)000,001,010,011,100,101,110,111，可分別記為v0,v1,v2,v3,v4,v5,v6,v7，下標正好是頂點的十進制表示。如果某個頂點vi的二進制表示的后兩個數(shù)字與另一個頂點vj的二進制表示的前兩個數(shù)字相同，則由向引一條有向邊ek，k是十進制數(shù)，對應i和j二進制表示將重合的數(shù)字只算一次的四位二進制數(shù)。例如，e1=<v0,v1>=<000,001>=0001，e7=<v3,v7>=<011,111>=0111,…。這樣構造出一個連通有向圖G，如圖3.5所示。第十一頁，共十五頁。圖3.5圖3.5每個頂點的出席均與入度相同，故為有向歐拉圖，含有一條有向歐拉回路，回路中每條邊均標記(biāojì)著一個不同的四位二進制數(shù)，可見，對應于圖的歐拉回路，存在一個16個二進制數(shù)組成的循環(huán)序列，其中每4個接連的二進制子序列均不相同。e6=0110第十二頁，共十五頁。圖3.5例如，對應(duìyìng)于歐拉有向回路:e0e1e3e7e15e14e12e9e2e5e11e6e13e10e4e8e0e6=0110對應于上述的歐拉有向回路的16個二進制數(shù)組成(zǔchénɡ)的循環(huán)序列是：0001111001011010把這個序列排成一個圓圈，與所求的鼓輪相對應，就得到鼓輪設計。第十三頁，共十五頁。用類似的方法，我們可以證明：存在一個2n個二進制數(shù)組成的循環(huán)序列，其中2n個由n個接連的二進制數(shù)組成的子序列均不相同(xiānɡtónɡ)。這個序列對應的歐位有向圖稱為笛波濾恩圖，記作G2,n.圖3.5中的圖記為G2,4。第十四頁，共十五頁。內(nèi)容(nèiróng)總結圖論是一門古老的數(shù)學分支，它起源于游戲難題的研究，如1736年歐拉所解決的哥尼斯堡七橋問題，以及迷宮問題、