歐拉回路性質(zhì)與應(yīng)用探究VIP

1、歐拉回路性質(zhì)與應(yīng)用探究 【摘要】歐拉回路，又稱“一筆畫”，是圖論中可行遍性問題的一種。本文首先介紹了歐拉回路的相關(guān)理論知識，以及求歐拉回路的算法。然后通過幾個(gè)實(shí)例，介紹了與歐拉回路相關(guān)的幾類典型問題。最后對歐拉回路的模型進(jìn)行了總結(jié)，指出其特點(diǎn)和具備的優(yōu)勢?！娟P(guān)鍵詞】歐拉回路歐拉路徑【正文】一引言歐拉回路問題是圖論中最古老的問題之一。它誕生于十八世紀(jì)的歐洲古城哥尼斯堡。普瑞格爾河流經(jīng)這座城市，人們在兩岸以及河中間的兩個(gè)小島之間建了七座橋（如圖1）。圖1市民們喜歡在這里散步，于是產(chǎn)生了這樣一個(gè)問題：是否可以找到一種方案，使得人們從自己家里出發(fā)，不重復(fù)地走遍每一座橋，然后回到家中？這個(gè)問題如果用數(shù)學(xué)

2、語言來描述，就是在圖2中找出一條回路，使得它不重復(fù)地經(jīng)過每一條邊。這便是著名的“哥尼斯堡七橋問題”。圖2無數(shù)熱衷于此的人試圖解決這個(gè)問題，但均以失敗告終。問題傳到了歐拉（Leonhard Euler, 1707-1783）那里，立即引起了這位大數(shù)學(xué)家的重視。經(jīng)過悉心研究，歐拉終于在1736年發(fā)表了論文哥尼斯堡的七座橋，不但成功地證明了“七橋問題”無解，而且找到了對于一般圖是否存在這類回路的充要條件。后人為了紀(jì)念歐拉這位偉大的數(shù)學(xué)家，便將這類回路稱為歐拉回路。歐拉回路問題在信息學(xué)競賽中有著廣泛的應(yīng)用，近年來在各類比賽中出現(xiàn)了許多與之相關(guān)的試題。本文將介紹歐拉回路的相關(guān)理論知識，并通過幾道例題分析

3、歐拉回路的實(shí)際應(yīng)用。二相關(guān)知識首先介紹相關(guān)概念和定理。設(shè)是一個(gè)圖。歐拉回路圖中經(jīng)過每條邊一次并且僅一次的回路稱作歐拉回路。歐拉路徑圖中經(jīng)過每條邊一次并且僅一次的路徑稱作歐拉路徑。歐拉圖存在歐拉回路的圖稱為歐拉圖。半歐拉圖存在歐拉路徑但不存在歐拉回路的圖稱為半歐拉圖。在以下討論中，假設(shè)圖不存在孤立點(diǎn) 度為0的頂點(diǎn)稱為孤立點(diǎn)。；否則，先將所有孤立點(diǎn)從圖中刪除。顯然，這樣做并不會(huì)影響圖中歐拉回路的存在性。我們經(jīng)常需要判定一個(gè)圖是否為歐拉圖（或半歐拉圖），并且找出一條歐拉回路（或歐拉路徑）。對于無向圖有如下結(jié)論：定理1無向圖為歐拉圖，當(dāng)且僅當(dāng)為連通圖且所有頂點(diǎn)的度為偶數(shù)。證明必要性。設(shè)圖的一條歐拉回路

4、為。由于經(jīng)過圖的每一條邊，而圖沒有孤立點(diǎn)，所以也經(jīng)過圖的每一個(gè)頂點(diǎn)，為連通圖成立。而對于圖的任意一個(gè)頂點(diǎn)，經(jīng)過時(shí)都是從一條邊進(jìn)入，從另一條邊離開，因此經(jīng)過的關(guān)聯(lián)邊的次數(shù)為偶數(shù)。又由于不重復(fù)地經(jīng)過了圖的每一條邊，因此的度為偶數(shù)。充分性。假設(shè)圖中不存在回路，而是連通圖，故一定是樹，那么有。由于圖所有頂點(diǎn)的度為偶數(shù)而且不含孤立點(diǎn)，那么圖的每一個(gè)頂點(diǎn)的度至少為2。由握手定理，有，與假設(shè)相矛盾。故圖中一定存在回路。設(shè)圖中邊數(shù)最多的一條簡單回路 邊沒有重復(fù)出現(xiàn)的回路稱為簡單回路。為下面證明回路是圖的歐拉回路。假設(shè)不是歐拉回路，則中至少含有一個(gè)點(diǎn)，該點(diǎn)的度大于經(jīng)過該點(diǎn)的關(guān)聯(lián)邊的次數(shù)。令，從出發(fā)有一條不屬于的

