【正文】 法的偽代碼如下： ()。證明　只需按如圖所示的方式合并。性質(zhì)設(shè)、是圖的兩個(gè)沒有公共邊，但有至少一個(gè)公共頂點(diǎn)的簡單回路，我們可以將它們合并成一個(gè)新的簡單回路。贓熱俁閫歲匱閶鄴鎵騷鯛漢鼉。下面以無向圖為例，介紹求歐拉回路的算法。這兩個(gè)結(jié)論的證明與定理和推論的證明方法類似，這里不再贅述。推論有向圖為半歐拉圖，當(dāng)且僅當(dāng)?shù)幕鶊D連通，且存在頂點(diǎn)的入度比出度大、的入度比出度小，其它所有頂點(diǎn)的入度等于出度。連通，且所有頂點(diǎn)的入度等于出度。滲釤嗆儼勻諤鱉調(diào)硯錦鋇絨鈔。給圖加上一條虛擬邊得到圖，則圖的每一個(gè)頂點(diǎn)度均為偶數(shù)，故圖中存在歐拉回路。充分性。而對(duì)于其它任意一個(gè)頂點(diǎn)，進(jìn)入的次數(shù)等于離開的次數(shù)，故的度為偶數(shù)。設(shè)圖的一條歐拉路徑為由于經(jīng)過圖的每一條邊，而圖沒有孤立點(diǎn)，所以也經(jīng)過圖的每一個(gè)頂點(diǎn)，為連通圖成立。由定理可以立即得到一個(gè)用于判定半歐拉圖的推論：推論無向圖為半歐拉圖，當(dāng)且僅當(dāng)為連通圖且除了兩個(gè)頂點(diǎn)的度為奇數(shù)之外，其它所有頂點(diǎn)的度為偶數(shù)。故是圖的歐拉回路。依此類推，存在不屬于的邊。令，從出發(fā)有一條不屬于的邊。下面證明回路是圖的歐拉回路。設(shè)圖中邊數(shù)最多的一條簡單回路 邊沒有重復(fù)出現(xiàn)的回路稱為簡單回路。由握手定理，有，與假設(shè)相矛盾。假設(shè)圖中不存在回路，而是連通圖，故一定是樹，那么有。煢楨廣鰳鯡選塊網(wǎng)羈淚鍍齊鈞。而對(duì)于圖的任意一個(gè)頂點(diǎn)，經(jīng)過時(shí)都是從一條邊進(jìn)入，從另一條邊離開，因此經(jīng)過的關(guān)聯(lián)邊的次數(shù)為偶數(shù)。設(shè)圖的一條歐拉回路為。定理　無向圖為歐拉圖，當(dāng)且僅當(dāng)為連通圖且所有頂點(diǎn)的度為偶數(shù)。我們經(jīng)常需要判定一個(gè)圖是否為歐拉圖（或半歐拉圖），并且找出一條歐拉回路（或歐拉路徑）。顯然，這樣做并不會(huì)影響圖中歐拉回路的存在性。在以下討論中，假設(shè)圖不存在孤立點(diǎn) 度為0的頂點(diǎn)稱為孤立點(diǎn)。歐拉圖存在歐拉回路的圖稱為歐拉圖。歐拉回路圖中經(jīng)過每條邊一次并且僅一次的回路稱作歐拉回路。二　相關(guān)知識(shí)首先介紹相關(guān)概念和定理。本文將介紹歐拉回路的相關(guān)理論知識(shí)，并通過幾道例題分析歐拉回路的實(shí)際應(yīng)用。釅錒極額閉鎮(zhèn)檜豬訣錐顧葒鈀。經(jīng)過悉心研究，歐拉終于在年發(fā)表了論文《哥尼斯堡的七座橋》，不但成功地證明了“七橋問題”無解，而且找到了對(duì)于一般圖是否存在這類回路的充要條件。圖無數(shù)熱衷于此的人試圖解決這個(gè)問題，但均以失敗告終。這便是著名的“哥尼斯堡七橋問題”。聞創(chuàng)溝燴鐺險(xiǎn)愛氌譴凈禍測(cè)樅。它誕生于十八世紀(jì)的歐洲古城哥尼斯堡。矚慫潤厲釤瘞睞櫪廡賴賃軔朧。然后通過幾個(gè)實(shí)例，介紹了與歐拉回路相關(guān)的幾類典型問題。歐拉回路性質(zhì)與應(yīng)用探究湖南師大附中　仇榮琦【摘要】歐拉回路，又稱“一筆畫”，是圖論中可行遍性問題的一種。本文首先介紹了歐拉回路的相關(guān)理論知識(shí)，以及求歐拉回路的算法。最后對(duì)歐拉回路的模型進(jìn)行了總結(jié)，指出其特點(diǎn)和具備的優(yōu)勢(shì)?！娟P(guān)鍵詞】歐拉回路　歐拉路徑【正文】一　引言歐拉回路問題是圖論中最古老的問題之一。普瑞格爾河流經(jīng)這座城市，人們?cè)趦砂兑约昂又虚g的兩個(gè)小島之間建了七座橋（如圖）。圖市民們喜歡在這里散步，于是產(chǎn)生了這樣一個(gè)問題：是否可以找到一種方案，使得人們從自己家里出發(fā)，不重復(fù)地走遍每一座橋，然后回到家中？這個(gè)問題如果用數(shù)學(xué)語言來描述，就是在圖中找出一條回路，使得它不重復(fù)地經(jīng)過每一條邊。殘騖樓諍錈瀨濟(jì)溆塹籟婭騍東。問題傳到了歐拉（ , ）那里，立即引起了這位大數(shù)學(xué)家的重視。后人為了紀(jì)念歐拉這位偉大的數(shù)學(xué)家，便將這類回路稱為歐拉回路。歐拉回路問題在信息學(xué)競賽中有著廣泛的應(yīng)用，近年來在各類比賽中出現(xiàn)了許多與之相關(guān)的試題。彈貿(mào)攝爾霽斃攬磚鹵廡詒爾膚。設(shè)是一個(gè)圖。歐拉路徑圖中經(jīng)過每條邊一次并且僅一次的路徑稱作歐拉路徑。半歐拉圖存在歐拉路徑但不存在歐拉回路的圖稱為半歐拉圖。；否則，先將所有孤立點(diǎn)從圖中刪除。謀蕎摶篋飆鐸懟類蔣薔點(diǎn)鉍雜。對(duì)于無向圖有如下結(jié)論：廈礴懇蹣駢時(shí)盡繼價(jià)騷巹癩龔。證明必要性。由于經(jīng)過圖的每一條邊，而圖沒有孤立點(diǎn)，所以也經(jīng)過圖的每一個(gè)頂點(diǎn)，為連通圖成立。又由于不重復(fù)地經(jīng)過了圖的每一條邊，因此的度為偶數(shù)。充分性。由于圖所有頂點(diǎn)的度為偶數(shù)而且不含孤立點(diǎn)，那么圖的每一個(gè)頂點(diǎn)的度至少為。故圖中一定存在回路。為鵝婭盡損鵪慘歷蘢鴛賴縈詰聾。假設(shè)不是歐拉回路，則中至少含有一個(gè)點(diǎn)，該點(diǎn)的度大于經(jīng)過該點(diǎn)的關(guān)聯(lián)邊的次數(shù)。若，則頂點(diǎn)自身構(gòu)成一個(gè)環(huán)，可以將其加入中形成一個(gè)更大的回路；否則，若，由于的度為偶數(shù)，而中經(jīng)過的關(guān)聯(lián)邊的次數(shù)也是偶數(shù)，所以必然存在一條不屬于的邊。故是一條新的回路，將其加入中可以形成一個(gè)更大的回路，這與是圖的最大回路的假設(shè)相矛盾?；[叢媽羥為贍僨蟶練淨(jìng)櫧撻曉。證明　必要性。對(duì)于頂點(diǎn)，進(jìn)入的次數(shù)比離開的次數(shù)少；對(duì)于頂點(diǎn)，進(jìn)入的次數(shù)比離開的次數(shù)多：故和的度為奇數(shù)。預(yù)頌圣鉉儐歲齦訝驊糴買闥齙。設(shè)是圖中唯一的兩個(gè)度為奇數(shù)的頂點(diǎn)。從中刪去得到一條從到的路徑，即為圖的歐拉路徑。對(duì)于有向圖，可以得到類似的結(jié)論：定理有向圖為歐拉圖，當(dāng)且僅當(dāng)?shù)幕鶊D 忽略有向圖所有邊的方向，得到的無向圖稱為該有向圖的基圖。鐃誅臥瀉噦圣騁貺頂廡縫勵(lì)羆。擁締鳳襪備訊顎輪爛薔報(bào)贏無。注意到定理的證明是構(gòu)造性的，可以利用它來尋找歐拉回路。首先給出以下兩個(gè)性質(zhì)：性質(zhì)設(shè)是歐拉圖中的一個(gè)簡單回路，將中的邊從圖中刪去得到一個(gè)新的圖，則的每一個(gè)極大連通子圖都有一條歐拉回路。證明　若為無向圖，則圖的各頂點(diǎn)的度為偶數(shù)；若為有向圖，則圖的各頂點(diǎn)的入度等于出度。壇摶鄉(xiāng)囂懺蔞鍥鈴氈淚躋馱釣。圖由此可以得到以下求歐拉圖的歐拉回路的算法：在圖中任意找一個(gè)回路；將圖中屬于回路的邊刪除；在殘留圖的各極大連通子圖中分別尋找歐拉回路；將各極大連通子圖的歐拉回路合并到中得到圖的歐拉回路。 頂點(diǎn)的每個(gè)鄰接點(diǎn) 邊未被標(biāo)記 將邊作上標(biāo)記。 ()。最后依次取出棧每一條邊而得到圖的歐拉回路。在實(shí)際應(yīng)用中，以上的實(shí)現(xiàn)可能導(dǎo)致堆棧溢出（遞歸的深度最多可以達(dá)到層），因此常常需要將其改造成非遞歸的形式。蠟變黲癟報(bào)倀鉉錨鈰贅籜葦繯。以上介紹了歐拉回路的相關(guān)知識(shí)和算法。下面通過剖析若干實(shí)例，探究建立歐拉回路模型的方法，使讀者對(duì)歐拉回路算法有更深入的認(rèn)識(shí)。三　例題例題一單詞游戲 題目來源：ACM/ICPC Central Europe Regional Contest 1999/20XX，有改動(dòng)綾鏑鯛駕櫬鶘蹤韋轔糴飆鈧麥。你需要給這些盤子安排一個(gè)合適的順序，使得相鄰兩個(gè)盤子中，前一個(gè)盤子上面單詞的末字母等于后一個(gè)盤子上面單詞的首字母。如果能，請(qǐng)給出一個(gè)合適的順序。數(shù)據(jù)規(guī)模分析通過對(duì)題目條件的一些初步分析，我們很容易