歐拉圖的判定

122886 閱讀 0 評(píng)論 0 點(diǎn)贊

本篇將簡(jiǎn)要介紹歐拉圖的概念、實(shí)現(xiàn)和應(yīng)用，幫助大家在答題中更好的判定。

一、定義

圈：任選圖中一個(gè)頂點(diǎn)為起點(diǎn)，沿著不重復(fù)的邊，經(jīng)過(guò)不重復(fù)的頂點(diǎn)為途徑，之后又回到起點(diǎn)的閉合途徑稱為圈。

歐拉路徑：通過(guò)圖中所有邊一次且僅一次遍歷所有頂點(diǎn)的路徑稱為歐拉(Euler)路徑；

歐拉回路：通過(guò)圖中所有邊一次且僅一次行遍所有頂點(diǎn)的回路稱為歐拉回路；

歐拉圖：具有歐拉回路的圖稱為歐拉圖；

半歐拉圖：有歐拉路徑但沒(méi)有歐拉回路的圖稱為半歐拉圖。

歐拉圖與半歐拉圖的判定：

G是歐拉圖 ? G中所有頂點(diǎn)的度均為偶數(shù) ? G是若干個(gè)邊不重的圈的并。

G是半歐拉圖 ? G中恰有兩個(gè)奇數(shù)度頂點(diǎn)。

二、性質(zhì)

歐拉圖中所有頂點(diǎn)的度數(shù)都是偶數(shù)。

若G是歐拉圖，則它為若干個(gè)環(huán)的并，且每條邊被包含在奇數(shù)個(gè)環(huán)內(nèi)。

三、判別法

1. 無(wú)向圖是歐拉圖當(dāng)且僅當(dāng)：

（1）非零度頂點(diǎn)是連通的

（2）頂點(diǎn)的度數(shù)都是偶數(shù)

2. 無(wú)向圖是半歐拉圖當(dāng)且僅當(dāng)：

（1）非零度頂點(diǎn)是連通的

（2）恰有 0 或 2 個(gè)奇度頂點(diǎn)

3. 有向圖是歐拉圖當(dāng)且僅當(dāng)：

（1）非零度頂點(diǎn)是強(qiáng)連通的

（2）每個(gè)頂點(diǎn)的入度和出度相等

4. 有向圖是半歐拉圖當(dāng)且僅當(dāng)：

（1）非零度頂點(diǎn)是弱連通的

（2）至多一個(gè)頂點(diǎn)的出度與入度之差為 1

（3）至多一個(gè)頂點(diǎn)的入度與出度之差為 1

（4）其他頂點(diǎn)的入度和出度相等

四、求歐拉回路或歐拉路

1. Fleury 算法

也稱避橋法，是一個(gè)偏暴力的算法。

算法流程為每次選擇下一條邊的時(shí)候優(yōu)先選擇不是橋的邊。

一個(gè)廣泛使用但是錯(cuò)誤的實(shí)現(xiàn)方式是先 Tarjan 預(yù)處理橋邊，然后再 DFS 避免走橋。但是由于走圖過(guò)程中邊會(huì)被刪去，一些非橋邊會(huì)變?yōu)闃蜻厡?dǎo)致錯(cuò)誤。最簡(jiǎn)單的實(shí)現(xiàn)方法是每次刪除一條邊之后暴力跑一遍 Tarjan 找橋，時(shí)間復(fù)雜度是。復(fù)雜的實(shí)現(xiàn)方法要用到動(dòng)態(tài)圖等，實(shí)用價(jià)值不高。

2. Hierholzer 算法

也稱逐步插入回路法。

（1）過(guò)程

算法流程為從一條回路開(kāi)始，每次任取一條目前回路中的點(diǎn)，將其替換為一條簡(jiǎn)單回路，以此尋找到一條歐拉回路。如果從路開(kāi)始的話，就可以尋找到一條歐拉路。

（2）實(shí)現(xiàn)

Hierholzer 算法的暴力實(shí)現(xiàn)如下：

Hierholzer 算法

（3）性質(zhì)

這個(gè)算法的時(shí)間復(fù)雜度約為。實(shí)際上還有復(fù)雜度更低的實(shí)現(xiàn)方法，就是將找回路的 DFS 和 Hierholzer 算法的遞歸合并，邊找回路邊使用 Hierholzer 算法。

如果需要輸出字典序最小的歐拉路或歐拉回路的話，因?yàn)樾枰獙⑦吪判?，時(shí)間復(fù)雜度是（計(jì)數(shù)排序或者基數(shù)排序可以優(yōu)化至）。如果不需要排序，時(shí)間復(fù)雜度是。

（4）應(yīng)用

有向歐拉圖可用于計(jì)算機(jī)譯碼。

設(shè)有 m 個(gè)字母，希望構(gòu)造一個(gè)有個(gè)扇形的圓盤(pán)，每個(gè)圓盤(pán)上放一個(gè)字母，使得圓盤(pán)上每連續(xù) n 位對(duì)應(yīng)長(zhǎng)為 n 的符號(hào)串。轉(zhuǎn)動(dòng)一周（次）后得到由 m 個(gè)字母產(chǎn)生的長(zhǎng)度為 n 的個(gè)各不相同的符號(hào)串。