5、邊。若，則頂點(diǎn)自身構(gòu)成一個(gè)環(huán)，可以將其加入中形成一個(gè)更大的回路；否則，若，由于的度為偶數(shù)，而中經(jīng)過的關(guān)聯(lián)邊的次數(shù)也是偶數(shù)，所以必然存在一條不屬于的邊。依此類推，存在不屬于的邊。故是一條新的回路，將其加入中可以形成一個(gè)更大的回路，這與是圖的最大回路的假設(shè)相矛盾。故是圖的歐拉回路。由定理1可以立即得到一個(gè)用于判定半歐拉圖的推論：推論1無向圖為半歐拉圖，當(dāng)且僅當(dāng)為連通圖且除了兩個(gè)頂點(diǎn)的度為奇數(shù)之外，其它所有頂點(diǎn)的度為偶數(shù)。證明必要性。設(shè)圖的一條歐拉路徑為由于經(jīng)過圖的每一條邊，而圖沒有孤立點(diǎn)，所以也經(jīng)過圖的每一個(gè)頂點(diǎn)，為連通圖成立。對于頂點(diǎn)，進(jìn)入的次數(shù)比離開的次數(shù)少1；對于頂點(diǎn)，進(jìn)入的次數(shù)比離開的次數(shù)

6、多1：故和的度為奇數(shù)。而對于其它任意一個(gè)頂點(diǎn)，進(jìn)入的次數(shù)等于離開的次數(shù)，故的度為偶數(shù)。充分性。設(shè)是圖中唯一的兩個(gè)度為奇數(shù)的頂點(diǎn)。給圖加上一條虛擬邊得到圖，則圖的每一個(gè)頂點(diǎn)度均為偶數(shù)，故圖中存在歐拉回路。從中刪去得到一條從到的路徑，即為圖的歐拉路徑。對于有向圖，可以得到類似的結(jié)論：定理2有向圖為歐拉圖，當(dāng)且僅當(dāng)?shù)幕鶊D 忽略有向圖所有邊的方向，得到的無向圖稱為該有向圖的基圖。連通，且所有頂點(diǎn)的入度等于出度。推論2有向圖為半歐拉圖，當(dāng)且僅當(dāng)?shù)幕鶊D連通，且存在頂點(diǎn)的入度比出度大1、的入度比出度小1，其它所有頂點(diǎn)的入度等于出度。這兩個(gè)結(jié)論的證明與定理1和推論1的證明方法類似，這里不再贅述。注意到定理1的

7、證明是構(gòu)造性的，可以利用它來尋找歐拉回路。下面以無向圖為例，介紹求歐拉回路的算法。首先給出以下兩個(gè)性質(zhì)：性質(zhì)1設(shè)是歐拉圖中的一個(gè)簡單回路，將中的邊從圖中刪去得到一個(gè)新的圖，則的每一個(gè)極大連通子圖都有一條歐拉回路。證明若為無向圖，則圖的各頂點(diǎn)的度為偶數(shù)；若為有向圖，則圖的各頂點(diǎn)的入度等于出度。性質(zhì)2設(shè)、是圖的兩個(gè)沒有公共邊，但有至少一個(gè)公共頂點(diǎn)的簡單回路，我們可以將它們合并成一個(gè)新的簡單回路。證明只需按如圖3所示的方式合并。圖3由此可以得到以下求歐拉圖的歐拉回路的算法：1 在圖中任意找一個(gè)回路；2 將圖中屬于回路的邊刪除；3 在殘留圖的各極大連通子圖中分別尋找歐拉回路；4 將各極大連通子圖的歐拉

8、回路合并到中得到圖的歐拉回路。該算法的偽代碼如下：Procedure Euler-circuit ();Begin For 頂點(diǎn)的每個(gè)鄰接點(diǎn) Do If 邊未被標(biāo)記 Then Begin將邊作上標(biāo)記;將邊作上標(biāo)記; /1Euler-circuit ();將邊加入棧; End;End;最后依次取出棧每一條邊而得到圖的歐拉回路。由于該算法執(zhí)行過程中每條邊最多訪問兩次，因此該算法的時(shí)間復(fù)雜度為。在實(shí)際應(yīng)用中，以上的實(shí)現(xiàn)可能導(dǎo)致堆棧溢出（遞歸的深度最多可以達(dá)到層），因此常常需要將其改造成非遞歸的形式。完整的Pascal代碼見附錄1（遞歸形式）和附錄2（非遞歸形式）。如果圖是有向圖，我們?nèi)匀豢梢允褂靡陨?/p>

9、算法，只需將標(biāo)記有/1的行刪去即可。以上介紹了歐拉回路的相關(guān)知識和算法。然而實(shí)際問題中，更靈活、更具挑戰(zhàn)性的部分則是模型的建立。下面通過剖析若干實(shí)例，探究建立歐拉回路模型的方法，使讀者對歐拉回路算法有更深入的認(rèn)識。三例題例題一單詞游戲 題目來源：ACM/ICPC Central Europe Regional Contest 1999/2000，有改動(dòng)題目描述有個(gè)盤子，每個(gè)盤子上寫著一個(gè)僅由小寫字母組成的英文單詞。你需要給這些盤子安排一個(gè)合適的順序，使得相鄰兩個(gè)盤子中，前一個(gè)盤子上面單詞的末字母等于后一個(gè)盤子上面單詞的首字母。請你編寫一個(gè)程序，判斷是否能達(dá)到這一要求。如果能，請給出一個(gè)合適的順

