1、偏序关系偏序关系 离散数学关系离散数学关系 南京大学计算机科学与技术系南京大学计算机科学与技术系 内容提要内容提要l偏序与全序偏序与全序l哈斯图哈斯图l极大极大 (小小)元、最大元、最大(小小)元元l上上(下下)界、上界、上(下下)确界确界l良序良序l链与反链（链与反链（ Dilworth定理定理 ）l格及其性质格及其性质偏序关系的定义偏序关系的定义(Partial Order)l偏序关系偏序关系：集合上的：集合上的自反的、反对称的、传递的关系自反的、反对称的、传递的关系l通常记作通常记作 l定义了偏序关系的集合称为偏序集，记作定义了偏序关系的集合称为偏序集，记作(A, )l举例举例l集合包含
2、关系集合包含关系 (2A, ), 其中其中A是集合是集合l(Z+, |)，Z+是正整数集，是正整数集，“|”是整除关系是整除关系l既是偏序又是等价的关系既是偏序又是等价的关系l任意非空集合任意非空集合A上的恒等关系上的恒等关系IA“字典顺序字典顺序”l设设 是非空集合是非空集合A上的偏序关系，定义上的偏序关系，定义A A上的关系上的关系R如下：如下： (x1, y1) R (x2, y2) iff. x1 x2且且x1 x2, 或者或者x1 = x2且且y1 y2l易证易证R是是A A上的偏序关系上的偏序关系l给定有限字符集合给定有限字符集合 ，若在，若在 上有一个偏序关系，类似上述上有一个偏
3、序关系，类似上述办法，可以对任意正整数办法，可以对任意正整数k,定义定义 k(由由 中字符构成的长度中字符构成的长度为为k的串的集合的串的集合)上的偏序关系。加以适当的技术处理，则上的偏序关系。加以适当的技术处理，则容易定义容易定义 +(由由 中字符构成的长度为任意正整数的串的集中字符构成的长度为任意正整数的串的集合合)上的偏序关系：字典关系上的偏序关系：字典关系l注意：在通常的字典关系中，任何两个元素均可比。注意：在通常的字典关系中，任何两个元素均可比。全序：一种特殊的偏序关系全序：一种特殊的偏序关系l如果对如果对a, b A，a b和和b a中有一个成立，则中有一个成立，则a,b可比。可比
4、。l设设R是是A上的偏序关系，如果上的偏序关系，如果A中的任意两个元素都是中的任意两个元素都是可比的，则称可比的，则称R是是A上的上的全序关系（或线序关系）全序关系（或线序关系）l举例（全序）举例（全序）l实数集上的实数集上的“不大于不大于” 关系关系 、基于拉丁字母表的字典顺序、基于拉丁字母表的字典顺序偏序集上的偏序集上的“小于小于”关系及覆盖关系及覆盖l设设(A, )是偏序集是偏序集lA上的上的“小于小于”关系关系 定义如下：定义如下： x y iff x y x y l元素元素y覆盖覆盖x定义如下：定义如下： x y ，且不存在，且不存在z A使得使得 x z y哈斯图哈斯图 l一般的关
5、系图可以表示偏序关系一般的关系图可以表示偏序关系l哈斯图哈斯图(Hasse)：利用特定性质简化图示方法：利用特定性质简化图示方法l利用自反性省略圈利用自反性省略圈l利用反对称性省略箭头利用反对称性省略箭头l利用传递性省略部分连线（覆盖）利用传递性省略部分连线（覆盖）abcabca,b,ccbab,ca,ca,b (a,b,c)上的包含关系上的包含关系9128101156432171,2,.,12上的整除关系上的整除关系24846231211,2,3,4,6,8,12,24上的整除关系上的整除关系偏序集中的特殊元素偏序集中的特殊元素 ：极大：极大(小小)lx是偏序集是偏序集(A, )中的极大元中
6、的极大元 iff. l对任意对任意yA,若若x y, 则则x=ylx是偏序集是偏序集(A, )中的极小元中的极小元 iff. l对任意对任意yA,若若y x, 则则x=yl有关极大元与极小元的讨论有关极大元与极小元的讨论l不一定存在，但是，有穷集合一定有极大不一定存在，但是，有穷集合一定有极大(小小)元元l不一定唯一不一定唯一l一个元素可能兼为极大一个元素可能兼为极大(小小)元元没有比它更大没有比它更大 ( (小小) )的了！的了！偏序集中的特殊元素偏序集中的特殊元素 ：最大：最大(小小)lx是偏序集是偏序集(A, )中的最大元中的最大元 iff. l 对任意对任意yA, y xlx是偏序集是
7、偏序集(A, )中的最小元中的最小元 iff. l对任意对任意yA, x yl有关最大元与最小元的讨论有关最大元与最小元的讨论l可能不存在可能不存在l若存在，必唯一。若存在，必唯一。它比谁都要大它比谁都要大 ( (小小) )！123624偏序集中的特殊元素偏序集中的特殊元素 ：上：上( (下下) )确界确界l上界上界：对于偏序集：对于偏序集(A, )和和A的子集的子集B，若存在，若存在y A，对对B中任意元素中任意元素x, 均有均有x y,则则y是是B的上界的上界。l最小上界最小上界：如果：如果B的上界构成的偏序集有的上界构成的偏序集有最小元最小元，则该最小元为则该最小元为B的的最小上界（最小
8、上界（lub），上确界），上确界。l类似地可以定义下界、类似地可以定义下界、最大下界（最大下界（glb），下确界），下确界。l有关上有关上(下下)界的讨论界的讨论l不一定存在；不一定存在；l最小上界若存在，则必唯一。最小上界若存在，则必唯一。从哈斯图看特殊元素从哈斯图看特殊元素最大最大/极大极大极小极小极小极小子集子集BB的上界的集合的上界的集合最小上界最小上界拓扑排序（拓扑排序（Topological sorting）abdcgefabdecgfacgdbef有向无环图上构造一种线性有向无环图上构造一种线性序序良序良序l定义：给定集合定义：给定集合A上的偏序上的偏序 ，若，若A的的任一非空子
9、集均任一非空子集均存在最小元素存在最小元素，则该偏序为良序。，则该偏序为良序。l良序必为全序良序必为全序l对任意对任意a,b A, a,b必有最小元，则必有最小元，则a,b一定可比一定可比l实际上，实际上，“反对称性反对称性+任一非空子集存在最小元任一非空子集存在最小元”就能就能够保证全序性质（偏序性质够保证全序性质（偏序性质+任何两个元素均可比）。任何两个元素均可比）。l自反性：对任意自反性：对任意a A, a也必有最小元，即也必有最小元，即a al传递性：假设传递性：假设a b, b c, a, b, c的最小元素只能是的最小元素只能是a, 因此因此a cl任何两个元素可比，上面已证明。任
10、何两个元素可比，上面已证明。关于次序关系的进一步讨论关于次序关系的进一步讨论l注意：良序结构上可以实施数学归纳法注意：良序结构上可以实施数学归纳法l全序是否一定是良序？全序是否一定是良序？l当当A是无穷集合时，是无穷集合时，全序不一定是良序全序不一定是良序l例如：例如： (R， ), 任何开区间上没有最小元素任何开区间上没有最小元素l良序良序 全序全序 偏序偏序l偏序偏序/全序全序/良序的逆关系是否仍为偏序良序的逆关系是否仍为偏序/全序全序/良序？良序？l良序的逆关系不一定是良序良序的逆关系不一定是良序l例如例如(N， )链链与与反链反链l链与反链链与反链l设设C是偏序集是偏序集(P, )的一
11、个子集的一个子集l如果如果C中任何两个元素均可比，则中任何两个元素均可比，则C构成一个链构成一个链l如果如果C中任何两个元素均不可比，则中任何两个元素均不可比，则B构成一个反链构成一个反链链与反链（示例）链与反链（示例）fabcdeg.元素个数最多的反链，含元素个数最多的反链，含k个元素个元素a1a2aiak互不相交）ikiiCPC(1l链覆盖链覆盖 是是(P, )中一组互不相交的链中一组互不相交的链, 它们一起包它们一起包含了含了P中的所有元素中的所有元素.lDilworth 定理定理 (1950) 在任意在任意有限有限偏序集偏序集(P, )中中, 覆盖覆盖P的最小链数等于的最小链数等于P中
12、最长反链的长度（元素个数）中最长反链的长度（元素个数）.l注：覆盖注：覆盖P的链数的链数 P中任一反链的元素个数中任一反链的元素个数. 等价结论等价结论:有限有限偏序集中存在一个链覆盖和一个反链，它们偏序集中存在一个链覆盖和一个反链，它们大小相等大小相等Dilworth定理定理Dilworth定理的归纳证明定理的归纳证明l证明证明. 按照按照P中元素个数（中元素个数（|P|=1, 2 ）进行归纳证明）进行归纳证明. 设设a为为P中的一个极大元素中的一个极大元素, P =P-al设设(P, )有一个大小为有一个大小为k的反链的反链a1, a2, , ak，并有一个规模，并有一个规模为为k的链覆盖
13、的链覆盖C1, C2, , Ck.l对任意对任意Ci , P中大小为中大小为k的任一反链均有唯一的元素属于的任一反链均有唯一的元素属于Ci，这些元素有一个最大元，记为这些元素有一个最大元，记为xi.lA=x1, x2, , xk必是反链。否则，不妨假设必是反链。否则，不妨假设A中有两个元素中有两个元素 xi xj. 根据根据xj的定义，的定义，P中必有一个大小为中必有一个大小为k的反链的反链Aj, xj是是Aj和和Cj的公共元素，假设的公共元素，假设y是是Aj和和Ci的公共元素，则的公共元素，则y xi. 从而从而y xj.与与Aj是反链是反链矛盾矛盾.aaixia1x1akxkDilwort
14、h定理的归纳证明定理的归纳证明（图示）图示）C1CiCkP的反链的反链C1, C2, , Ck为为P的链覆盖的链覆盖Dilworth定理的归纳证明（续）定理的归纳证明（续）l如果如果 a, x1, x2, , xk是是P中的反链，而中的反链，而P的链覆盖的链覆盖a , C1, C2, , Ck就是规模为就是规模为k+1的覆盖的覆盖. 得证得证.l如果如果 a, x1, x2, , xk不是不是P中的反链，即中的反链，即:存在某个存在某个xm使得使得xm a. （a是极大元，不会出现是极大元，不会出现 a xm.） 令令 K = a z Cm | z xm. 显然显然K是是P中的一条链中的一条链
15、. P-K中最中最大反链的大小为大反链的大小为k-1（根据（根据xm的定义，的定义， P-K中没有含中没有含k个元素个元素的反链）的反链）. 由归纳假设，由归纳假设，P-K有大小为有大小为k-1的一个链覆盖，该的一个链覆盖，该覆盖与覆盖与K构成构成P的链覆盖（链数为的链覆盖（链数为k），）， 已知已知x1, x2, , xk 是是P中的反链（含中的反链（含k个元素）个元素）. 得证得证.“道是无序却有序道是无序却有序”l自然数自然数1,2,3,n2+1的任何一种排列中，必然含一的任何一种排列中，必然含一个长度不小于个长度不小于n+1的严格递增链或严格递减链。的严格递增链或严格递减链。建立问题的
16、偏序模型建立问题的偏序模型l给定给定1, 2 n2+1(=m)的一种排列的一种排列 v1v2vm，定义集合：，定义集合：lA= (i,vi) |i=1,2,n2+1l建立两个偏序关系建立两个偏序关系R1和和R2l(i, vi)R1(j, vj) iff. （ij并且并且vivj）或者）或者 (i, vi)=(j, vj)l(i, vi)R2(j, vj) iff. （ivj）或者）或者 (i, vi)=(j, vj)lR1 R2 = IA, R1 R2 = A A /R1的链是的链是R2反链。反链。l问题：一定存在问题：一定存在A的一个至少含的一个至少含n+1个元素的子集，它是个元素的子集，它
17、是R1的链或者的链或者R2的链。的链。l若若R1链的长度均链的长度均 n, 即即R2反链的大小均反链的大小均 n，则存在，则存在个数个数k n的的R2覆盖，覆盖，有长度超过有长度超过n的的R2链，否则元素个数链，否则元素个数 n2.矛盾矛盾.格格l定义：定义：l设设(S, )是偏序集是偏序集l x, y S, 存在存在x,y的最小上界的最小上界lubx,y , 记为记为x y。l x, y S, 存在存在x,y的最大下界的最大下界glbx,y, 记为记为x y。l则称则称S关于关于 构成构成格格。lub : “least upper bound”glb : “greatest lower bo
18、und 格的例子格的例子l( (B), )l x y=x y, x y=x yl(x N+ | x|60, |)，60的正因子集合及整除关系的正因子集合及整除关系lx y=gcd(x,y), x y=lcm(x,y)l(, )l x y=minx,y, x y=maxx,y 格（示例）28格（示例）29格与哈斯图格与哈斯图l右边两个哈斯图所表示的偏序集右边两个哈斯图所表示的偏序集不是不是格格 格与哈斯图（续）31格的基本关系式格的基本关系式l根据根据“最小上界最小上界”和和“最大下界最大下界”的定义，有的定义，有如下关系式：如下关系式：la c, b c a b clc a, c b c a
19、b格的性质格的性质l若若(S, )是格，则：是格，则： a, b S: a b a b=a a b=bl采用循环证明采用循环证明la b a b=ala b=a a b=bla b=b a b 格的性质格的性质l设设(S, )是格，则是格，则(S, , )有下列性质有下列性质:l结合律结合律：(a b) c = a (b c), (a b) c = a (b c)l交换律交换律：a b = b a, a b = b al吸收律吸收律： a (a b) = a, a (a b)=a作业作业l教材教材8.6lp. 443-446: 29, 31, 43, 45, 51, 60 (第60题请参考8.6.6节)
