動機
一條恰好使用每條邊一次的路線,與一條恰好經過每個頂點一次的路線,解決的是不同的問題。當需要枚舉的對象是轉移或相互重疊的詞時,頂點重複是很自然的。歐拉(Euler)遍歷把「每條邊都要用到」這一要求轉化為度數平衡與一個連通性條件。
對於詞,圖的頂點表示所記住的固定長度的前綴,每條邊表示一個需要列出的完整區塊。每條邊恰好遍歷一次,就使每個區塊恰好出現一次。圖的重疊規則把一條迴路轉化為一個緊湊的循環詞,而不是一份互不相連的區塊列表。
定義
定義 5.2.1
(有向跡、度數與弱連通)
設有限有向多重圖至少有一個頂點,其弧帶有標號,容許有環與平行弧。跡不重複使用任何弧。閉歐拉跡從某個頂點出發並回到同一頂點,且每條弧恰好使用一次。端點為相異頂點 的開歐拉跡從 出發、到 結束,同樣每條弧恰好使用一次。
一個環對入度和出度各貢獻一。在非孤立頂點上的弱連通是指:當存在弧時,忽略方向並去掉孤立頂點之後,這些頂點構成一個連通圖。無邊圖在任意選定的頂點處擁有空的閉跡。
定義 5.2.2
(萬有詞與詞重疊圖)
固定一個大小為 的字母表 和區塊長度 。正長度 的循環詞按週期方式讀取;它的長度為 的區塊可以繞過末端迴繞,若 甚至可以迴繞多於一次。萬有循環詞包含 中的每個元素。我們要尋找每個元素恰好出現一次的循環詞。
線性詞不迴繞。若其長度為 ,則長度為 的區塊有 個起始位置。詞重疊圖的頂點集為 ,對 中的每個詞有一條帶標號的弧,從它長度為 的前綴指向它長度為 的後綴。當 時,只有一個空詞頂點以及 個帶標號的環。
概念視角結構
頂點儲存重疊記憶;邊才是必須恰好出現一次的對象
頂點重複意味著重新訪問了所記住的後綴,這是無害的。重複一條邊則會重複它的整個區塊,而這在所求的萬有詞中是被禁止的。度數平衡定理控制著對邊的枚舉,而重疊關係把它壓縮成一個循環序列。
定理/命題
定理 5.2.3
(平衡性與非孤立連通性刻劃歐拉跡)
有限有向多重圖存在閉歐拉跡,當且僅當所有頂點的入度等於出度,並且在存在弧時其非孤立的底圖是連通的。
對於相異的 ,從 到 的開歐拉跡存在,當且僅當同樣的連通性條件成立, 的出度比入度大一, 的入度比出度大一,且其餘所有頂點都是平衡的。
定理 5.2.4
(萬有詞達到兩個計數下界)
對每個 ,存在長度為 的循環詞,其中每個長度為 的詞恰好出現一次。沒有更短的萬有循環詞。
另存在長度為 的線性詞,恰好包含每個長度為 的詞一次,並且不存在更短的萬有線性詞。循環的定義包括單符號字母表,即使所要求的區塊長度超過整個循環的長度。
定理 5.2.5
(該構造關於其顯式圖是線性的)
給定帶有持久未用弧指標的鄰接表,歐拉圈拼接可以在 次圖操作和 個儲存條目內實現。對於重疊圖,這些數量為 和 。
對於固定的字母表,帶有顯式詞標號的直接實現使用 的符號運算量與儲存空間,包括圖的構造和初始線性詞前綴。當 時,輸出規模本身關於 是指數級的;這並不是關於區塊長度的多項式輸出規模的論斷。
證明思路或證明
證明
(度數計數、貪心閉片段與拼接)
閉準則的必要性來自對跡在每個頂點處到達與離開次數的計數。其使用過的弧在底圖意義下也連通了每個非孤立頂點。開跡的度數差來自唯一的一次起始離開和最後一次到達;其餘每一次到達都與一次離開配對。
對於閉情形的充分性,從一個有未用出弧的頂點出發,貪心地沿未用弧前進。若從 出發的跡停在不同的頂點 ,則在該處已用入弧數將比已用出弧數多一。由於沒有未用出弧,這一差值也會使該處的已用入弧數超過原來的入度,與原圖的平衡性矛盾。因此有限的貪心跡只能停在其起點,從而得到一條閉跡。
去掉閉跡所用的弧,剩餘圖仍保持平衡。若當前跡上有某個頂點還有未用出弧,則在該處重複此論證,構造另一條閉跡,並在該頂點處把它拼接進舊跡。弧的標號使得即使幾條弧有相同端點,也不會被重複使用。
當不再有這樣的頂點時,所有弧必然都已被使用。否則,取底圖中一條路徑第一次越過邊界之處,弱連通性提供了一條未用弧,它連接一個已在跡上的頂點與一個跡外的頂點。已用的越界弧會使其兩個端點都已在跡上。若這條未用越界弧指向外部,它直接提供了跡上的一條未用出弧。若它指向內部,則其端點處的剩餘平衡性也在該處提供了一條未用出弧。兩者都與停止條件矛盾。這樣就證明了充分性,而無需把弱連通性替換為未經證明的更強假設。
對於開情形,添加一條特別的輔助弧 。它使兩個端點平衡,並保持非孤立連通性。增廣圖中存在閉歐拉跡。將其弧列表旋轉,使之從該輔助弧之後立即開始,然後刪去該弧;剩下的列表就是從 到 的開歐拉跡。特別的標號使得即使已有另一條弧具有相同的方向和端點,這一論證依然有效。
證明透視
剩餘平衡性阻止貪心片段停在錯誤的頂點
充分性的證明在兩個不同的地方使用它的兩個假設。平衡性在局部、在貪心行走停下的那一刻使用:從 出發而卡在 的行走,進入 的已用弧比離開 的多一條;既然再沒有未用的出弧, 原來的出度便小於入度。後續每一輪都可以作同樣的計數,因為閉片段在每個頂點用掉的入弧與出弧一樣多,所以剩餘圖仍然平衡。
連通性只在拼接停止之後、在整體上使用一次:它給出一條連接路線頂點集與其餘部分的越界弧,而越界弧在路線上那個端點處的剩餘平衡性,把指向內部的越界弧轉化為一條未用出弧。兩個假設不能互相代替:兩個分離頂點上各有一個環的圖是平衡的,卻無法連起來;只有一條弧 的圖是連通的,卻使行走滯留在 。開情形藉一條帶標號的輔助弧化為閉情形,因此不需要第三個論證。
實現拼接而不必反覆掃描整條路線
證明
(指標與工作表的計數)
保持出弧鄰接指標和一個由路線出現位置組成的循環鏈表。每當使用一條弧,貪心片段便推進相應的出弧指標。為每個已訪問的頂點儲存一個已知的路線出現位置,這樣新的閉片段就能透過常數次指標修改插入該處。
維護一個候選出現位置的工作表,這些位置的頂點可能仍有未用出弧。當新片段產生出現位置時,檢查並安排它們;當舊候選從工作表中移除時,若其出弧列表已耗盡則跳過。若某個起始頂點仍有更多未用弧,則它也出現在新創建的片段中,因而可以透過這個新出現位置再次被安排。
每條弧只產生常數個儲存的路線條目,並且被鄰接指標處理一次。每個出現位置只在創建時被安排一次,每個被安排的候選只被移除一次。因此,初始的頂點掃描、鄰接處理、工作表和拼接合計需要 次操作。每處理一個片段就重新掃描整條不斷增長的路線的樸素實現不具有這一界;工作表的計數分析是該實現的一部分。
重疊圖滿足該準則
證明
(重疊圖的度數與強連通性)
對任意長度為 的頂點,在末尾添加任一字母表符號得到一條出弧,在開頭添加任一符號得到一條入弧。兩種度數都是 ,當 時的空詞頂點也不例外。
該圖是強連通的,因而是弱連通的:從任意頂點出發,依次添加所需目標頂點的各個符號。經過 步之後,所記住的後綴恰好就是該目標。當 時無需任何步驟,因為只有一個頂點。因此,已證明的歐拉準則給出一條包含全部 條帶標號區塊弧各一次的迴路。
重疊把迴路轉化為一個詞
證明
(把迴路讀成詞、下界與符號代價)
讀取線性表示的方法是:先寫出初始頂點的詞,然後按迴路次序寫出每條弧的最後一個符號。用歸納法可知,在每個新寫出的符號處結束的長度為 的區塊恰好是該弧的標號:先前的後綴是它的尾頂點,而添加操作給出整條邊所對應的詞。這樣的區塊共有 個,兩兩相異且窮盡所有區塊。總長度為 。
對於循環表示,讀取沿迴路各條弧的最後一個符號。在每個弧位置結束的區塊都是它的標號,因為相繼的弧標號在其後 個符號與前 個符號處重疊,包括由末到首的閉合。沿著之前的弧向後追溯,可對全部 個符號證明這一點,即使這意味著迴繞多於一次。從區塊的結束位置轉為區塊的起始位置只是對循環位置做一個置換,所以每個區塊仍然恰好出現一次。
任何長度為 的循環詞只有 個區塊起始位置,因此要包含全部不同的區塊,必須有 。線性萬有詞首先長度至少為 ,然後還需 。這是兩個下界,二者都被迴路構造所達到。
對於固定字母表上帶顯式詞標號的圖的構造,把全部長度為 的頂點儲存在一棵字典樹中。每條弧及其移位後的頭部可以用 次符號操作寫出並定位;因此枚舉所有弧用 。歐拉階段採用所述的圖條目模型。這一顯式的符號界不把任意長的詞標號當作一次免費的比較,也不在未計入代價的情況下假設存在常數時間的字串字典。
例題詳解
例題 5.2.6
(八個二進制三元區塊恰好填滿長度為八的循環)
循環詞 的連續迴繞三元區塊為
這些恰好是長度為三的全部八個二進制詞。在重疊圖中,它們給出閉頂點路線 。四個兩位頂點的入度與出度都是二,而且每條區塊弧恰好出現一次。
線性代表為 ,即把最初兩個符號附在末尾,以給出最後的迴繞區塊。它的十個符號恰好給出八個普通的三元區塊位置,因此同樣達到線性下界。
例題 5.2.7
(把環片段拼接進更大的迴路)
使用如下的弧: 處的一個環、一條弧 和一條弧 。兩個頂點都是平衡的。單獨的環就是在 處一個有效的初始閉片段。
其餘兩條弧構成閉片段 ,可以在 的該出現位置處拼接,得到 或相應的循環旋轉。儘管 重複出現,每條弧仍恰好使用一次。環是一條獨立的弧,貢獻一個入關聯和一個出關聯,而不是因無關緊要而被丟棄。
例題 5.2.8
(單符號字母表需要重複迴繞,而不是更長的循環)
對於字母表 和區塊長度四,唯一的區塊是 。單符號循環 透過週期讀取在其唯一的起始位置包含它,需要迴繞數次。重疊圖只有一個頂點 ,以及一個標號為 的環。
最短的線性詞則是 ,長度為四,與公式 的預測一致。當區塊長度為一、字母表為 時,該圖是一個空詞頂點加三個環,而循環 恰好包含每個單符號區塊一次。這兩個邊界情形使用相同的定義。
常見錯誤
反例模式
僅有平衡的度數無法連接不相連的片段
取兩個頂點,各有自己的一個環,二者之間沒有弧。每個頂點的入度都等於出度,但沒有任何一條跡能同時使用兩個環。非孤立的底圖是不連通的。這就是為甚麼連通性是一個獨立的假設,而不能從度數平衡推出。
常見錯誤
(歐拉跡可以重複頂點)
不要把歐拉跡與不得重複頂點的路徑混淆。在二進制三元區塊的重疊圖中,迴路 把四個頂點各經過兩次;只有弧才是恰好使用一次的。
常見錯誤
(迴繞與不迴繞的區塊計數)
循環區塊的計數包含迴繞,而線性計數只包含後面還有足夠符號的起始位置。長度為八的循環 包含全部二進制三元區塊,但若當作線性詞讀取,它只有六個三元區塊位置;線性代表 需要多兩個符號。
常見錯誤
(對圖線性不等於對區塊長度多項式)
線性的圖操作界並不會使一個相對於其較小的長度參數而言指數級長的萬有詞變成多項式長度。當 、 時,循環有 個符號,任何把它寫出來的算法都至少需要這麼多步。
總結
有向圖的度數平衡與非孤立弱連通性給出歐拉跡的完整判別準則。剩餘平衡性支持閉片段的拼接,持久指標加上被安排的出現位置給出線性的圖運算量。詞重疊圖滿足這些條件,從而產生最優的萬有循環詞與線性詞,其中短循環與空前綴的邊界情形均被明確處理。
練習
快速檢查
(驗證循環詞 恰好一次地包含字母表 上的所有有序對。證明其長度是最小的。)
列出它的九個循環對的起始位置,包括由末到首的那一對。
解答 · 答案
這些對為 。九個可能的有序對各出現一次。任何包含它們全部的循環詞至少有九個起始位置,因此長度至少為九。所給出的詞達到這一下界,其最後一對由末兩個符號接上起始的零構成。
快速檢查
(為甚麼包含每個三位區塊的二進制線性詞至少有十個符號?給出一個達到該界的詞。)
數一數普通的起始位置,並與八個可能的區塊比較。
解答 · 答案
長度為 的線性詞有 個三元區塊位置。要包含全部八個不同的區塊,需要 ,故 。詞 達到十,它的區塊已在第一個例子中列出。長度為八的循環之所以足夠,只是因為其迴繞的區塊也被容許;去掉這一約定,計數就會改變。
快速檢查
(對於由弧 、、 以及 處的一個環構成的圖,求一條開歐拉跡。驗證端點的度數,並解釋輔助弧的構造。)
把環保留為四條帶標號的弧之一。
解答
頂點 的出度為二、入度為一; 的入度為二、出度為一; 是平衡的。非孤立的底圖是連通的。弧序列 使用了全部四條弧,並具有所要求的端點。
添加輔助弧 使每個頂點都平衡。相應的閉跡可以旋轉,使該弧排在最後,刪去它便得到所示的開跡。它的特別標號使之區別於可能同時存在的任何原有平行弧。