10、序。數(shù)據(jù)規(guī)模分析通過對題目條件的一些初步分析，我們很容易得到下面的模型。模型1：以個(gè)盤子作為頂點(diǎn)；如果盤子的末字母等于盤子的首字母，那么從向連一條有向邊。對于樣例我們可以按圖4所示的方式構(gòu)圖。這樣，問題轉(zhuǎn)化為在圖中尋找一條不重復(fù)地經(jīng)過每一個(gè)頂點(diǎn)的路徑，即哈密爾頓路。然而，求哈密爾頓路是一個(gè)十分困難的問題，這樣的模型沒有給我們的解題帶來任何便利。因此，我們必須另辟蹊徑。圖4模型2：經(jīng)過分析，我們發(fā)現(xiàn)模型1的失敗之處在于，圖中需要遍歷的信息也就是每一個(gè)盤子表示在頂點(diǎn)上，而頂點(diǎn)的遍歷問題不易解決。能否將遍歷信息表示在邊上呢？考慮如下的構(gòu)圖方法：以26個(gè)字母作為頂點(diǎn)；對于每一個(gè)盤子，如果它的首字母為c

11、1，末字母為c2，那么從c1向c2連一條有向邊。對于樣例我們可以按圖5所示的方式構(gòu)圖，圖中未表示出的頂點(diǎn)均為孤立點(diǎn)，可以事先將其刪去。這樣，問題轉(zhuǎn)化為在圖中尋找一條不重復(fù)地經(jīng)過每一條邊的路徑，即歐拉路徑。這個(gè)問題能夠在時(shí)間內(nèi)解決。圖5小結(jié)比較以上兩個(gè)模型，模型1非常直觀，模型2的建立則需要一點(diǎn)逆向思維：我們已經(jīng)習(xí)慣于“頂點(diǎn)表示元素，邊表示元素之間的關(guān)系”這種先入為主的思想，而模型2則是反其道而行之將元素表示在邊上，而頂點(diǎn)則起到連接各個(gè)元素的作用。這說明，我們考慮問題時(shí)，必須將算法進(jìn)行反復(fù)地推敲、改進(jìn)，甚至打破舊的思維模式，大膽創(chuàng)新，才能找到解決問題的最佳方法。例題二倉庫管理 題目來源：Cent

12、ral-European Olympiad in Informatics 2005 Day 1 Depot Rearrangement題目描述一個(gè)公司有家商店，每家商店銷售相同的種商品。公司有一個(gè)很大的倉庫，商品在運(yùn)往商店之前首先在這里進(jìn)行整理、裝箱。公司將一定數(shù)量的某種商品放到一個(gè)箱子中，并貼上商品標(biāo)簽，用來標(biāo)識。這樣，一共有個(gè)箱子，每家商店都將得到標(biāo)簽為的箱子各一個(gè)。倉庫是在一個(gè)狹窄的建筑里，所以箱子只好排成一列。為了加快分發(fā)，管理員決定對箱子重新排列。一個(gè)好的排列順序應(yīng)該滿足以下條件：前個(gè)箱子具有不同的標(biāo)識，以便運(yùn)往1號商店；接下來個(gè)箱子具有不同的標(biāo)識，以便運(yùn)往2號商店依此類推。另外，初

13、始狀態(tài)時(shí)只有箱子隊(duì)列的末尾才有唯一的一個(gè)空位，每一次移動(dòng)都只能將一個(gè)箱子移動(dòng)到當(dāng)前的空位，并且要求所有移動(dòng)結(jié)束后，空位必須回到隊(duì)尾。請你編寫程序，計(jì)算重新排列所需的最少移動(dòng)次數(shù)和相應(yīng)的移動(dòng)方式。數(shù)據(jù)規(guī)模分析構(gòu)造二分圖，其頂點(diǎn)集，其中代表家商店，代表種商品。設(shè)倉庫中商店的箱子（即從第個(gè)到第個(gè)箱子）中商品的數(shù)量為，我們需要通過重新排列箱子使得所有。對任意，若，那么從向連條有向邊，表示商店多了個(gè)商品；若，那么從向連條有向邊，表示商店少了個(gè)商品。例如，樣例，的情況，各個(gè)箱子的排列情況如下表：413165232356214564132455123466按上述方法構(gòu)造圖如下：圖6通過分析整個(gè)重排過程中空位

14、的位置，不難發(fā)現(xiàn)：初始和結(jié)束狀態(tài)中，空位處于隊(duì)尾的位置；另外還可能有若干個(gè)中間狀態(tài)，空位也處于隊(duì)尾的位置。我們將空位處于隊(duì)尾時(shí)的相鄰兩個(gè)狀態(tài)之間的若干次移動(dòng)稱為一個(gè)階段。如此定義階段有什么好處呢？其實(shí)，一個(gè)階段的移動(dòng)與圖中的簡單回路一一對應(yīng)。例如，上圖中回路對應(yīng)的操作序列為：30à31；41316523235621456413245512346624à30；41316523235621456413245123465631à24。413165232356214564132456123465（圖中藍(lán)色格子為移動(dòng)的起始位置，綠色格子為移動(dòng)的終止位置。）現(xiàn)在問題轉(zhuǎn)化為：如

