在有向無環圖中，有如下的一些定義和性質：
鍊：一條鍊是一些點的集合，鍊上任意兩個點x, y，滿足要麼 x 能到達 y ，要麼 y 能到達 x 。
反鍊：一條反鍊是一些點的集合，鍊上任意兩個點x, y，滿足 x 不能到達 y，且 y 也不能到達 x。
又有諸如以下定理：
一、有向無環圖最小不相交路徑覆寫
定義：用最少的不相交路徑覆寫所有頂點。
定理：把原圖中的每個點V拆成Vx和Vy，如果有一條有向邊A->B，那麼就加邊Ax-By。這樣就得到了一個二分圖，最小路徑覆寫=原圖的節點數-新圖最大比對。
簡單證明：一開始每個點都獨立的為一條路徑，總共有n條不相交路徑。我們每次在二分圖裡加一條邊就相當于把兩條路徑合成了一條路徑，因為路徑之間不能有公共點，是以加的邊之間也不能有公共點，這就是比對的定義。是以有：最小路徑覆寫=原圖的節點數-新圖最大比對。
二、有向無環圖最小可相交路徑覆寫
定義：用最小的可相交路徑覆寫所有頂點。
算法：先用floyd求出原圖的傳遞閉包，即如果a到b有路，那麼就加邊a->b。然後就轉化成了最小不相交路徑覆寫問題。
三、偏序集的最大反鍊
定義：偏序集中的最大獨立集。
Dilworth定理：對于任意偏序集都有，最大獨立集(最大反鍊)=最小鍊的劃分(最小可相交路徑覆寫).
通過Dilworth定理, 我們就可以把偏序集的最大獨立集問題轉化為最小可相交路徑覆寫問題了。
經典例題：
BZOJ 1143祭祀river