算法思路

任意選擇一個(gè)頂點(diǎn)v0v0,

假設(shè)已經(jīng)確定好了前面的路徑了。在剩下的邊中選一個(gè)新的邊

• 這個(gè)新的邊需要跟它前面的那個(gè)點(diǎn)要相關(guān)聯(lián)
• 除非沒有點(diǎn)可以選，否則不能是剩余子圖的割邊。

一直到等這個(gè)步驟2完成為止。

得到的路徑就是歐拉環(huán)路

證明（摘抄自老師課件）

定理4.2：若G是Euler圖，則G中任一用Fleury算法作出的跡都是G的Euler環(huán)游。
證：設(shè)G是Euler圖，W_n=v_0 e_1 v_1?e_n v_n是G中用Fleury算法作出的跡，顯然，終點(diǎn)v_n在G_n中的度必然為零。由此推知v_n=v_0；換言之，W_n是閉跡。
現(xiàn)在假設(shè)W_n不是G的Euler環(huán)游，并且設(shè)S是G_n中度為正的頂點(diǎn)集。那么，S是非空的，且v_n∈S ?，這里S ?=V\S。設(shè)m是使得v_m∈S
以及v_(m+1)∈S ?的最大整數(shù)。由于W_n 終止于S ?，所以e_(m+1) 是G_m中[S,S ?]的僅有的一條邊，因此也就是G_m的一條割邊
設(shè)e是G_m 中和v_m關(guān)聯(lián)的另外任意一條邊。可以推得(第2步)：e必然也是G_m 的一條割邊，因而是G_m [S]的割邊。但是由于G_m [S]=G_n [S]，
所以G_m [S]中每個(gè)頂點(diǎn)都是偶點(diǎn)。可是由此推出G_m [S]沒有割邊

總結(jié)

以上是生活随笔為你收集整理的Fleury算法找欧拉环游的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。