15、何在圖中找出若干個(gè)沒有公共邊的回路，使得它們覆蓋圖中所有的邊。注意到一個(gè)長度為的回路對應(yīng)的移動(dòng)次數(shù)為，如果用個(gè)回路覆蓋圖，則總移動(dòng)次數(shù)。由于題目要求盡量小，所以要盡量小。而圖中，的入度與出度相等，的入度與出度相等，因此的每一個(gè)極大強(qiáng)連通子圖都有歐拉回路。顯然，用各極大強(qiáng)連通子圖的歐拉回路來覆蓋圖能夠使得回路數(shù)最少。完整的算法流程如下：1 建立二分圖；2 求出的所有極大強(qiáng)連通子圖；3 對于的每一個(gè)極大強(qiáng)連通子圖，求出一條歐拉回路；4 根據(jù)各極大強(qiáng)連通子圖的歐拉回路構(gòu)造出對應(yīng)的移動(dòng)方案。小結(jié)一些看似與歐拉回路，甚至與圖沒有太大關(guān)系的問題，經(jīng)過巧妙的轉(zhuǎn)化，就能構(gòu)圖并且轉(zhuǎn)化成在圖中求歐拉回路，從而高效

16、地解決問題。這也說明歐拉回路應(yīng)用的靈活性。例題三中國郵路問題（版本1） 題目來源：經(jīng)典問題題目描述A城市的交通系統(tǒng)由若干個(gè)路口和街道組成，每條街道都連接著兩個(gè)路口。所有街道都是雙向通行的，且每條街道都有一個(gè)長度值。一名郵遞員傳送報(bào)紙和信件，要從郵局出發(fā)經(jīng)過他所管轄的每一條街道最后返回郵局（每條街道可以經(jīng)過不止一次）。請問他應(yīng)該如何安排自己的路線，使得走過的總長度最短呢？分析這道題目看起來比較復(fù)雜，不好下手。先來分析簡單一點(diǎn)的情況。將路口看成頂點(diǎn)，街道看成無向邊，得到一個(gè)無向圖。如果不是連通圖，那么一定無解；否則，如果是歐拉圖，顯然的任意一條歐拉回路都是最優(yōu)線路。如果中奇點(diǎn) 度為奇數(shù)的頂點(diǎn)稱為奇

17、點(diǎn)。個(gè)數(shù)為2（設(shè)這兩個(gè)頂點(diǎn)為，），那么中一定存在一條從到的歐拉路徑。然后，找一條從到的最短路徑，將其連接到之后得到一條完整的回路?？梢宰C明，這樣的路線一定是最優(yōu)的。如果中奇點(diǎn)個(gè)數(shù)大于2，怎樣確定最優(yōu)路線呢？注意到前面關(guān)于奇點(diǎn)個(gè)數(shù)為2的情況討論中，我們實(shí)際是將從到的最短路徑所經(jīng)過的邊加入到了中，即得到的新圖，而歐拉圖的一條歐拉回路即是最優(yōu)路線。經(jīng)過分析，我們發(fā)現(xiàn)加入任意一條路徑的結(jié)果是路徑的兩個(gè)端點(diǎn)的度增加了1，奇偶性改變；而路徑中其它結(jié)點(diǎn)的度增加了2，奇偶性不變。因此，增加的每一條路徑的兩個(gè)端點(diǎn)都應(yīng)該是奇點(diǎn)，這樣每次增加一條路徑就能減少2個(gè)奇點(diǎn)。我們知道，任意圖中奇點(diǎn)個(gè)數(shù)為偶數(shù) 由握手定理，對

18、任意圖有，故奇點(diǎn)個(gè)數(shù)必為偶數(shù)。設(shè)圖中奇點(diǎn)個(gè)數(shù)為，那么一定能通過增加條路徑使得所有頂點(diǎn)的度為偶數(shù)。更進(jìn)一步地，考慮如何使得增加的條路徑的總長度最短。顯然，增加的每一條路徑都必須是兩點(diǎn)間的最短路徑；另外，需要給個(gè)奇點(diǎn)找到一種合理的配對方式，使得總長度最小。以圖的個(gè)奇點(diǎn)作為頂點(diǎn)集構(gòu)造無向完全圖，邊的權(quán)值為兩點(diǎn)間的最短路徑長度，則的最小權(quán)完備匹配對應(yīng)最優(yōu)的方案。無向完全的最小權(quán)匹配可以用Edmonds提出的算法 詳見參考文獻(xiàn)4。在多項(xiàng)式時(shí)間內(nèi)解決。最后按照匹配的方案在圖中增邊得到圖，并在圖中求歐拉回路即可。完整的算法流程如下：1 如果是連通圖，轉(zhuǎn)2，否則返回?zé)o解并結(jié)束；2 檢查中的奇點(diǎn)，構(gòu)成圖的頂點(diǎn)集

