圖論在計(jì)算機(jī)科學(xué)中應(yīng)用

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

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

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