偏序（partial order）定義為滿足自反性、反對稱性、傳遞性的關(guān)系。因此，和為偏序關(guān)系，但和不是偏序關(guān)系。偏序集合（partially order set）S就是指具備偏序關(guān)系R的集合。有偏序關(guān)系的集合可簡寫為偏序集（poset）。
AOV網(wǎng)所代表的一項工程中活動的集合就是一個偏序集合。測試AOV網(wǎng)是否具有回路（即是否是一個有向無環(huán)圖）的方法，就是在AOV網(wǎng)的偏序集合下構(gòu)造一個拓撲序列，如果能構(gòu)造這樣的拓撲序列，則說明該AOV網(wǎng)沒有回路，這時的拓撲序列是AOV網(wǎng)中所有活動的一個全序集合。
內(nèi)容介紹
定義
設(shè)R是非空集合A上的一個二元關(guān)系，若R滿足：自反性、反對稱性、傳遞性，則稱R為A上的偏序關(guān)系。
以下為定義：
非嚴(yán)格偏序，自反偏序
給定集合S，“≤”是S上的二元關(guān)系，若“≤”滿足：
自反性：，有；
反對稱性：，；
傳遞性：?a，b，，且；
則稱“≤”是S上的 非嚴(yán)格偏序或 自反偏序。
嚴(yán)格偏序，反自反偏序
給定集合S，“<”是S上的二元關(guān)系，若“<”滿足：
反自反性：，有；
非對稱性：?a，；
傳遞性：?a，b，；
則稱“<”是S上的 嚴(yán)格偏序或 反自反偏序。
嚴(yán)格偏序與有向無環(huán)圖(dag)有直接的對應(yīng)關(guān)系。一個集合上的嚴(yán)格偏序的關(guān)系圖就是一個有向無環(huán)圖。其傳遞閉包是它自己。
下面是一些主要的例子:
自然數(shù)的集合配備了它的自然次序(小于等于關(guān)系)。這個偏序是全序。
整數(shù)的集合配備了它的自然次序。這個偏序是全序。
自然數(shù)的集合的有限子集。這個偏序是全序。
自然數(shù)的集合配備了整除關(guān)系。
給定集合的子集的集合(它的冪集)按包含排序。
向量空間的子空間的集合按包含來排序。
一般地說偏序集合的兩個元素x和y 可以處于四個互斥關(guān)系中的恰好一個: 要么，要么，要么，要么x 和y 是“不可比較”的（非前三者）。全序集是用不存在第四種可能性的集合: 所有元素對都是可比較的，并且聲稱三分法成立。自然數(shù)、整數(shù)、有理數(shù)和實數(shù)都關(guān)于自然代數(shù)排序是全序的，而復(fù)數(shù)不是。這不是說復(fù)數(shù)不能全序排序；比如我們可以按詞典次序排序它們，通過當(dāng)且僅當(dāng)，但是這種排序沒有合理的大小意義因為它使得 1 大于 100 i。按絕對大小排序它們產(chǎn)生在其中所有對都是可比較的預(yù)序，但這不是偏序因為 1 和 i 有相同的絕對大小但卻不相等，違反了反對稱性。
Dilworth定理
對于一個偏序集，其最少鏈劃分數(shù)等于其最長反鏈的長度。
參考資料 >