19、；3 求出中每對奇點(diǎn)之間的最短路徑長度，作為圖對應(yīng)頂點(diǎn)間的邊權(quán)；4 對進(jìn)行最小權(quán)匹配；5 把最小權(quán)匹配里的每一條匹配邊代表的路徑，加入到圖中得到圖；6 在中求歐拉回路，即所求的最優(yōu)路線。例題四中國郵路問題（版本2） 題目來源：經(jīng)典問題題目描述A城市的交通系統(tǒng)由若干個(gè)路口和街道組成，每條街道都連接著兩個(gè)路口。所有街道都只能單向通行，且每條街道都有一個(gè)長度值。一名郵遞員傳送報(bào)紙和信件，要從郵局出發(fā)經(jīng)過他所管轄的每一條街道最后返回郵局（每條街道可以經(jīng)過不止一次）。請問他應(yīng)該如何安排自己的路線，使得走過的總長度最短呢？分析本題條件與例題三的唯一區(qū)別是：所有街道只能單向通行。顯然，如果的基圖不連通，那么

20、一定無解。另外，如果存在某個(gè)頂點(diǎn)，它的入度或者出度為0，那么不可能存在經(jīng)過該點(diǎn)的回路。因此，這種情況也是無解的。仿照例題三的思路，考慮能否通過在圖中增加若干條路徑得到歐拉圖，然后在中求歐拉回路。首先計(jì)算每個(gè)頂點(diǎn)的入度與出度之差。如果中所有的，那么中已經(jīng)存在歐拉回路。否則，由于，的值一定是有正有負(fù)。對于的頂點(diǎn)，需要增加條從出發(fā)的路徑；對于的頂點(diǎn)，需要增加條到結(jié)束的路徑；對于的頂點(diǎn)，要求不作為增加的任何一條路徑的端點(diǎn)（或者是，以為終止點(diǎn)的路徑數(shù)等于以為出發(fā)點(diǎn)的路徑數(shù)，但在那種情況下，可以把后者連接到前者之后而合并成一條路徑）。這個(gè)模型與網(wǎng)絡(luò)流模型有著驚人的相似！的頂點(diǎn)對應(yīng)于網(wǎng)絡(luò)流模型中的源點(diǎn)，它發(fā)

21、出個(gè)單位的流；的頂點(diǎn)對應(yīng)于網(wǎng)絡(luò)流模型中的匯點(diǎn)，它接收個(gè)單位的流；而的頂點(diǎn)則對應(yīng)于網(wǎng)絡(luò)流模型中的中間結(jié)點(diǎn)，它接收的流量等于發(fā)出的流量。在原問題中還要求增加的路徑總長度最小，我們可以給網(wǎng)絡(luò)中每條邊的費(fèi)用值設(shè)為圖中對應(yīng)邊的長度。這樣，在網(wǎng)絡(luò)中求最小費(fèi)用最大流，即可使總費(fèi)用最小。具體來說，可以這樣構(gòu)造網(wǎng)絡(luò)：1 其頂點(diǎn)集為圖的所有頂點(diǎn)，以及附加的超級源和超級匯；2 對于圖中每一條邊，在中連邊，容量為，費(fèi)用為該邊的長度；3 從源點(diǎn)向所有的頂點(diǎn)連邊，容量為，費(fèi)用為0；4 從所有的頂點(diǎn)向匯點(diǎn)連邊，容量為，費(fèi)用為0。完整的算法流程如下：1 如果的基圖連通且所有頂點(diǎn)的入、出度均不為0，轉(zhuǎn)2，否則返回?zé)o解并結(jié)束；2

22、 計(jì)算所有頂點(diǎn)的值；3 構(gòu)造網(wǎng)絡(luò)；4 在網(wǎng)絡(luò)中求最小費(fèi)用最大流；5 對中每一條流量的邊，在圖中增加次得到；6 在中求歐拉回路，即為所求的最優(yōu)路線。拓展如果將條件改成：部分街道能夠雙向通行，部分街道只能單向通行，該如何解決？ 本問題已被證明是一個(gè)NPC問題。詳見參考文獻(xiàn)5。小結(jié)例題三、例題四以及拓展的問題，雖然條件上只有幾字之差，但解法卻迥然不同。這說明我們在做題時(shí)必須仔細(xì)審題，緊緊圍繞題中的關(guān)鍵條件進(jìn)行思考。否則，可能會(huì)使思維誤入歧途。另外，我們平時(shí)要注意發(fā)散思維、舉一反三：如果將題目改動(dòng)一個(gè)條件該如何解決？這樣，通過思考和解決一系列具有諸多相似點(diǎn)的問題，我們的思維能力和思維深度得到了鍛煉。例

