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

歐拉回路性質(zhì)與應(yīng)用探究【摘要】歐拉回路，又稱“一筆畫”，是圖論中可行遍性問題的一種。本文首先介紹了歐拉回路的相關(guān)理論知識，以及求歐拉回路的算法。然后通過幾個實(shí)例，介紹了與歐拉回路相關(guān)的幾類典型問題。最后對歐拉回路的模型進(jìn)行了總結(jié)，指出其特點(diǎn)和具備的優(yōu)勢?！娟P(guān)鍵詞】歐拉回路歐拉路徑【正文】一引言歐拉回路問題是圖論中最古老的問題之一。它誕生于十八世紀(jì)的歐洲古城哥尼斯堡。普瑞格爾河流經(jīng)這座城市，人們在兩岸以及河中間的兩個小島之間建了七座橋(如圖1)。圖1市民們喜歡在這里散步，于是產(chǎn)生了這樣一個問題：是否可以找到一種方案，使得人們從自己家里出發(fā)，不重復(fù)地走遍每一座橋，然后回到家中？這個問題如果用數(shù)學(xué)語言來描述，就是在圖2中找出一條回路，使得它不重復(fù)地經(jīng)過每一條邊。這便是著名的“哥尼斯堡七橋問題”。圖2無數(shù)熱衷于此的人試圖解決這個問題，但均以失敗告終。問題傳到了歐拉(LeonhardEuler,1707-1783)那里，立即引起了這位大數(shù)學(xué)家的重視。經(jīng)過悉心研究，歐拉終于在1736年發(fā)表了論文《哥尼斯堡的七座橋》，不但成功地證明了“七橋問題”無解，而且找到了對于一般圖是否存在這類回路的充要條件。后人為了紀(jì)念歐拉這位偉大的數(shù)學(xué)家，便將這類回路稱為歐拉回路。歐拉回路問題在信息學(xué)競賽中有著廣泛的應(yīng)用，近年來在各類比賽中出現(xiàn)了許多與之相關(guān)的試題。本文將介紹歐拉回路的相關(guān)理論知識，并通過幾道例題分析歐拉回路的實(shí)際應(yīng)用。二相關(guān)知識首先介紹相關(guān)概念和定理。設(shè)G=(V,E)是一個圖。歐拉回路圖G中經(jīng)過每條邊一次并且僅一次的回路稱作歐拉回路。歐拉路徑圖G中經(jīng)過每條邊一次并且僅一次的路徑稱作歐拉路徑。歐拉圖存在歐拉回路的圖稱為歐拉圖。半歐拉圖存在歐拉路徑但不存在歐拉回路的圖稱為半歐拉圖。在以下討論中，假設(shè)圖G不存在孤立點(diǎn)1；否則，先將所有孤立點(diǎn)從圖中刪除。顯然，這樣做并不會影響圖G中歐拉回路的存在性。我們經(jīng)常需要判定一個圖是否為歐拉圖(或半歐拉圖)，并且找出一條歐拉回路(或歐拉路徑)。對于無向圖有如下結(jié)論：定理1無向圖G為歐拉圖，當(dāng)且僅當(dāng)G為連通圖且所有頂點(diǎn)的度為偶數(shù)。證明必要性。設(shè)圖G的一條歐拉回路為C。由于C經(jīng)過圖G的每一條邊，而圖G沒有孤立點(diǎn)，所以C也經(jīng)過圖G的每一個頂點(diǎn)，G為連通圖成立。而對于圖G的任意一個頂點(diǎn)v，C經(jīng)過v時都是從一條邊進(jìn)入，從另一條邊離開，因^C經(jīng)過v的關(guān)聯(lián)邊的次數(shù)為偶數(shù)。又由于C不重復(fù)地經(jīng)過了圖G的每一條邊，因此v的度為偶數(shù)。充分性。假設(shè)圖G中不存在回路，而G是連通圖，故G一定是樹，那么有|E=|V|-1。由于圖G所有頂點(diǎn)的度為偶數(shù)而且不含孤立點(diǎn)，那么圖G的每一個頂點(diǎn)的度至少為2。由握手定理，有EI=2￡d(v)>|V|，與假設(shè)相矛盾。故圖G中一定存在回路。設(shè)圖G中邊veV數(shù)最多的一條簡單回路2為C={e=(v,v),e=(v,v),,e=(v,v)}1 012 12 m m-10下面證明回路C是圖G的歐拉回路。1度為0的頂點(diǎn)稱為孤立點(diǎn)。2邊沒有重復(fù)出現(xiàn)的回路稱為簡單回路。假設(shè)C不是歐拉回路，則C中至少含有一個點(diǎn)七，該點(diǎn)的度大于C經(jīng)過該點(diǎn)的關(guān)聯(lián)邊的次數(shù)。令v'=v，從v'出發(fā)有一條不屬于C的邊e=(v',v')。若v'=v'，則頂點(diǎn)v'自0k 0 10 1 10 0身構(gòu)成一個環(huán)，可以將其加入C中形成一個更大的回路；否則，若vJv'，由于v'的度為1 0 1偶數(shù)，而C中經(jīng)過v'的關(guān)聯(lián)邊的次數(shù)也是偶數(shù)，所以必然存在一條不屬于C的邊1e=(vf,v')。依此類推，存在不屬于c的邊e=(vr,v'),...,e=(v‘，v')。故2 12 3 23 k k-10C={e,e'，…,e'}是一條新的回路，將其加入C中可以形成一個更大的回路，這與C是12k圖G的最大回路的假設(shè)相矛盾。故C是圖G的歐拉回路。由定理1可以立即得到一個用于判定半歐拉圖的推論：推論1無向圖G為半歐拉圖，當(dāng)且僅當(dāng)G為連通圖且除了兩個頂點(diǎn)的度為奇數(shù)之外，其它所有頂點(diǎn)的度為偶數(shù)。證明必要性。設(shè)圖G的一條歐拉路徑為P={e=(v,v),e=(v,v),...,e=(v,v)}1 012 12 m m-1m由于P經(jīng)過圖G的每一條邊，而圖G沒有孤立點(diǎn)，所以P也經(jīng)過圖G的每一個頂點(diǎn)，G為連通圖成立。對于頂點(diǎn)v0，P進(jìn)入v0的次數(shù)比離開v0的次數(shù)少1；對于頂點(diǎn)vm,P進(jìn)入vm的次數(shù)比離開v,"T次數(shù)多1：故v”pvm的度為奇數(shù)。而對于其它任意一個頂點(diǎn)v(v豐v,v豐v)，P進(jìn)入v的次數(shù)等于離開v的次數(shù)，故v的度為偶數(shù)。kk0km k k k充分性。設(shè)v1,v2是圖G中唯一的兩個度為奇數(shù)的頂點(diǎn)。給圖G加上一條虛擬邊e0=(v1,v2)得到圖G，則圖G的每一個頂點(diǎn)度均為偶數(shù)，故圖G中存在歐拉回路C。從C中刪去e0得到一條從v1到v2的路徑P，P即為圖G的歐拉路徑。對于有向圖，可以得到類似的結(jié)論：定理2有向圖G為歐拉圖，當(dāng)且僅當(dāng)G的基圖3連通，且所有頂點(diǎn)的入度等于出度。推論2有向圖G為半歐拉圖，當(dāng)且僅當(dāng)G的基圖連通，且存在頂點(diǎn)u的入度比出度大1、v的入度比出度小1，其它所有頂點(diǎn)的入度等于出度。這兩個結(jié)論的證明與定理1和推論1的證明方法類似，這里不再贅述。3忽略有向圖所有邊的方向，得到的無向圖稱為該有向圖的基圖。注意到定理1的證明是構(gòu)造性的，可以利用它來尋找歐拉回路。下面以無向圖為例，介紹求歐拉回路的算法。首先給出以下兩個性質(zhì)：性質(zhì)1設(shè)C是歐拉圖G中的一個簡單回路，將C中的邊從圖G中刪去得到一個新的圖G，則G的每一個極大連通子圖都有一條歐拉回路。證明若G為無向圖，則圖G的各頂點(diǎn)的度為偶數(shù)；若G為有向圖，則圖G的各頂點(diǎn)的入度等于出度。性質(zhì)2設(shè)C1、C2是圖G的兩個沒有公共邊，但有至少一個公共頂點(diǎn)的簡單回路，我們可以將它們合并成一個新的簡單回路C'。證明只需按如圖3所示的方式合并。圖3由此可以得到以下求歐拉圖G的歐拉回路的算法：1在圖G中任意找一個回路C；2將圖G中屬于回路C的邊刪除；3在殘留圖的各極大連通子圖中分別尋找歐拉回路；4將各極大連通子圖的歐拉回路合并到C中得到圖G的歐拉回路。該算法的偽代碼如下：ProcedureEuler-circuit(start)；BeginFor頂點(diǎn)start的每個鄰接點(diǎn)vDoIf邊(start,v)未被標(biāo)記ThenBegin將邊(start,v)作上標(biāo)記；將邊(v,start)作上標(biāo)記； //1Euler-circuit(v)；將邊（start,v）加入棧S；End;End;最后依次取出棧s每一條邊而得到圖G的歐拉回路。由于該算法執(zhí)行過程中每條邊最多訪問兩次，因此該算法的時間復(fù)雜度為。（|eD。在實(shí)際應(yīng)用中，以上的實(shí)現(xiàn)可能導(dǎo)致堆棧溢出（遞歸的深度最多可以達(dá)到|目層），因此常常需要將其改造成非遞歸的形式。完整的Pascal代碼見附錄1（遞歸形式）和附錄2（非遞歸形式）。如果圖G是有向圖，我們?nèi)匀豢梢允褂靡陨纤惴ǎ恍鑼?biāo)記有7/1的行刪去即可。以上介紹了歐拉回路的相關(guān)知識和算法。然而實(shí)際問題中，更靈活、更具挑戰(zhàn)性的部分則是模型的建立。下面通過剖析若干實(shí)例，探究建立歐拉回路模型的方法，使讀者對歐拉回路算法有更深入的認(rèn)識。三例題例題一單詞游戲4題目描述有N個盤子，每個盤子上寫著一個僅由小寫字母組成的英文單詞。你需要給這些盤子安排一個合適的順序，使得相鄰兩個盤子中，前一個盤子上面單詞的末字母等于后一個盤子上面單詞的首字母。請你編寫一個程序，判斷是否能達(dá)到這一要求。如果能，請給出一個合適的順序。數(shù)據(jù)規(guī)模1<N<100000分析通過對題目條件的一些初步分析，我們很容易得到下面的模型。模型1：以N個盤子作為頂點(diǎn)；如果盤子A的末字母等于盤子B的首字母，那么從A向B連一條有向邊。對于樣例我們可以按圖4所示的方式構(gòu)圖。這樣，問題轉(zhuǎn)化為在圖中尋找一條不重復(fù)地經(jīng)過每一個頂點(diǎn)的路徑，即哈密爾頓路。然而，求哈密爾頓路是一個十分困難的問題，這樣的模型沒有給我們的解題帶來任何便利。因此，我們必須另辟蹊徑。4題目來源：ACM/ICPCCentralEuropeRegionalContest1999/2000，有改動

模型2：經(jīng)過分析，我們發(fā)現(xiàn)模型1的失敗之處在于，圖中需要遍歷的信息一也就是每一個盤子——表示在頂點(diǎn)上，而頂點(diǎn)的遍歷問題不易解決。能否將遍歷信息表示在邊上呢？考慮如下的構(gòu)圖方法：以26個字母作為頂點(diǎn)；對于每一個盤子，如果它的首字母為％，末字母為。2，那么從c1向c2連一條有向邊。對于樣例我們可以按圖5所示的方式構(gòu)圖，圖中未表示出的頂點(diǎn)均為孤立點(diǎn)，可以事先將其刪去。這樣，問題轉(zhuǎn)化為在圖中尋找一條不重復(fù)地經(jīng)過每一條邊的路徑，即歐拉路徑。這個問題能夠在。(|E\N)時間內(nèi)解決。圖5小結(jié)比較以上兩個模型，模型1非常直觀，模型2的建立則需要一點(diǎn)逆向思維：我們已經(jīng)習(xí)慣于“頂點(diǎn)表示元素，邊表示元素之間的關(guān)系”這種先入為主的思想，而模型2則是反其道而行之——將元素表示在邊上，而頂點(diǎn)則起到連接各個元素的作用。這說明，我們考慮問題時，必須將算法進(jìn)行反復(fù)地推敲、改進(jìn)，甚至打破舊的思維模式，大膽創(chuàng)新，才能找到解決問題的最佳方法。例題二倉庫管理5題目描述一個公司有N家商店，每家商店銷售相同的M種商品。公司有一個很大的倉庫，商品在運(yùn)往商店之前首先在這里進(jìn)行整理、裝箱。公司將一定數(shù)量的某種商品放到一個箱子中，并貼上商品標(biāo)簽，用1?M來標(biāo)識。這樣，一共有NxM個箱子，每家商店都將得到標(biāo)簽為1?M的箱子各一個。倉庫是在一個狹窄的建筑里，所以箱子只好排成一列。為了加快分發(fā)，管理員決定對箱子重新排列。一個好的排列順序應(yīng)該滿足以下條件：前M個箱子具有不同的標(biāo)識，以便運(yùn)往1號商店；接下來M個箱子具有不同的標(biāo)識，以便運(yùn)往2號商店……依此類推。另外，初始狀態(tài)時只有箱子隊列的末尾才有唯一的一個空位，每一次移動都只能將一個箱子移動到當(dāng)前的空位，并且要求所有移動結(jié)束后，空位必須回到隊尾。請你編寫程序，計算重新排列所需的最少移動次數(shù)和相應(yīng)的移動方式。數(shù)據(jù)規(guī)模1<N,M<400分析構(gòu)造二分圖G，其頂點(diǎn)集V={p,p，…，p}U{q,q，…,q}，其中p?p代表1 2 n 1 2 m 1nn家商店，q1-qm代表m種商品。設(shè)倉庫中商店i的箱子(即從第(i-1)m+1個到第ixm個箱子)中商品j的數(shù)量為ttj，我們需要通過重新排列箱子使得所有t,^=1。對任意i,j(1<i<n,1<j<m)，若t>1，那么從p向q連t-1條有向邊，表示商店i多了，,j iji,jt-1個商品j；若tV1，那么從q向p連1-1條有向邊，表示商店i少了1-1個i,j i,j ji i,j i,j商品j。例如，樣例N=5，M=6的情況，各個箱子的排列情況如下表：413165232356214564132455123466按上述方法構(gòu)造圖G如下:5題目來源：Central-EuropeanOlympiadinInformatics2005Day1DepotRearrangement

1p2P3P4P5P1p2P3P4P5P通過分析整個重排過程中空位的位置，不難發(fā)現(xiàn)：初始和結(jié)束狀態(tài)中，空位處于隊尾的位置；另外還可能有若干個中間狀態(tài)，空位也處于隊尾的位置。我們將空位處于隊尾時的相鄰兩個狀態(tài)之間的若干次移動稱為一個階段。如此定義階段有什么好處呢？其實(shí)，一個階段的移動與圖G中的簡單回路一一對應(yīng)。例如，上圖中回路｛(p,q),(q,P),(P,q),(q,P)｝對應(yīng)的操作序列為:4 5 5 5 5 6 6 4①30331；4131652323562145641324551234616②24330；4131652323562145641324511234656③31324。41316523235621456413245612346J（圖中藍(lán)色格子為移動的起始位置，綠色格子為移動的終止位置。）現(xiàn)在問題轉(zhuǎn)化為：如何在圖G中找出若干個沒有公共邊的回路，使得它們覆蓋圖G中所有的邊。注意到一個長度為totx2的回路對應(yīng)的移動次數(shù)為tot+1，如果用c個回路覆蓋圖G，則總移動次數(shù)sum=M+C。由于題目要求sum盡量小，所以c要盡量小。而圖G中，p.（1<i<n）的入度與出度相等，qj（1<j<m）的入度與出度相等，因此G的每一個極大強(qiáng)連通子圖都有歐拉回路。顯然，用各極大強(qiáng)連通子圖的歐拉回路來覆蓋圖G能夠使得回路數(shù)最少。完整的算法流程如下：1建立二分圖G；2求出G的所有極大強(qiáng)連通子圖；3對于G的每一個極大強(qiáng)連通子圖，求出一條歐拉回路；4根據(jù)各極大強(qiáng)連通子圖的歐拉回路構(gòu)造出對應(yīng)的移動方案。小結(jié)一些看似與歐拉回路，甚至與圖沒有太大關(guān)系的問題，經(jīng)過巧妙的轉(zhuǎn)化，就能構(gòu)圖并且轉(zhuǎn)化成在圖中求歐拉回路，從而高效地解決問題。這也說明歐拉回路應(yīng)用的靈活性。例題三中國郵路問題（版本1）6題目描述A城市的交通系統(tǒng)由若干個路口和街道組成，每條街道都連接著兩個路口。所有街道都是雙向通行的，且每條街道都有一個長度值。一名郵遞員傳送報紙和信件，要從郵局出發(fā)經(jīng)過他所管轄的每一條街道最后返回郵局（每條街道可以經(jīng)過不止一次）。請問他應(yīng)該如何安排自己的路線，使得走過的總長度最短呢？分析這道題目看起來比較復(fù)雜，不好下手。先來分析簡單一點(diǎn)的情況。將路口看成頂點(diǎn)，街道看成無向邊，得到一個無向圖G。如果G不是連通圖，那么一定無解；否則，如果G是歐拉圖，顯然G的任意一條歐拉回路都是最優(yōu)線路。如果G中奇點(diǎn)7個數(shù)為2（設(shè)這兩個頂點(diǎn)為％，v2），那么G中一定存在一條從％到v2的歐拉路徑P。然后，找一條從?2到％的最短路徑R，將其連接到P之后得到一條完整的回路。可以證明，這樣的路線一定是最優(yōu)的。如果G中奇點(diǎn)個數(shù)大于2,怎樣確定最優(yōu)路線呢？注意到前面關(guān)于奇點(diǎn)個數(shù)為2的情況討論中，我們實(shí)際是將從v2到七的最短路徑R所經(jīng)過的邊加入到了G中，即得到的新圖G=GR，而歐拉圖G'的一條歐拉回路即是最優(yōu)路線。經(jīng)過分析，我們發(fā)現(xiàn)加入任意一條路徑R的結(jié)果是路徑R的兩個端點(diǎn)的度增加了1，6題目來源：經(jīng)典問題7度為奇數(shù)的頂點(diǎn)稱為奇點(diǎn)。奇偶性改變；而路徑R中其它結(jié)點(diǎn)的度增加了2,奇偶性不變。因此，增加的每一條路徑的兩個端點(diǎn)都應(yīng)該是奇點(diǎn)，這樣每次增加一條路徑就能減少2個奇點(diǎn)。我們知道，任意圖中奇―人，，，，，， ―人，，， 、, 、里、k-」 山, ―點(diǎn)個數(shù)為偶數(shù)8。設(shè)圖G中奇點(diǎn)個數(shù)為k，那么一定能通過增加3條路徑使得所有頂點(diǎn)的度為偶數(shù)。k更進(jìn)一步地，考慮如何使得增加的3條路徑的總長度最短。顯然，增加的每一條路徑都必須是兩點(diǎn)間的最短路徑；另外，需要給k個奇點(diǎn)找到一種合理的配對方式，使得總長度最小。以圖G的k個奇點(diǎn)作為頂點(diǎn)集構(gòu)造無向完全圖H，邊的權(quán)值為兩點(diǎn)間的最短路徑長度，則H的最小權(quán)完備匹配對應(yīng)最優(yōu)的方案。無向完全的最小權(quán)匹配可以用Edmonds提出的算法9在多項(xiàng)式時間內(nèi)解決。最后按照匹配的方案在圖G中增邊得到圖G，并在圖G中求歐拉回路即可。完整的算法流程如下：1如果G是連通圖，轉(zhuǎn)2,否則返回?zé)o解并結(jié)束；2檢查G中的奇點(diǎn)，構(gòu)成圖H的頂點(diǎn)集；3求出G中每對奇點(diǎn)之間的最短路徑長度，作為圖H對應(yīng)頂點(diǎn)間的邊權(quán)；4對H進(jìn)行最小權(quán)匹配；5把最小權(quán)匹配里的每一條匹配邊代表的路徑，加入到圖G中得到圖G'；6在G中求歐拉回路，即所求的最優(yōu)路線。例題四中國郵路問題（版本2）10題目描述A城市的交通系統(tǒng)由若干個路口和街道組成，每條街道都連接著兩個路口。所有街道都只能單向通行，且每條街道都有一個長度值。一名郵遞員傳送報紙和信件，要從郵局出發(fā)經(jīng)過他所管轄的每一條街道最后返回郵局（每條街道可以經(jīng)過不止一次）。請問他應(yīng)該如何安排自己的路線，使得走過的總長度最短呢？分析本題條件與例題三的唯一區(qū)別是：所有街道只能單向通行。顯然，如果G的基圖不連通，那么一定無解。另外，如果存在某個頂點(diǎn)，它的入度或者出度為0，那么不可能存在經(jīng)過該點(diǎn)的回路。因此，這種情況也是無解的。仿照例題三的思路，考慮能否通過在圖G中增加若干條路徑得到歐拉圖G'，然后在G'8由握手定理，對任意圖G有￡d（v）=2扈|，故奇點(diǎn)個數(shù)必為偶數(shù)。veV9詳見參考文獻(xiàn)4。10題目來源：經(jīng)典問題中求歐拉回路。首先計算每個頂點(diǎn)V的入度與出度之差d'(v)。如果G中所有的d'(v)=0,那么G中已經(jīng)存在歐拉回路。否則，由于￡dr(v)=0，d'(v)的值一定是有正有負(fù)。對于d'(v)>0veV的頂點(diǎn)v，需要增加d'(v)條從v出發(fā)的路徑；對于d'(v)<0的頂點(diǎn)v，需要增加d'(v)條到v結(jié)束的路徑；對于d'(v)=0的頂點(diǎn)v，要求v不作為增加的任何一條路徑的端點(diǎn)(或者是，以v為終止點(diǎn)的路徑數(shù)等于以v為出發(fā)點(diǎn)的路徑數(shù)，但在那種情況下，可以把后者連接到前者之后而合并成一條路徑)。這個模型與網(wǎng)絡(luò)流模型有著驚人的相似！d'(v)>0的頂點(diǎn)v對應(yīng)于網(wǎng)絡(luò)流模型中的源點(diǎn)，它發(fā)出d'(v)個單位的流；d'(v)<0的頂點(diǎn)v對應(yīng)于網(wǎng)絡(luò)流模型中的匯點(diǎn)，它接收-d'(v)個單位的流；而d'(v)=0的頂點(diǎn)v則對應(yīng)于網(wǎng)絡(luò)流模型中的中間結(jié)點(diǎn)，它接收的流量等于發(fā)出的流量。在原問題中還要求增加的路徑總長度最小，我們可以給網(wǎng)絡(luò)中每條邊的費(fèi)用值w(e)設(shè)為圖G中對應(yīng)邊的長度。這樣，在網(wǎng)絡(luò)中求最小費(fèi)用最大流，即可使總費(fèi)用￡f(e)w(e)最小。具體來說，可以這樣構(gòu)造網(wǎng)絡(luò)N:eeE1其頂點(diǎn)集為圖G的所有頂點(diǎn)，以及附加的超級源s和超級匯r；2對于圖G中每一條邊(u,v)，在N中連邊(u,v)，容量為8，費(fèi)用為該邊的長度；3從源點(diǎn)s向所有d'(v)>0的頂點(diǎn)v連邊(s,v)，容量為d'(v)，費(fèi)用為0；4從所有d'(v)<0的頂點(diǎn)u向匯點(diǎn)t連邊(u,t)，容量為—d'(v)，費(fèi)用為0。完整的算法流程如下：1如果G的基圖連通且所有頂點(diǎn)的入、出度均不為0，轉(zhuǎn)2,否則返回?zé)o解并結(jié)束；2計算所有頂點(diǎn)v的d'(v)值；3構(gòu)造網(wǎng)絡(luò)N；4在網(wǎng)絡(luò)N中求最小費(fèi)用最大流；5對N中每一條流量f(u,v)的邊(u,v)，在圖G中增加f(u,v)次得到G；6在G中求歐拉回路，即為所求的最優(yōu)路線。拓展如果將條件改成：部分街道能夠雙向通行，部分街道只能單向通行，該如何解決？1111本問題巳被證明是一個NPC問題。詳見參考文獻(xiàn)5。小結(jié)例題三、例題四以及拓展的問題，雖然條件上只有幾字之差，但解法卻迥然不同。這說明我們在做題時必須仔細(xì)審題，緊緊圍繞題中的關(guān)鍵條件進(jìn)行思考。否則，可能會使思維誤入歧途。另外，我們平時要注意發(fā)散思維、舉一反三：如果將題目改動一個條件該如何解決？這樣，通過思考和解決一系列具有諸多相似點(diǎn)的問題，我們的思維能力和思維深度得到了鍛煉。例題五賭博機(jī)12題目描述一臺賭博機(jī)由n個整數(shù)發(fā)生器T,T，…T組成。T能夠產(chǎn)生的整數(shù)集合為S，1 2n i i并且S〔是集合｛1,2,...n｝的一個子集。S,可以為空集。在賭博機(jī)運(yùn)轉(zhuǎn)的任意時刻，n個發(fā)生器中有且僅有一個發(fā)生器處于活動狀態(tài)。游戲開始時只有T是活動的。設(shè)當(dāng)前的活動發(fā)生器為T，若S^0，游戲者可以在S中選擇一個數(shù)尸，然后機(jī)器將尸從S中刪除，并將活ii i i動狀態(tài)轉(zhuǎn)移到T；否則，S〔=0，那么游戲結(jié)束。如果最后一個活動發(fā)生器為〈，并且游戲結(jié)束時所有S=0，那么游戲者失敗，否則獲勝。i現(xiàn)在你正站在一臺賭博機(jī)面前。在開始游戲之前，你決定先編寫一個程序，判斷你能否獲勝。如果能，程序?qū)⒏嬖V你每次如何選擇合適的數(shù)才能獲勝。數(shù)據(jù)規(guī)模1<n<1000，2：|S|<12000ii=1分析我們將問題抽象成圖結(jié)構(gòu)。構(gòu)造圖G，其頂點(diǎn)集V=｛七,％,...,七｝表示n個發(fā)生器。如果T可以產(chǎn)生八那么從七向七連一條有向邊。在本問題中，任意一次游戲過程在圖G中都對應(yīng)一條從七出發(fā)的簡單路徑。特別地，一次失敗的游戲過程對應(yīng)一條從七出發(fā)的歐拉回路。如果游戲者無論如何都將失敗，那么對應(yīng)的圖G滿足：從七出發(fā)，不管怎么走，只要不刻意地重復(fù)走一條邊，一定能走出一條歐拉回路而不會在途中無法繼續(xù)。我們把這類圖稱為隨機(jī)歐拉圖。顯然，隨機(jī)歐拉圖屬于歐拉圖。根據(jù)歐拉圖的相關(guān)結(jié)論，對于基圖不連通，或者不滿足所有頂點(diǎn)七(1<i<n)的入度等于出度的情況，游戲者無論如何都不會失敗。以下的討論中，我們只考慮圖G為歐拉圖的情況。通過分析，我們不難發(fā)現(xiàn)這樣一個結(jié)論：對于任何一次游戲過程，最后一個活動發(fā)生器12題目來源：PolishOlympiadinInformatics1996StageIIProblem3Gambling，有改動一定是T1。否則，如果最后一個活動發(fā)生器為T(1<i<n)，那么在對應(yīng)的路徑中，進(jìn)入七的次數(shù)比離開七的次數(shù)大1。而七的入度等于出度，所以此時一定存在一條從七出發(fā)的邊還沒有被訪問過，這不符合游戲結(jié)束的條件。也就是說，任何一次游戲過程在圖中對應(yīng)一個簡單回路。假設(shè)某次游戲過程在圖G中對應(yīng)的回路為C。將回路C經(jīng)過的邊從圖G中刪去，得到殘留圖G(即G=G-C)，那么G'中所有頂點(diǎn)的入度與出度相等。這里分為兩種情況：若G為零圖13,那么這是一次失敗的游戲過程；否則，G'的每一個極大強(qiáng)連通子圖都存在歐拉回路。注意到G'中七一定是孤立點(diǎn)，否則游戲不會結(jié)束。因此，G'中一定存在不經(jīng)過七的回路?？傊?，游戲者能夠獲勝，當(dāng)且僅當(dāng)圖G存在一個子圖G，使得G由不經(jīng)過七的回路組成，并且獲勝的游戲過程對應(yīng)G'的補(bǔ)圖G中的歐拉回路。0最后還有一個問題：如何尋找圖G中不經(jīng)過七的回路？其實(shí)，只需將圖G中的頂點(diǎn)七刪除，然后在殘留圖中進(jìn)行深度優(yōu)先遍歷(DFS)即可。如果在DFS遍歷過程中，發(fā)現(xiàn)某個頂點(diǎn)v存在一條回邊指向它的祖先結(jié)點(diǎn)u，那么DFS樹中從u到v的路徑以及邊(v,u)構(gòu)成一個回路。完整的算法流程如下：1、 建立有向圖G；2、 判斷其中是否存在歐拉回路。如果存在，轉(zhuǎn)3,否則任意產(chǎn)生并返回一次游戲過程并結(jié)束；3、 檢查圖G中是否存在不經(jīng)過V］的回路C。如果存在，令G0=G-C，返回圖G0中的歐拉回路并結(jié)束，否則轉(zhuǎn)4；4、 返回游戲失敗?！究偨Y(jié)】歐拉回路是指不重復(fù)地經(jīng)過圖中所有邊的回路。歐拉回路模型簡潔、靈活，容易實(shí)現(xiàn)且算法效率高，因而得到廣泛的應(yīng)用。在實(shí)際問題中，如果能將主要信息集中在邊上，并且轉(zhuǎn)化成遍歷圖中每一條邊，就能很好地運(yùn)用歐拉回路的相關(guān)性質(zhì)和算法高效地解決。因此，在解題過程中，模型的建立起到了至關(guān)重要的作用。而問題的模型往往不是顯而易見的，我們13不含任何邊的圖稱為零圖。必須在仔細(xì)分析、研究題目的基礎(chǔ)上，挖掘問題的本質(zhì)，拓展思路，大膽創(chuàng)新，才能建立合適的模型從而高效地解決問題?！局轮x】本論文的撰寫得到湖南師大附中李淑平老師的精心指導(dǎo)，在此表示衷心的感謝！同時感謝班上信息組同學(xué)和集訓(xùn)隊隊友的幫助與支持！【參考文獻(xiàn)】劉汝佳黃亮《算法藝術(shù)與信息學(xué)競賽》盧開澄盧華明 《圖論及其應(yīng)用》戴一奇胡冠章陳衛(wèi)《圖論與代數(shù)結(jié)構(gòu)》J.Edmonds,E.Johnson《Matching,Eulertours,andtheChinesepostman》C.Papadimitriou《Thecomplexityofedgetraversing》BalticOlympiadinInformatics2001官方解答【附錄】附錄1求無向圖的歐拉回路(遞歸實(shí)現(xiàn))programeuler;constmaxn=10000;｛頂點(diǎn)數(shù)上限｝maxm=100000;ii數(shù)上限｝typetnode=^tr;tr=recordf,t:longint邊的起始點(diǎn)和終止點(diǎn)｝al:boolean訪問標(biāo)記｝rev,next:tnode反向邊和鄰接表中的下一條邊｝end;varn,m,bl:longint;｛頂點(diǎn)數(shù)，邊數(shù)，基圖的極大連通子圖個數(shù)｝tot:longint;g:array[1..maxn]oftnode;d:array[1..maxn]oflongint;頂點(diǎn)的度｝fa,rank:array[1..maxn]oflongint;｛并查集中元素父結(jié)點(diǎn)和啟發(fā)函數(shù)值｝list:array[1..maxm]oftnode;最終找到的歐拉回路｝o:boolean;原圖中是否存在歐拉回路｝procedurebuild(ta,tb:longint);｛在鄰接表中建立邊(ta,tb)｝vart1,t2:tnode;begint1:=new(tnode);t2:=new(tnode);t1八.f:=ta;t1八.t:=tb;t1八.al:=false;t1八.rev:=t2;t1八.next:=g[ta];g[ta]:=t1;t2八.f:=tb;t2八.t:=ta;t2八.al:=false;t2八.rev:=t1;t2八.next:=g[tb];g[tb]:=t2;end;proceduremerge(a,b:longint);在并查集中將a,b兩元素合并｝varoa,ob:longint;beginoa:=a;whilefa[a]<>adoa:=fa[a];fa[oa]:=a;ob:=b;whilefa[b]<>bdob:=fa[b];fa[ob]:=b;ifa<>bthenbegindec(bl);^并后，基圖的極大連通子圖個數(shù)減少1｝ifrank[a]=rank[b]theninc(rank[a]);ifrank[a]>rank[b]thenfa[b]:=aelsefa[a]:=b;end;end;procedureinit;(初始化｝vari,ta,tb:longint;beginfillchar(fa,sizeof(fa),0);fillchar(rank,sizeof(rank),0);fillchar(d,sizeof(d),0);readln(n,m);fori:=1tondofa[i]:=i;bl:=n;fori:=1tomdobeginreadln(ta,tb);build(ta,tb);inc(d[tb]);inc(d[ta]);merge(ta,tb);end;end;proceduresearch(i:longint);｛以i為出發(fā)點(diǎn)尋找歐拉回路｝varte:tnode;beginte:=g[i];whilete<>nildobeginifnotte八.althenbeginte八.al:=true;te八.rev八.al:=true;search(te八.t);list[tot]:=te;dec(tot);end;te:=te八.next;end;end;proceduremain;｛主過程｝vari:longint;begino:=false;fori:=1tondoifd[i]=0thendec(bl);排除孤立點(diǎn)的影響｝ifbl<>1thenexit;原圖不連通，無解｝fori:=1tondoifodd(d[i])thenexit;存在奇點(diǎn)，無解｝o:=true;fori:=1tondoifd[i]<>0thenbreak;tot:=m;search(i);從一個非孤立點(diǎn)開始尋找歐拉回路｝end;procedureprint;｛輸出結(jié)果｝vari:longint;beginifnotothenwriteln('Nosolution.')elsebeginwriteln(list[1]八.f);fori:=1tomdowriteln(list[i]八.t);end;end;begininit;main;print;end.附錄2求無向圖的歐拉回路(非遞歸實(shí)現(xiàn))programeuler;constmaxn=10000;｛頂點(diǎn)數(shù)上限｝typetnode=^tr;tr=recordf,t:longint邊的起始點(diǎn)和終止點(diǎn)｝rev,prev,next:tnode反向邊和鄰接表中的上一條邊，下一條邊｝end;varn,m,bl:longint;｛頂點(diǎn)數(shù)，邊數(shù)，基圖的極大連通子圖個數(shù)｝g:array[1..maxn]oftnode;d:array[1..maxn]oflongint;頂點(diǎn)的度｝fa,rank:array[1..maxn]oflongint;｛并查集中元素父結(jié)點(diǎn)和啟發(fā)函數(shù)值｝o:boolean;原圖中是否存在歐拉回路｝f,link:tnode;用鏈表保存最終找到的歐拉回路｝procedurebuild(ta,tb:longint);在鄰接表中建立邊(ta,tb)｝vart1,t2:tnode;begint1:=new(tnode);t2:=new(tnode);t1八.f:=ta;t1八.t:=tb;t1八.rev:=t2;t1八.prev:=nil;t1八.next:=g[ta];ifg[ta]<>niltheng[ta]八.prev:=t1;g[ta]:=t1;t2八.f:=tb;t2八.t:=ta;t2八.rev:=t1;t2八.prev:=nil;t2八.next:=g[tb];ifg[tb]<>niltheng[tb]八.prev:=t2;g[tb]:=t2;end;proceduremerge(a,b:longint);在并查集中將a,b兩元素合并｝varoa,ob:longint;beginoa:=a;whilefa[a]<>adoa:=fa[a];fa[oa]:=a;ob:=b;whilefa[b]<>bdob:=fa[b];fa[ob]:=b;ifa<>bthenbegindec(bl);合并后，基圖的極大連通子圖個數(shù)減少1｝ifrank[a]=rank[b]theninc(rank[a]);ifrank[a]>rank[b]thenfa[b]:=aelsefa[a]:=b;end;end;procedureinit;(初始化｝vari,ta,tb:longint;beginfillchar(fa,sizeof(fa),0);fillchar(rank,sizeof(rank),0);fillchar(d,sizeof(d),0);readln(n,m);fori:=1tondofa[i]:=i;bl:=n;fori:=1tomdobeginreadln(ta,tb);build(ta,tb);inc(d[tb]);inc(d[ta]);merge(ta,tb);end;end;proceduredelm(t:tnode);｛在鄰接表中刪除邊t｝varno:longint;beginno:=t八.f;ift八.prev<>nilthent八.prev八.next:=t\nextelseg[no]:=t八.next;ift八.next<>nilthent八.next八.prev:=t\prev;end;procedurefindcircle(no:longint;varhead,tail:tnode);以no為起點(diǎn)找一條回路，保存在以head為頭，tail為尾的鏈表中｝vari:longint;begini:=no;head:=g[i];tail:=head;g[i]:=g[i]八.next;ifg[i]<>niltheng[i]八.prev:=nil;tail八.prev:=nil;tail八.next:=nil;delm(tail八.rev);i:=tail八.t;whilei<>nodobegintail八.next:=g[i];g[i]:=g[i]八.next;ifg[i]<>niltheng[i]八.prev:=nil;tail:=tail八.next;tail八.prev:=nil;tail八.next:=nil;delm(tail八.rev);i:=tail八.t;end;end;proceduremain;｛主過程｝vari:longint;te,head,tail:tnode;begino:=false;fori:=1tondoifd[i]=0thendec(bl);排除孤立點(diǎn)的影響｝ifbl<>1thenexit;原圖不連通，無解｝fori:=1tondoifodd(d[i])thenexit;存在奇點(diǎn)，無解｝o:=true;fori:=1tondoifd[i]<>0thenbreak;findcircle(i,head,tail);首先任意找一條回路｝link:=head;f:=link;whilelink<>nildoifg[link八.t]<>nilthenbeginfindcircle(link八.t,head,tail);tail八.next:=link八.next;link八.next:=head將兩個回路合并｝endelselink:=link八.next;end;procedureprint;｛輸出結(jié)果｝beginifnotothenwriteln('Nosolution.')elsebeginlink:=f;writeln(link八.f);whilelink<>nildobeginwriteln(link八.t);link:=link八.next;end;end;end;begininit;main;print;end.附錄3例題一的英文原題PlayonWordsSomeofthesecretdoorscontainaveryinterestingwordpuzzle.Theteamofarchaeologistshastosolveittoopenthatdoors.Becausethereisnootherwaytoopenthedoors,thepuzzleisveryimportantforus.Thereisalargenumberofmagneticplatesoneverydoor.Everyplatehasonewordwrittenonit.Theplatesmustbearrangedintoasequenceinsuchawaythateverywordbeginswiththesameletterasthepreviouswordends.Forexample,theword"acm”canbefollowedbytheword“Motorola”.Yourtaskistowriteacomputerprogramthatwillreadthelistofwordsanddeterminewhetheritispossibletoarrangealloftheplatesinasequence(accordingtothegivenrule)andconsequentlytoopenthedoor.InputSpecificationTheinputconsistsofTtestcases.Thenumberofthem(T)isgivenonthefirstlineoftheinputfile.EachtestcasebeginswithalinecontainingasingleintegernumberNthatindicatesthenumberofplates(1VnV100000).ThenexactlyNlinesfollow,eachcontainingasingleword.Eachwordcontainsatleasttwoandatmost1000lowercasecharacters,thatmeansonlyletters'a'through'z'willappearintheword.Thesamewordmayappearseveraltimesinthelist.OutputSpecificationYourprogramhastodeterminewhetheritispossibletoarrangealltheplatesinasequencesuchthatthefirstletterofeachwordisequaltothelastletterofthepreviousword.Alltheplatesfromthelistmustbeused,eachexactlyonce.Thewordsmentionedseveraltimesmustbeusedthatnumberoftimes.Ifthereexistssuchanorderingofplates,yourprogramshouldprintthesentence"Orderingispossible.".Otherwise,outputthesentence"Thedoorcannotbeopened.".SampleInput32acmibm3acmmalformmouse2okokOutputfortheSampleInputThedoorcannotbeopened.Orderingispossible.Thedoorcannotbeopened.附錄4例題二的英文原題DepotRearrangementAcompanyoperatesNshops,sellingMdifferentproductsineachshop.Thecompanyhasalargedepotwheretheproductsarepackedbeforedeliveringtoshops.Eachshopreceivesthesamenumberofitemsofeachproduct.Hencethecompanypacksacertainnumberofitemsofagivenproductintoacontainer,andlabelsthatcontainerwiththeproductidentifier.Productsareidentifiedbythenumbersfrom1toM.Thus,attheendofpacking,thereareN*Mcontainersinthedepot,andexactlyNcontainersarelabeledwithagivenproductlabelforeachproduct.Becausethedepotisinanarrowbuilding,thecontainersarearrangedinasinglerow.Inordertospeed-updistribution,themanagerofthedepotwantstorearrangethecontainers.Sincetheproductdeliverytotheshopsoccursbysendingexactlyonetrucktoeachshop,andeachtruckcarriesonecontainerofeachproduct,asuitablearrangementisthefollowing.ThefirstMcontainersintherowmustbelabeledwithdifferentproductlabels,thesecondMcontainersintherowmustbelabeledwithdifferentproductlabels,andsoon.Unfortunately,thereisonlyonefreeplaceattheendoftherowtoholdacontainer.Thereforetherearrangementmustbeperformedbysuccessivelypickingupacontainerandmovingittothefreeplace.Aftertherearrangementthefreeplacemustbeattheendoftherow.Thegoalistoachievetherequiredrearrangementbyaminimalnumberofmoves.TaskYouaretowriteaprogramthatcomputesarearrangementwhichneedstheminimalnumberofmoves.InputThefirstlineofthetextfiledepot.incontainstwointegers,NandM.N(1VNV400)isthenumberofshopsandM(1VMV400)isthenumberofproducts.ThesecondlinecontainsN*Mintegers,thelabelsofthecontainersintheirinitialorder.Eachproductidentifierx(1VxVM)occursexactlyNtimesintheline.OutputThefirstlineofthetextfiledepot.outcontainsoneintegerS,theminimalnumberofmovesthatarenecessarytoobtainarequiredorderofthecontainerrow(SubtaskA).ThefollowingSlinesdescribearearrangement(SubtaskB).Eachlinecontainsapairofintegersxy.Thepairxydescribesamove:thecontaineratpositionxistomovetopositiony.Positionsareidentifiedbythenumbersfrom1toN*M+1;initiallythepositionN*M+1isfree(holdsnocontainer).Amovefromxtoyislegalonlyifpositionyisfreepriortothemove.Afteramovefromxtoythepositionxwillbefree.ItisenoughtooutputonlythefirstlineifyousolveonlySubtaskA.Iftherearemultiplepossibilities,yourprogramshouldoutputonlyone;itdoesnotmatterwhichone.Exampledepot.in56413165232356214564132455123466depot.out8TOC\o"1-5"\h\z311891841031431243024附錄5例題五的英文原題GamblingAgamblingmachineconsistsofngeneratorsofintegers:q,...,G,where1<=n<=1000.ThegeneratorG.cangenerateintegersonlyfromthecertainsetS.inc