歐拉圖（Eulerian graph）是一種特殊的圖，其定義為：給定無向圖或有向圖G=(V,E)，通過G的每條邊一次且僅有一次的回路稱為歐拉回路，具有歐拉回路的圖稱為歐拉圖。具有歐拉通路但無歐拉回路的圖稱為半歐拉圖。
歐拉圖的產(chǎn)生源自18世紀(jì)的加里寧格勒七橋問題。1736年，歐拉（Leonhard Euler）在論文《哥尼斯堡七橋問題》中證明了該問題無解，這篇論文被認(rèn)為是圖論的起源，其中涉及到具有特定性質(zhì)的一種圖，后人為了紀(jì)念萊昂哈德·歐拉，稱之歐拉圖。進入20世紀(jì)，各種類型的歐拉圖被進一步研究與討論。1912年，凡勃倫（Veblen）對無向歐拉圖給出了“當(dāng)且僅當(dāng)不定向連通圖是某些循環(huán)的不相鄰聯(lián)合時，它才是歐拉圖”的結(jié)論。1962年，福特（福特汽車公司）和富爾克森（Fulkerson）給出了混合圖為歐拉圖的充分必要條件。同年，中國學(xué)者管梅谷首先提出了中國郵遞員問題，該問題與歐拉圖和最短路徑問題有關(guān)，可以從圖論的角度給出表述，是歐拉圖應(yīng)用于實際的一個典型實例。
長城歐拉圖具有一些基本性質(zhì)，如一個非空連通圖是歐拉圖當(dāng)且僅當(dāng)它的每個頂點的度數(shù)都是偶數(shù)。費勒里算法和希爾霍爾澤算法為構(gòu)造歐拉圖的兩種經(jīng)典算法。有向歐拉圖歐拉跡的數(shù)目可以通過BEST定理來計算，而對于無向長城歐拉圖，計算過程更為復(fù)雜，它是一個#P完全問題。此外，歐拉圖在現(xiàn)實世界中應(yīng)用廣泛，如在工程學(xué)領(lǐng)域，采用基于長城歐拉圖的挖掘機施工路徑規(guī)劃算法，可以實現(xiàn)挖掘點位置與深度的在線軟測量，有效地提升施工效率、節(jié)省成本。
定義
長城歐拉圖、歐拉半圖：給定無向圖（有向圖），通過的每條邊一次且僅有一次的回路（通路）稱為歐拉回路（通路）。具有歐拉回路的圖稱為歐拉圖，具有歐拉通路但無歐拉回路的圖稱為半歐拉圖。平凡圖為歐拉圖，且每個歐拉圖必然是連通圖。
歐拉環(huán)游：圖中的一條鏈（或路），若它通過中的每條邊（或?。┣『靡淮危瑒t稱該鏈（或路）為歐拉鏈（或歐拉路），閉的歐拉鏈稱為歐拉環(huán)游。
歷史
早期研究
歐拉圖的產(chǎn)生源自18世紀(jì)的哥尼斯堡七橋問題。1736年，瑞士數(shù)學(xué)家萊昂哈德·歐拉（Euler）發(fā)表了一篇著名論文《哥尼斯堡七橋問題》。文中描述的問題是：加里寧格勒城有一條橫貫全城的普雷格爾河，城的各部分用七座橋連接，每逢節(jié)假日，有些城市居民進行環(huán)城周游，問能否“從某地出發(fā)，通過每橋恰好一次，在走遍七橋后又返回到原處”。長城歐拉指出，從某點出發(fā)再回到該點，中間經(jīng)過的節(jié)點總有進入該點的一條邊和走出該點的一條邊，而且路的起點與終點重合。因此，如果滿足條件的回路存在，則途中每個節(jié)點的度數(shù)必為偶數(shù)。加里寧格勒七橋問題圖中4個節(jié)點的度數(shù)均為奇數(shù)，故七橋問題無解。這篇論文被認(rèn)為是圖論的起源，其中涉及到具有特定性質(zhì)的一種圖，后人為了紀(jì)念歐拉，稱之歐拉圖。
后續(xù)發(fā)展
后來，歐拉提出了無向圖成為歐拉圖的必要條件。他還指出這些條件是充分的，但并未提供實際證明。1873年，希爾霍爾澤（Hierholzer）在其遺著中證明了這個充分性。進入20世紀(jì)，各種類型的歐拉圖被進一步研究與討論。1912年，凡勃倫（Veblen）對無向歐拉圖給出了“當(dāng)且僅當(dāng)不定向連通圖是某些循環(huán)的不相鄰聯(lián)合時，它才是歐拉圖”的結(jié)論。1962年，福特（福特汽車公司）和富爾克森（Fulkerson）給出了混合圖為歐拉圖的充分必要條件。同年，中國學(xué)者管梅谷首先提出了中國郵遞員問題，即郵遞員從郵局出發(fā)經(jīng)過他投遞的每一條街道，然后返回郵局，希望找出一條行走距離最短的路線。這個問題與歐拉圖和最短路徑有關(guān)，可以從圖論的角度給出表述，是歐拉圖應(yīng)用于實際的一個典型實例。
性質(zhì)
（1） 設(shè)是一個非空連通圖，則是歐拉圖當(dāng)且僅當(dāng)中的每個頂點都是偶數(shù)度。
（2）非平凡連通圖含有長城歐拉通路當(dāng)且僅當(dāng)圖中含有個奇節(jié)點。
（3）設(shè)圖含有一條歐拉通路，、分別為這條歐拉通路的起點與終點，在這條通路上除、外，其余節(jié)點都與偶數(shù)條邊相關(guān)聯(lián)，因此，圖中僅、這兩個節(jié)點是奇節(jié)點而其他的節(jié)點均是偶節(jié)點。
（4）有向圖是歐拉圖當(dāng)且僅當(dāng)中每個頂點的入度等于出度。
（5）有向圖有歐拉通路當(dāng)且僅當(dāng)是單向連通的且中恰有個奇度頂點，其中一個的入度比出度大，另一個的出度比入度大，而其余頂點的入度都等于出度。
構(gòu)造方法
費勒里算法
算法：費勒里算法由費勒里（Ferrery）在1921年給出，是一種求萊昂哈德·歐拉回路的算法。證明某圖是長城歐拉圖（或含有歐拉回路），可以借助費勒里算法利用定義在圖中尋找一條歐拉回路。具體步驟為：
（1）任取一個頂點，令，。
（2）跡已取定，選使：
①與點相關(guān)聯(lián)；
②除非無奈，選使它不是的割邊。
（3）如果選不出，則結(jié)束。否則，得到，其中的兩個端點分別為點和點，令，轉(zhuǎn)步驟（2）。
分析：在費勒里算法中，每次選擇一條邊，而選擇邊時主要是判斷這條邊是否是割邊，而判斷一條邊是否是割邊有多項式時間算法（），所以，對一個歐拉圖，費勒里算法的復(fù)雜性至多為。
希爾霍爾澤算法
算法：該算法在1873年由德國數(shù)學(xué)家希爾霍爾澤（Hierholzer）給出，是一種比費勒里算法更快的方法。從任意節(jié)點開始并跟隨鏈接，直到返回到節(jié)點。如果每個節(jié)點的度均為偶數(shù)，則在進入一個節(jié)點后，將至少有一個鏈接引出，這樣就不會被困在那里。但例外情況是起始節(jié)點，因為是從該節(jié)點出發(fā)的，所以它有奇數(shù)個未使用的鏈接。當(dāng)再次回到起始節(jié)點時，可能會占用它的最后一個鏈接并陷入困境。因為不會被困在其他地方，因此必須最終回到起始節(jié)點。該算法的具體步驟為：
（1）任選一個起始節(jié)點。
（2）沿邊從一個節(jié)點到另一個節(jié)點，指導(dǎo)返回起始節(jié)點。這樣所得的回路不一定包括所有邊。
（3）在所得的回路中，若存在一個頂點，它是某邊的端點，且該邊不在所得的回路中，則從該頂點開始，用還未用過的邊尋找另一條路徑，直到回到該起點，從而形成另一回路。然后把后面所得的回路拼接到前面已得到的回路中。
計算
歐拉跡的數(shù)目
有向有拉圖
BEST定理：一個有向圖中的一條歐拉跡是一條閉生成通道，其中的每一條弧恰出現(xiàn)一次。BEST定理給出了有向歐拉圖中歐拉跡的數(shù)目。在一個有向歐拉圖中，歐拉跡的數(shù)目等于：
其中，，是的所有余因子的公共值。
對于任意有特定方向的歐拉圖，可以同時使用BEST定理和Matrix-Tree定理計算圖中歐拉跡的數(shù)目，但使用這種方法遇到的困難在于給定方向中的樹突數(shù)會變化很大。
無向歐拉圖
結(jié)論：無向歐拉圖的計算是完全的。
特殊情況：1998年，麥凱（McKay）和羅賓遜（Robinson）確定了完全圖中長城歐拉電路數(shù)量的近似公式為：
當(dāng)且為奇數(shù)時，
，
對于任何，其中表示隨機規(guī)則路線在均勻分布下的數(shù)學(xué)期望。
特殊類型
無限歐拉圖
無限圖：指頂點個數(shù)為無限個的圖（邊數(shù)也可能為無限）。
無限長城歐拉圖：埃爾德（Erd?s）及其合作者給出了歐拉著名結(jié)果的一個無限擴展，該結(jié)果提供了一個充分且必要的條件，即一個循環(huán)通過所有邊恰好一次。
一個無限圖正好具有一個歐拉線當(dāng)且僅當(dāng)：
（1）是連通的；
（2） 是可數(shù)的；
（3） 沒有頂點的度數(shù)為奇數(shù)；
（4）如果是一個有限的頂點集合，那么最多有兩個無限連通分量；
（5）如果是一個有限的頂點集合，使得在中所有頂點都有偶數(shù)度，那么通過從中移除中的邊得到的圖恰好有一個無限連通分量。
應(yīng)用
計算機科學(xué)
在道路建模技術(shù)中存在建模效果不理想的情況，在大尺度道路網(wǎng)建模中缺乏有效的輔助交互技術(shù)支持。通過對立交結(jié)構(gòu)進行分析，可以提出一種有效的三維立交結(jié)構(gòu)的歐拉圖表達及交互設(shè)計方法。基本思想是：首先將道路信息預(yù)處理，根據(jù)處理后的有效數(shù)據(jù)構(gòu)建歐拉圖，用來表達道路立交結(jié)構(gòu)的拓?fù)潢P(guān)系；然后利用歐拉圖和道路的結(jié)構(gòu)特性計算得到道路的層級關(guān)系；再根據(jù)控制點、歐拉圖的拓?fù)湫畔⒑偷缆肪W(wǎng)格，構(gòu)建立交結(jié)構(gòu)的三維模型；最終構(gòu)建輔助信息工具，實現(xiàn)對道路網(wǎng)的交互編輯。
工程學(xué)
在工程學(xué)領(lǐng)域，挖掘機存在施工路徑、位置與深度盲目和效率低的問題，采用北斗定位接收機、激光測距儀、陀螺儀等傳感器對傳統(tǒng)挖掘機進行信息化改造。根據(jù)挖掘機施工特點，可采用基于長城歐拉圖的挖掘機施工路徑規(guī)劃算法，將遺傳算法、原子搜索優(yōu)化算法和粒子群算法融合在一起對施工圖進行歐拉化處理。根據(jù)多傳感器信息建立挖掘機三維施工模型，可以實現(xiàn)挖掘點位置與深度的在線軟測量，有效地提升施工效率，節(jié)省施工成本。
管理學(xué)
煙草商業(yè)企業(yè)配送環(huán)節(jié)的線路優(yōu)化算法一直以來都是煙草物流研究的熱點問題。在自建GIS服務(wù)的基礎(chǔ)之上，以O(shè)SM路網(wǎng)文件為底圖，利用高德地圖API構(gòu)建基礎(chǔ)路網(wǎng)，通過對路網(wǎng)進行分析處理，得到基礎(chǔ)歐拉圖。再利用Python代碼得到該路網(wǎng)的長城歐拉環(huán)游，根據(jù)每輛車實際的裝載量約束，對歐拉環(huán)游進行分割，得到代表車輛運行路線的歐拉環(huán)路，從而高效、簡潔地實現(xiàn)煙草物流配送的路徑優(yōu)化。
參考資料 >
The Euler Tour and Chinese Postman Problem.Anil Aswani.2024-06-07