23、題五賭博機(jī) 題目來源：Polish Olympiad in Informatics 1996 Stage II Problem 3 Gambling，有改動(dòng)題目描述一臺賭博機(jī)由個(gè)整數(shù)發(fā)生器組成。能夠產(chǎn)生的整數(shù)集合為，并且是集合的一個(gè)子集。可以為空集。在賭博機(jī)運(yùn)轉(zhuǎn)的任意時(shí)刻，個(gè)發(fā)生器中有且僅有一個(gè)發(fā)生器處于活動(dòng)狀態(tài)。游戲開始時(shí)只有是活動(dòng)的。設(shè)當(dāng)前的活動(dòng)發(fā)生器為，若，游戲者可以在中選擇一個(gè)數(shù)，然后機(jī)器將從中刪除，并將活動(dòng)狀態(tài)轉(zhuǎn)移到；否則，那么游戲結(jié)束。如果最后一個(gè)活動(dòng)發(fā)生器為，并且游戲結(jié)束時(shí)所有，那么游戲者失敗，否則獲勝。現(xiàn)在你正站在一臺賭博機(jī)面前。在開始游戲之前，你決定先編寫一個(gè)程序，判斷你能否

24、獲勝。如果能，程序?qū)⒏嬖V你每次如何選擇合適的數(shù)才能獲勝。數(shù)據(jù)規(guī)模，分析我們將問題抽象成圖結(jié)構(gòu)。構(gòu)造圖，其頂點(diǎn)集表示個(gè)發(fā)生器。如果可以產(chǎn)生，那么從向連一條有向邊。在本問題中，任意一次游戲過程在圖中都對應(yīng)一條從出發(fā)的簡單路徑。特別地，一次失敗的游戲過程對應(yīng)一條從出發(fā)的歐拉回路。如果游戲者無論如何都將失敗，那么對應(yīng)的圖滿足：從出發(fā)，不管怎么走，只要不刻意地重復(fù)走一條邊，一定能走出一條歐拉回路而不會(huì)在途中無法繼續(xù)。我們把這類圖稱為隨機(jī)歐拉圖。顯然，隨機(jī)歐拉圖屬于歐拉圖。根據(jù)歐拉圖的相關(guān)結(jié)論，對于基圖不連通，或者不滿足所有頂點(diǎn)的入度等于出度的情況，游戲者無論如何都不會(huì)失敗。以下的討論中，我們只考慮圖為歐

25、拉圖的情況。通過分析，我們不難發(fā)現(xiàn)這樣一個(gè)結(jié)論：對于任何一次游戲過程，最后一個(gè)活動(dòng)發(fā)生器一定是。否則，如果最后一個(gè)活動(dòng)發(fā)生器為，那么在對應(yīng)的路徑中，進(jìn)入的次數(shù)比離開的次數(shù)大1。而的入度等于出度，所以此時(shí)一定存在一條從出發(fā)的邊還沒有被訪問過，這不符合游戲結(jié)束的條件。也就是說，任何一次游戲過程在圖中對應(yīng)一個(gè)簡單回路。假設(shè)某次游戲過程在圖中對應(yīng)的回路為。將回路經(jīng)過的邊從圖中刪去，得到殘留圖（即），那么中所有頂點(diǎn)的入度與出度相等。這里分為兩種情況：若為零圖 不含任何邊的圖稱為零圖。，那么這是一次失敗的游戲過程；否則，的每一個(gè)極大強(qiáng)連通子圖都存在歐拉回路。注意到中一定是孤立點(diǎn)，否則游戲不會(huì)結(jié)束。因此，中

26、一定存在不經(jīng)過的回路?？傊?，游戲者能夠獲勝，當(dāng)且僅當(dāng)圖存在一個(gè)子圖，使得由不經(jīng)過的回路組成，并且獲勝的游戲過程對應(yīng)的補(bǔ)圖中的歐拉回路。最后還有一個(gè)問題：如何尋找圖中不經(jīng)過的回路？其實(shí)，只需將圖中的頂點(diǎn)刪除，然后在殘留圖中進(jìn)行深度優(yōu)先遍歷（DFS）即可。如果在DFS遍歷過程中，發(fā)現(xiàn)某個(gè)頂點(diǎn)存在一條回邊指向它的祖先結(jié)點(diǎn)，那么DFS樹中從到的路徑以及邊構(gòu)成一個(gè)回路。完整的算法流程如下：1、 建立有向圖；2、 判斷其中是否存在歐拉回路。如果存在，轉(zhuǎn)3，否則任意產(chǎn)生并返回一次游戲過程并結(jié)束；3、 檢查圖中是否存在不經(jīng)過的回路。如果存在，令，返回圖中的歐拉回路并結(jié)束，否則轉(zhuǎn)4；4、 返回游戲失敗?！究偨Y(jié)】

27、歐拉回路是指不重復(fù)地經(jīng)過圖中所有邊的回路。歐拉回路模型簡潔、靈活，容易實(shí)現(xiàn)且算法效率高，因而得到廣泛的應(yīng)用。在實(shí)際問題中，如果能將主要信息集中在邊上，并且轉(zhuǎn)化成遍歷圖中每一條邊，就能很好地運(yùn)用歐拉回路的相關(guān)性質(zhì)和算法高效地解決。因此，在解題過程中，模型的建立起到了至關(guān)重要的作用。而問題的模型往往不是顯而易見的，我們必須在仔細(xì)分析、研究題目的基礎(chǔ)上，挖掘問題的本質(zhì)，拓展思路，大膽創(chuàng)新，才能建立合適的模型從而高效地解決問題。【致謝】本論文的撰寫得到湖南師大附中李淑平老師的精心指導(dǎo)，在此表示衷心的感謝！同時(shí)感謝班上信息組同學(xué)和集訓(xùn)隊(duì)隊(duì)友的幫助與支持！【參考文獻(xiàn)】1 劉汝佳 黃亮算法藝術(shù)與信息學(xué)競賽2

