動機
偏序刻劃了哪些對象可以排在哪些對象之後,同時容許某些元素對互不可比。如果要把全部元素安排到若干有序的「軌道」中,至少需要多少條軌道?每個反鏈都給出一個障礙:它的元素不能位於同一條軌道上。狄爾沃斯(Dilworth)定理指出,在有限偏序集中,這個顯而易見的障礙就是唯一的障礙。
證明會將相容的相鄰選擇轉化為匹配的邊。匹配為每個元素至多選定一個前驅和一個後繼。隨後,最小頂點覆蓋會揭示一個最大反鏈。這一構造既給出一種安排,又給出少於該數目的軌道不可能的證書,因此其結論比兩個數相等這一無解釋的等式更有用。
定義
定義 6.2.1
(鏈、反鏈、高度與寬度)
設 為有限偏序集。鏈是其元素兩兩可比的子集。反鏈是其相異元素兩兩不可比的子集。高度 是最大鏈的大小,寬度 是最大反鏈的大小。鏈劃分把 表示為若干非空鏈的不交併;反鏈劃分則使用非空反鏈。對於空偏序集,高度、寬度以及兩種最小劃分的大小均為零。
劃分不同於單獨一條長鏈或單獨一個大反鏈:它必須恰好一次地容納每個元素。任何反鏈與每條鏈至多相交於一個元素。因此反鏈的大小為每個鏈劃分的部分數給出下界。同樣,每條鏈也為反鏈劃分的大小給出下界。
定義 6.2.2
(二分嚴格比較圖)
取 的兩個獨立副本 。當且僅當原偏序集中 時,把 與 相連。同一元素的兩個副本是不同的頂點,並且不存在邊 。該圖使用全部嚴格比較,包括由遞移性推出的比較。
匹配是端點互不相交的邊的集合,其最大大小記作 。頂點覆蓋是與圖中每條邊都相交的頂點集合。這些圖論定義針對的是雙副本圖,而鏈與反鏈由原偏序集的元素構成。明確保持這一區分可避免把兩個副本重複計數。
定理/命題
引理 6.2.3
(二分圖中的匹配與頂點覆蓋)
在每個有限二分圖中,匹配的最大大小等於頂點覆蓋的最小大小。
定理 6.2.4
(狄爾沃斯有限鏈劃分定理)
對每個有限偏序集 ,劃分 所需鏈的最少數目等於 。更確切地說,設 , 為嚴格比較圖中最大匹配的大小,則這兩個量都等於 。由一個最大匹配和一個大小相同的頂點覆蓋,可以構造出最優鏈劃分和最大反鏈。
定理 6.2.5
(高度版本:反鏈劃分)
對每個有限偏序集 ,劃分所需反鏈的最少數目等於 。對於非空的 ,令 為以 為終點的最大鏈的大小。 的非空水平集構成一個最優反鏈劃分。
這兩個命題在劃分問題中交換了鏈與反鏈的角色。高度定理有簡短的直接證明;寬度定理則需要更實質的論證。僅僅反轉序關係並不能交換鏈與反鏈,因為這樣不會改變可比性。
證明思路或證明
證明
(二分圖中的匹配與覆蓋)
我們首先論證證明中用到的二分圖匹配—覆蓋事實。取任意有限二分圖的一個最大匹配,其兩部分為 。從未匹配的左頂點集 出發,從左到右沿未匹配邊行進,從右到左沿匹配邊行進,並設 分別為兩部分中可達的頂點集。沒有未匹配的右頂點是可達的,因為由此得到的交錯路徑會令匹配變大。
每個可達的右頂點都與一個可達的左頂點匹配,並且 之外的每個可達左頂點都是經由其匹配邊到達的。因此該匹配把 與 配對。此外,可達左頂點的每個鄰點也是可達的:未匹配邊可以被沿用,而它的匹配鄰點(如果有)就是搜尋中它的前驅。於是
覆蓋每一條邊,且 ,即匹配的大小。每個覆蓋的大小至少等於每個匹配的大小,因為互不相交的匹配邊需要互不相同的覆蓋頂點。這就證明了所需的匹配—覆蓋等式,包括空圖的情形。
證明
(由匹配得鏈,由覆蓋得反鏈)
現在對嚴格比較圖使用一個最大匹配。把每條匹配邊 替換為原元素上的有向連接 。每個元素至多有一條出邊和一條入邊。不存在有向圈,因為嚴格序關係構成的圈會與遞移性及非自反性矛盾。因此這些連接構成互不相交的有向路徑,容許孤立頂點。每條路徑都是一條鏈,路徑的數目為 。
反過來,一個分成 部分的鏈劃分,在每條鏈內部相鄰元素之間給出匹配邊。大小為 的鏈給出 條邊,故總共有 條邊。左、右副本恰好施加了所需的前驅與後繼限制。因此 ,這證明 是最小鏈劃分的大小。
在雙副本圖中選取大小為 的頂點覆蓋 ,並令
如果 中有兩個元素可比,則它們對應的比較邊沒有被覆蓋。因此 是反鏈。至多 個不同的原標號有副本在 中,所以 。所構造的鏈劃分對每個反鏈給出相反方向的界。於是 ,這就證明了狄爾沃斯定理。我們沒有假設覆蓋對每個標號至多包含一個副本;計數不等式和相反方向的界已經足夠。
證明透視
劃分與障礙在同一個數相遇
兩個互相獨立的構造在同一個數相遇。匹配給出有 個部分的鏈劃分;使連接構成路徑的,是匹配對每個左副本和每個右副本都至多使用一次,所以雙副本的設計恰好就是「至多一個後繼、至多一個前驅」的規則,而非自反性與遞移性排除了有向圈。覆蓋給出大小至少為 的反鏈;關鍵一步是只要某標號有一個副本被覆蓋就把它排除,於是 內任何比較 都會留下未被覆蓋的邊 。單獨任何一個構造都不能證明最優性。二分圖引理只經由 進入,正是它令兩個計數重合:反鏈至少有 個元素,而它的元素分屬劃分中不同的鏈,故至多有 個。遞移性用了兩次:一次排除有向圈,一次把所有比較都放進圖中;若缺少後者,劃分中一條鏈的相鄰元素之間未必有邊。
證明
(秩水平集構成最優反鏈劃分)
對於高度定理,若 ,則把 接在以 為終點的一條最長鏈之後,得到 。因此秩相同的元素互不可比。這些水平集把偏序集劃分為至多 個反鏈。大小為 的鏈至少需要這麼多個反鏈部分,所以該劃分是最優的。空集情形由約定得出。
例題詳解
例題 6.2.6
(一個前驅與兩個互不可比的後繼)
設 且 ,其中 互不可比。比較圖有邊 ,所以 。使用 的匹配給出鏈 。覆蓋 使 的兩個副本都落在覆蓋之外,從而給出最大反鏈 。因此寬度為二。秩水平集為 與 ,這是大小為二的最優反鏈劃分,其大小也等於高度。
例題 6.2.7
(十二的因數同時提供兩種證書)
按整除關係對 排序。鏈 與 給出兩部分的劃分; 是反鏈,證明寬度為二。對應的匹配有邊 。覆蓋 與每條嚴格整除邊都相交,且大小同樣為四。其未被覆蓋的原標號恰為四與六。最長鏈的大小為四,所以高度定理改而需要四個反鏈部分。
例題 6.2.8
(僅用覆蓋邊會得到錯誤的最優化問題)
取五個元素,滿足 、、、 以及所有由遞移性得到的比較。寬度為二: 與 是鏈,而 是反鏈。只使用哈塞(Hasse)圖的覆蓋邊時,最大匹配的大小為二,因為至多一條連接可以進入 ,至多一條可以離開 。錯誤的公式於是會給出三條鏈。加入比較 後,得到大小為三的匹配和正確答案二。鏈不必使用位於其兩個成員之間的每一個元素。
提取實際的劃分
證明描述了一種具體的重構方法。對每個原元素,記錄其匹配的後繼和匹配的前驅(如果存在)。從每個沒有匹配前驅的元素開始建立一條鏈,並反覆沿其後繼前進直到沒有後繼為止。每個元素恰好出現在一條這樣的路徑中。無圈性保證每個連通分支中存在起點,而度數限制則防止出現分叉或合併。
兩個副本使得鏈內部的元素可以同時有前驅和後繼,卻不容許有兩個前驅:那樣會在兩條匹配邊中使用同一個右副本頂點。兩個後繼同樣會重複使用某個左副本頂點。因此匹配施加的是路徑約束,而不是要求原元素總共只出現在一條連接中。
反鏈的重構採用相反的視角。僅當一個原標號的兩個副本都不在覆蓋中時,才選取該標號。若僅因左副本未被覆蓋就選取,則不夠:某條比較邊可能恰在另一個被選標號的右副本處被覆蓋。兩個副本都不在覆蓋中,才是使可比性不可能出現的精確性質。
寬度與高度約束總大小
最優鏈劃分有寬度個部分,每個部分的大小至多為高度。因此
這個界並不能確定各條鏈,但常常立即給出障礙。如果偏序集多於九個元素,則其高度和寬度不可能都至多為三。等號是可能成立的,例如三條長度為三且互不可比的鏈。
一個應用涉及由互不相同的實數組成的序列。對其下標定義序:當 ,或 且下標 處的值較小時,稱 。鏈即遞增子序列。由於各值互異,反鏈按下標順序讀出即為遞減子序列。若序列有 項,則不可能同時滿足所有遞增子序列長度至多為 且所有遞減子序列長度至多為 。否則大小界將給出至多 項。因此必定出現相應的更長子序列之一。
互異性假設解釋了為何不等式是嚴格的。若有重複值,按下標順序不可比的一對元素的值可能相等而非遞減。可以表述相關的非嚴格變體,但它們需要選定相等情形的約定,不應從互異值的論證中原樣推斷。
概念視角結構
高度與寬度刻劃不同的障礙
長鏈迫使反鏈部分很多。寬反鏈迫使鏈部分很多。哈塞圖所畫出的高度或每行的長度不一定等於這兩個量中的任何一個。劃分定理所依據的是可比性和經過證明的極值,而不是圖中頂點碰巧被放在何處。
秩水平集計算的是甚麼
高度證明中使用的秩,是以某元素為終點的最長鏈的大小,而不是圖中任意的標記。沿著線性擴張計算時,它等於其嚴格前驅的最大秩加一,沒有前驅時取零。每個前驅的秩此時都已可得。這給出反鏈水平集,並且只要記住取得每個最大值的前驅,還能得到最長鏈的證書。
偏序集不必是分級的:不同的極大鏈可能具有不同的長度。最長鏈秩依然適用,因為只需要嚴格遞增這一性質。證明中沒有用到每個覆蓋關係都使秩恰好增加一的假設。強加這一更強的條件只會不必要地排除有效的例子。
常見錯誤
反例模式
互換高度與寬度會改變問題
四元全序集的寬度為一,高度為四。它需要一個鏈部分,卻需要四個反鏈部分。反轉其序並不改變這兩個值:所有元素對仍然可比。正確的命題把最小鏈劃分與寬度配對,把最小反鏈劃分與高度配對;它們不是透過互換措辭、不加新證明就能得到的。
常見錯誤
(用哈塞圖的邊代替全部嚴格比較)
不要未經論證就用哈塞圖的邊取代嚴格比較圖。對滿足 、、、 的五元偏序集,哈塞圖的邊只容許大小為二的匹配,於是 會給出三條鏈;而比較 給出大小為三的匹配,正確答案是二。劃分中一條鏈的相鄰元素不一定構成覆蓋關係。
常見錯誤
(最少鏈數不是最長鏈)
鏈部分的最小數目必須照顧所有元素,由寬度控制;單條鏈的最大大小則是高度。在 的因數中,最長鏈 有四個元素,但兩條鏈 與 已經劃分了整個偏序集。
總結
二分圖匹配編碼了鏈中相鄰的連接,而最小覆蓋則揭示出一個大小等於所需劃分大小的反鏈。這以構造性的方式證明了狄爾沃斯定理。以某元素為終點的最長鏈的秩給出互補的反鏈劃分定理,並導出有用的大小界和子序列界。
練習
快速檢查
(對三元基集上的子集偏序集,給出劃分為三條鏈的方法,並給出一個三元反鏈以證明其最優性。)
每個子集(包括空集)必須在劃分中恰好出現一次。
解答 · 答案
在基集 上,使用鏈 、 以及 。這些互不相交的鏈包含全部八個子集。三個單元素集構成反鏈,所以至少需要三條鏈。所給出的劃分達到了這個下界。
快速檢查
(對滿足 、、、 的五元偏序集,求秩水平集和一條最長鏈。比較這兩個劃分定理。)
要包含由遞移性推出的所有比較。
解答 · 答案
秩在 上為一,在 上為二,在 上為三。它們的水平集給出三個反鏈部分。一條最長鏈是 ,證明高度為三。兩條鏈 與反鏈 證明寬度為二,且最小鏈劃分的大小為二。這兩個最優劃分的數目確實可以不同。
快速檢查
(證明:任何由十個互不相同的實數組成的序列,都含有長度為四的遞增子序列或長度為四的遞減子序列。)
指明下標偏序集,並應用已證明的大小界。
解答 · 答案
按下標與數值同時增大來對下標排序,並包含相等情形以保證自反性。遞移性與反對稱性由這兩個嚴格不等式得出。如果所要求的兩種子序列都不存在,則每條鏈和每個反鏈的大小都至多為三:互異性使得反鏈按下標順序讀出時是遞減的。由大小界將得到十至多為九,矛盾。因此至少存在所述子序列之一。