動機
頂點集 上有多少棵樹?當 ,答案是三:三個頂點的樹必為路徑,而中間的頂點決定整棵樹。當 ,形狀有路徑和星形兩種。標號路徑有 條,因為把頂點次序倒轉仍是同一條路徑;標號星形樹則有 棵,每個頂點都可選作中心。總數是 。由 和 ,我們猜想答案是 。
逐一按形狀計數很快便會變得困難:形狀愈來愈多,而且各自有不同的對稱性。較好的方法是建立雙射。數目 正好是所有長度為 、項取自 的序列的個數。因此,我們希望找到一條規則,把每棵標號樹轉成這樣的序列;再找另一條規則把每個序列轉回樹,並使兩條規則互相抵消。Prüfer 編碼正是這樣一對規則。本章的核心是證明兩個算法互逆;證明的關鍵是編碼記錄了樹的度數。
定義
定義 1.5.1
(標號樹與葉)
有限正整數集合 上的標號樹,是頂點集為 、連通而且無圈的簡單無向圖。我們主要研究 ;但算法也會作用於頂點集不再是初始整數段的子樹,所以容許任何上述的 ,並使用整數原有的次序。兩棵標號樹相等,意思是它們的邊集相同;這比同構有更嚴格的要求。
葉是度數為 的頂點。只有一個頂點的樹,其唯一頂點度數為 ,因此沒有葉。基於這個原因,以下算法要求 ; 的情況另行處理。
我們使用含 個頂點的樹 的三個標準事實:
- 恰有 條邊,因此 。
- 至少有兩個葉。考慮一條最長路徑:端點不能有路徑外的鄰點,否則可延長路徑;也不能有路徑上的第二個鄰點,否則形成圈。
- 若 是葉,則 是頂點集為 的樹。刪除度數為一的頂點既不會產生圈,也不會令其餘頂點失去連通性。
對有限序列 和數值 ,用 表示 在 中出現的次數;用 表示 中出現的值所組成的集合。
定義 1.5.2
(Prüfer 編碼器)
設 是 上的樹,。令 。對 ,執行以下三步:
- 令 為 中最小的葉;
- 記錄其唯一鄰點 ;
- 令 。
輸出為 。
定義 1.5.3
(Prüfer 解碼器)
設 的項均屬於 ,其中 。令 ,並用 表示剩餘的後綴。對 ,執行以下三步:
- 令 ;
- 加入邊 ;
- 令 ,並從後綴移去 。
後綴為空時,以一條邊連接 中餘下的兩個標號。輸出的圖記為 。
兩個算法都具有確切的遞歸性:第一步後, 的編碼器接下來的操作與 的編碼器完全相同;同樣, 上 的解碼器第一步後的操作,與 上 的解碼器完全相同。
編碼器有良好定義
引理 1.5.4
(編碼器不變量)
對每個 ,圖 是一棵有 個頂點的樹。因此每一步都有定義, 的長度恰為 ,而 是單獨一條邊。
證明
(對刪除次數歸納)
對 歸納。 成立,因為 。假設 是有 個頂點的樹,其中 。由於 ,事實 2 保證存在葉,故最小葉 及其唯一鄰點 均有定義。由事實 3, 是有 個頂點的樹。
迴圈恰執行 次,每次記錄一項,故編碼長度為 。最後的樹有兩個頂點,因此只有一條邊。
定理 1.5.5
(編碼記錄度數)
對每個頂點 ,
特別地, 的葉恰是 中沒有在 出現的頂點。
證明
(計算一個頂點處的邊)
第 步恰刪去一條邊 ;最後仍餘一條邊。因此 的每條邊不是在某一步恰好被刪一次,就是最後餘下的邊。
固定 ,數算 中以 為端點的邊,分兩種情況。
情況一:某個 使 。 第 步時 是 的葉,所以它恰有一條邊存留至該步。這條邊在第 步被刪,而此時 是被刪的葉,不是被記錄的鄰點。其餘 條以 為端點的邊均在較早的步驟 被刪。每個這樣的步驟中, 仍然存在,故被刪的葉 不是 ,邊 以 為端點當且僅當 。反過來,每個滿足 的 都刪去一條以 為端點的邊。第 步後 已被刪,再不會出現。因此 。
情況二: 是最後兩個頂點之一。 在 的度數為 。同樣的論證表明,恰有 條以它為端點的邊在滿足 的步驟中被刪。
定理第二句隨即成立,因為 當且僅當 。
度數記錄定理適用於每棵樹,包括 。 的編碼是後綴 ,所以它的葉恰是當前頂點中沒有在剩餘後綴出現的頂點。這正是解碼器使用的規則。
解碼器有良好定義,並輸出一棵樹
引理 1.5.6
(解碼器不變量)
對每個 ,在第 步之前:
- (I1) ;
- (I2) 的每一項都屬於 。
因此:
- (a) 候選頂點 存在;
- (b) 且 ,故不會產生自環;
- (c) ,即被記錄的鄰點仍然可用。
最後 含兩個不同元素。 的每個標號要麼作為某個 恰被移去一次,要麼屬於最後一對;而 有 條邊。
證明
(對解碼步驟歸納)
時兩個不變量均成立:,而 的各項都在 中。
假設第 步之前 (I1)、(I2) 成立。後綴 有 項,故最多只有 個不同的值。由於 , 必有元素沒有出現在後綴,證得 (a)。
由 (I2),。它不同於 ,因為 被選為不在 出現的標號,而 是該後綴首項。這證明 (b),並得到 (c)。
為檢查不變量得以保持,注意 。 的各項原本都在 中,因而屬於 ;它們亦不是 ,故屬於 。
標號只有被選中時才會離開 ,而且不會重新加入,故不會被選兩次。移去 個標號後剩下兩個,最後將它們連接。迴圈加了 條邊,再加最後一條,共 條。
定理 1.5.7
(解碼器輸出一棵樹)
是 上的標號樹。
證明
(逐個接上頂點的向下歸納)
對 ,令 為 上的圖,其邊為最後一條邊及所有 的 。這些邊確實位於 內:若 ,則 和 均屬於 。
是單獨一條邊,故是一棵樹。由 加入新頂點 和唯一的邊 ,便得到 ;由解碼器不變量引理的 (c),。在一棵樹上用一條邊接上一個新頂點,所得仍是樹。向下歸納可得 是 上的樹。
解碼所得樹的度數同樣由序列決定。這可單從解碼器檢驗,無須使用編碼器。
引理 1.5.8
(解碼所得度數)
在 中,每個 均滿足 。
證明
(計算解碼後一個頂點處的邊)
的邊是各條 和最後一條邊。它們兩兩不同:若 ,較早移去的標號 不在 中,但較後一條邊的兩個端點都在 中。最後一條邊的兩個端點也在 中,故亦不同於較早的邊。
邊 以 為端點,當且僅當 或 ;由解碼器不變量引理的 (b),兩者不會同時發生。每個滿足 的指標 都貢獻一條以 為端點的邊。
此外,以下兩者恰有一者成立: 對唯一一個 滿足 ,或 屬於最後一對。無論哪種情況,都再貢獻一條以 為端點的邊。
兩個算法互逆
定理 1.5.9
(編碼與解碼互逆)
對每個有限集合 ,若 ,則:
- 對 上每棵樹 ,;
- 對每個序列 ,。
證明
(對頂點數歸納)
兩部分均對 歸納,並同時考慮所有大小為 的頂點集。
當 ,唯一的序列是空序列,而 上唯一的樹是連接兩個頂點的一條邊。解碼器會連接兩個標號,所以兩個等式均成立。
現在設 。
第一部分。 令 。由度數記錄定理, 是 的葉集。因此解碼器首先選擇 ,並加入 的邊 。
解碼器餘下的操作,就是在 上解碼 。根據編碼器的定義,這序列是 。由歸納假設,餘下操作輸出 。因此
第二部分。 令 。由解碼度數引理, 的葉恰是 ,故最小的葉是 。邊 屬於 ,而 是葉,所以編碼器記錄 。
刪去 只會移去邊 。餘下的圖恰是解碼器在 上解碼 所構造的圖。由歸納假設,其編碼為 ,故 。
證明透視
各部分只用自己一方的事實
證明對每個算法只需要一個事實,而每一部分只使用屬於自己的那個。第一部分用度數記錄定理(只關於 的陳述)說明解碼器的第一個選擇 就是編碼器第一次刪除的 ;第二部分用解碼度數引理(只關於 的陳述)說明編碼器第一次刪除的是 。兩部分都沒有假設正要證明的恆等式,所以論證不是循環的。
兩部分的關鍵一步相同:樹的葉恰是不在其編碼中出現的標號,所以「最小的缺席標號」與「最小的葉」選出同一個頂點。一步之後,每個算法都在 或 上繼續;這是一個大小為 、通常不再是整數起始段的集合,因此歸納要同時對所有同樣大小的頂點集進行,並由基礎情形 收尾。
Cayley 公式與度數序列
定理 1.5.10
(Cayley 公式)
當 , 上標號樹的數目為 。當 ,這等於 ,即唯一的邊 。當 ,恰有一棵樹:頂點集為 的無邊圖,它既連通又無圈。
互逆定理給出 上的樹與集合 之間的雙射;後者有 個元素。 的情況由直接觀察解決,而不是由公式解決。上述編碼論證不適用於 ,因為序列的長度不可能為 ,編碼器在此亦沒有定義。
定理 1.5.11
(指定度數的樹)
設 ,且 均為整數。若每個 且 ,則 上滿足所有 的樹,其數目為
否則數目為 。
由度數記錄定理與互逆定理,這些樹對應於長度為 的序列,其中每個 恰出現 次。指定的出現次數之和正確:
故排列數就是上述多項式係數。若某個 ,它不可能是圖的度數;若某個 ,頂點 便是孤立點,這在有 個頂點的連通圖中不可能;若總和不符,則違反事實 1。以上任一情況都沒有符合條件的樹。
例題
例題 1.5.12
(星形樹與路徑)
星形樹。 設 為 上以 為中心的星形樹,其中 。除 外每個頂點都是葉,刪除葉後 仍是中心。因此每次記錄的鄰點都是 ,而
有 項。這與度數記錄定理一致,因為 。
路徑。 考慮路徑 。最小葉總是當前的左端點,故編碼為 。
再看重新標號的路徑 ,它的葉是 和 。刪去 時記錄 ;之後 成為葉,刪去 時記錄 。其編碼為 ,而路徑 的編碼為 。這兩棵樹同構,但它們是不同的標號樹,編碼也不同。
例題 1.5.13
(編碼七個頂點的樹)
設 的邊為 。其度數為 、,其餘頂點度數均為 。
| 步驟 | 當前的葉 | 刪去 | 記錄 |
|---|---|---|---|
| 1 | |||
| 2 | |||
| 3 | |||
| 4 | |||
| 5 |
最後餘下頂點 和 ,編碼為 。正如度數記錄定理所預測, 和 各出現兩次, 出現一次,而葉從不出現。
例題 1.5.14
(解碼序列)
在 上解碼 。
| 步驟 | 剩餘標號 | 後綴 | 未出現的標號 | 新邊 |
|---|---|---|---|---|
| 1 | ||||
| 2 | ||||
| 3 | ||||
| 4 | ||||
| 5 |
最後一條邊是 。輸出有六條邊 。
第 4 步時,標號 要待兩個 都離開後綴才可被選。為檢查結果,可重新編碼這棵樹:依次刪去 ,記錄的鄰點為 ,恰好是 。
反例與適用範圍
反例模式
改變選葉規則
對路徑 ,「最小葉」規則給出 ;「最大葉」規則先刪去 ,給出 。若規則容許選擇「任意葉」,甚至不能定義函數,因為一棵樹可得到兩個編碼。此雙射依賴確切的規則和標號的次序。
這個計數同樣只屬於完全圖:它列舉的是 的生成樹,而不是其他圖的生成樹。
反例模式
其他圖的生成樹
Cayley 公式只計算完全圖 的生成樹。邊為 的四圈恰有 棵生成樹,而不是 棵。解碼序列 得到邊 、 和 ,其中 不屬於該圈。Prüfer 解碼並不是列舉一般圖的生成樹的算法。
常見錯誤
常見錯誤
(對照完整的原始序列)
解碼器必須檢查標號是否不在剩餘後綴中。在解碼例題中,標號 曾在原序列出現,但在第 4 步、兩個 都離開後綴之後,它仍被正確選取。
常見錯誤
(數形狀而不是數標號樹)
上有 棵標號樹,卻只有兩種無標號形狀,即路徑和星形。公式 並不計算同構意義下的樹,Prüfer 編碼也不是形狀的不變量:同構的路徑 與 的編碼分別是 與 。
最後,算法並不是因為兩者「看來可逆」就互逆:沒有度數記錄定理和解碼度數引理,便沒有理由相信解碼器的首次選擇與編碼器的首次刪除一致。
練習
快速檢查
(設 且 。計算 上頂點 的度數為 的標號樹數目。)
解答
由度數記錄定理與互逆定理,我們要數算 中恰有 項等於 的序列。先以 種方法選出這些位置,再把其餘 個位置各填上 中的一個標號。數目為
範圍 恰好涵蓋可能值:連通性給出下界 ,而 給出上界。底數 至少為 ,所以指數為 時該因子確實等於 。當 ,唯一情況 給出 ,即單獨一條邊。
作為檢查,令 。 分別給出 、 和 ,而 。一般情況下,由二項式定理,
快速檢查
(設 是 上邊為 的樹。計算 ,再將結果解碼,確認可還原 。)
解答
編碼。 起初的葉為 。步驟如下:
- 刪去 並記錄 ;此時 成為葉;
- 刪去 並記錄 ;
- 刪去 並記錄 ;此時 成為葉;
- 刪去 並記錄 ;此時 成為葉;
- 刪去 並記錄 ;此時 成為葉;
- 刪去 並記錄 。
剩下頂點 和 。編碼為 ,長度為 ;唯一度數為 的頂點 出現兩次。
解碼。 各步未在後綴出現的標號集合依次為:
- ,得到邊 ;
- ,得到 ;
- ,得到 ;
- ,得到 ;
- ,得到 ;
- ,得到 。
最後一條邊是 。這七條邊恰是 的邊。
快速檢查
(列出 和 上所有標號樹及其編碼,並在 上解碼 。)
解答
上有一棵樹,即邊 ,其編碼為空序列,符合 。
上每棵樹都是以某個頂點 為中點的路徑。中點度數為 ,其餘兩點是葉,因此編碼為 。三棵樹的編碼分別是 、 和 ,符合 。
在 上解碼 :沒有出現在後綴的標號是 和 ,故解碼器連接 與 ,留下 ;最後一條邊為 。所得路徑為 ,中點是預期的 。
快速檢查
(計算 上度數序列為 的標號樹數目,並解釋為何沒有度數序列為 的樹。)
解答
所有度數至少為 ,而總和為 ,故可用指定度數定理:
第二個序列的總和為 ,故數目為 。
快速檢查
(利用指定度數定理證明,當 , 上有 條標號路徑。)
解答
一棵樹是路徑,當且僅當兩個頂點的度數為 ,其餘頂點的度數為 。端點有 種選法。對每一選擇,指定度數定理給出
總數為 。
這與先前的計數一致: 時得 ; 時得 ,符合動機一節; 時得 。
相關筆記
預備知識:樹、葉,以及邊數 。本章引向度數序列的計數,以及一般圖的生成樹計數;後者需要 Prüfer 編碼以外的方法。