28、 盧開澄 盧華明圖論及其應(yīng)用3 戴一奇 胡冠章 陳衛(wèi)圖論與代數(shù)結(jié)構(gòu)4 J. Edmonds, E. JohnsonMatching, Euler tours, and the Chinese postman5 C. PapadimitriouThe complexity of edge traversing6 Baltic Olympiad in Informatics 2001 官方解答【附錄】附錄1求無向圖的歐拉回路（遞歸實(shí)現(xiàn)）program euler; const maxn=10000;頂點(diǎn)數(shù)上限 maxm=100000;邊數(shù)上限 type tnode=tr; tr

29、=record f,t:longint;邊的起始點(diǎn)和終止點(diǎn) al:boolean;訪問標(biāo)記 rev,next:tnode;反向邊和鄰接表中的下一條邊 end; var n,m,bl:longint;頂點(diǎn)數(shù)，邊數(shù)，基圖的極大連通子圖個(gè)數(shù) tot:longint; g:array1.maxn of tnode; d:array1.maxn of longint;頂點(diǎn)的度fa,rank:array1.maxn of longint;并查集中元素父結(jié)點(diǎn)和啟發(fā)函數(shù)值 list:array1.maxm of tnode;最終找到的歐拉回路 o:boolean;原圖中是否存在歐拉回路 procedure b

30、uild(ta,tb:longint);在鄰接表中建立邊(ta, tb) var t1,t2:tnode; begin t1:=new(tnode); t2:=new(tnode); t1.f:=ta; t1.t:=tb; t1.al:=false; t1.rev:=t2; t1.next:=gta; gta:=t1; t2.f:=tb; t2.t:=ta; t2.al:=false; t2.rev:=t1; t2.next:=gtb; gtb:=t2; end; procedure merge(a,b:longint);在并查集中將a, b兩元素合并 var oa,ob:longint; b

31、egin oa:=a; while faa<>a do a:=faa; faoa:=a; ob:=b; while fab<>b do b:=fab; faob:=b; if a<>b then begin dec(bl);合并后，基圖的極大連通子圖個(gè)數(shù)減少1 if ranka=rankb then inc(ranka); if ranka>rankb then fab:=a else faa:=b; end; end; procedure init;初始化 var i,ta,tb:longint; begin fillchar(fa,sizeof(f

32、a),0); fillchar(rank,sizeof(rank),0); fillchar(d,sizeof(d),0); readln(n,m); for i:=1 to n do fai:=i; bl:=n; for i:=1 to m do begin readln(ta,tb); build(ta,tb); inc(dtb); inc(dta); merge(ta,tb); end; end; procedure search(i:longint);以i為出發(fā)點(diǎn)尋找歐拉回路 var te:tnode; begin te:=gi; while te<>nil do begi

33、n if not te.al then begin te.al:=true; te.rev.al:=true; search(te.t); listtot:=te; dec(tot); end; te:=te.next; end; end; procedure main;主過程 var i:longint; begin o:=false; for i:=1 to n do if di=0 then dec(bl);排除孤立點(diǎn)的影響 if bl<>1 then exit;原圖不連通，無解 for i:=1 to n do if odd(di) then exit;存在奇點(diǎn)，無解 o:

34、=true; for i:=1 to n do if di<>0 then break; tot:=m; search(i);從一個(gè)非孤立點(diǎn)開始尋找歐拉回路 end; procedure print;輸出結(jié)果 var i:longint; begin if not o then writeln('No solution.') else begin writeln(list1.f); for i:=1 to m do writeln(listi.t); end; end;begin init; main; print;end.附錄2求無向圖的歐拉回路（非遞歸實(shí)現(xiàn)）pr

35、ogram euler; const maxn=10000;頂點(diǎn)數(shù)上限 type tnode=tr; tr=record f,t:longint;邊的起始點(diǎn)和終止點(diǎn) rev,prev,next:tnode;反向邊和鄰接表中的上一條邊，下一條邊 end; var n,m,bl:longint;頂點(diǎn)數(shù)，邊數(shù)，基圖的極大連通子圖個(gè)數(shù) g:array1.maxn of tnode; d:array1.maxn of longint;頂點(diǎn)的度fa,rank:array1.maxn of longint;并查集中元素父結(jié)點(diǎn)和啟發(fā)函數(shù)值 o:boolean;原圖中是否存在歐拉回路 f,link:tnode;

36、用鏈表保存最終找到的歐拉回路 procedure build(ta,tb:longint);在鄰接表中建立邊(ta, tb) var t1,t2:tnode; begin t1:=new(tnode); t2:=new(tnode); t1.f:=ta; t1.t:=tb; t1.rev:=t2; t1.prev:=nil; t1.next:=gta; if gta<>nil then gta.prev:=t1; gta:=t1; t2.f:=tb; t2.t:=ta; t2.rev:=t1; t2.prev:=nil; t2.next:=gtb; if gtb<>ni

37、l then gtb.prev:=t2; gtb:=t2; end; procedure merge(a,b:longint);在并查集中將a, b兩元素合并 var oa,ob:longint; begin oa:=a; while faa<>a do a:=faa; faoa:=a; ob:=b; while fab<>b do b:=fab; faob:=b; if a<>b then begin dec(bl);合并后，基圖的極大連通子圖個(gè)數(shù)減少1 if ranka=rankb then inc(ranka); if ranka>rankb t

38、hen fab:=a else faa:=b; end; end; procedure init;初始化 var i,ta,tb:longint; begin fillchar(fa,sizeof(fa),0); fillchar(rank,sizeof(rank),0); fillchar(d,sizeof(d),0); readln(n,m); for i:=1 to n do fai:=i; bl:=n; for i:=1 to m do begin readln(ta,tb); build(ta,tb); inc(dtb); inc(dta); merge(ta,tb); end; e

39、nd; procedure delm(t:tnode);在鄰接表中刪除邊t var no:longint; begin no:=t.f; if t.prev<>nilthen t.prev.next:=t.nextelse gno:=t.next; if t.next<>nil then t.next.prev:=t.prev; end; procedure findcircle(no:longint;var head,tail:tnode);以no為起點(diǎn)找一條回路，保存在以head為頭，tail為尾的鏈表中 var i:longint; begin i:=no; he

40、ad:=gi; tail:=head; gi:=gi.next; if gi<>nil then gi.prev:=nil; tail.prev:=nil; tail.next:=nil; delm(tail.rev); i:=tail.t; while i<>no do begin tail.next:=gi; gi:=gi.next; if gi<>nil then gi.prev:=nil; tail:=tail.next; tail.prev:=nil; tail.next:=nil; delm(tail.rev); i:=tail.t; end;

41、end; procedure main;主過程 var i:longint; te,head,tail:tnode; begin o:=false; for i:=1 to n do if di=0 then dec(bl);排除孤立點(diǎn)的影響 if bl<>1 then exit;原圖不連通，無解 for i:=1 to n do if odd(di) then exit;存在奇點(diǎn)，無解 o:=true; for i:=1 to n do if di<>0 then break; findcircle(i,head,tail);首先任意找一條回路 link:=head;

42、 f:=link; while link<>nil do if glink.t<>nil then begin findcircle(link.t,head,tail); tail.next:=link.next; link.next:=head;將兩個(gè)回路合并 end else link:=link.next; end; procedure print;輸出結(jié)果 begin if not o then writeln('No solution.') else begin link:=f; writeln(link.f); while link<&

43、gt;nil do begin writeln(link.t); link:=link.next; end; end; end;begin init; main; print;end.附錄3例題一的英文原題Play on WordsSome of the secret doors contain a very interesting word puzzle. The team of archaeologists has to solve it to open that doors. Because there is no other way to open the doors, th

44、e puzzle is very important for us. There is a large number of magnetic plates on every door. Every plate has one word written on it. The plates must be arranged into a sequence in such a way that every word begins with the same letter as the previous word ends. For example, the word “acm” can b

45、e followed by the word “Motorola”. Your task is to write a computer program that will read the list of words and determine whether it is possible to arrange all of the plates in a sequence (according to the given rule) and consequently to open the door. Input SpecificationThe input consists of

46、T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing a single integer number N that indicates the number of plates (1 N 100000). Then exactly N lines follow, each containing a single word. Each word contains at leas

47、t two and at most 1000 lowercase characters, that means only letters 'a' through 'z' will appear in the word. The same word may appear several times in the list. Output SpecificationYour program has to determine whether it is possible to arrange all the plates in a sequence such

48、 that the first letter of each word is equal to the last letter of the previous word. All the plates from the list must be used, each exactly once. The words mentioned several times must be used that number of times. If there exists such an ordering of plates, your program should print the sent

49、ence "Ordering is possible.". Otherwise, output the sentence "The door cannot be opened.". Sample Input32acmibm3acmmalformmouse2okokOutput for the Sample InputThe door cannot be opened.Ordering is possible.The door cannot be opened.附錄4例題二的英文原題Depot RearrangementA company ope

50、rates N shops, selling M different products in each shop. The company has a large depot where the products are packed before delivering to shops. Each shop receives the same number of items of each product. Hence the company packs a certain number of items of a given product into a container, and la

51、bels that container with the product identifier. Products are identified by the numbers from 1 to M. Thus, at the end of packing, there are N*M containers in the depot, and exactly N containers are labeled with a given product label for each product. Because the depot is in a narrow building, the co

52、ntainers are arranged in a single row. In order to speed-up distribution, the manager of the depot wants to rearrange the containers. Since the product delivery to the shops occurs by sending exactly one truck to each shop, and each truck carries one container of each product, a suitable arrangement is the following. The first M containers in the row must be labeled with differe